โปรแกรม C++ เพื่อค้นหาการปิดสกรรมกริยาของกราฟ

หากให้กราฟกำกับ ให้พิจารณาว่าจุดยอด j สามารถเข้าถึงได้จากจุดยอดอื่น i สำหรับคู่จุดยอดทั้งหมด (i, j) ในกราฟที่กำหนดหรือไม่ เข้าถึงได้ หมายความว่ามีเส้นทางจากจุดยอด i ถึง j เมทริกซ์ความสามารถในการเข้าถึงนี้เรียกว่าการปิดสกรรมกริยาของกราฟ โดยทั่วไปแล้วอัลกอริทึมของ Warshall จะใช้เพื่อค้นหา Transitive Closure ของกราฟ G ที่กำหนด นี่คือโปรแกรม C++ เพื่อใช้อัลกอริทึมนี้

อัลกอริทึม

Begin
   1. Take maximum number of nodes as input.
   2. For Label the nodes as a, b, c…..
   3. To check if there any edge present between the nodes
   make a for loop:
   // ASCII code of a is 97
   for i = 97 to (97 + n_nodes)-1
      for j = 97 to (97 + n_nodes)-1
         If edge is present do,
            adj[i - 97][j - 97] = 1
         else
            adj[i - 97][j - 97] = 0
      End loop
   End loop.
   4. To print the transitive closure of graph:
   for i = 0 to n_nodes-1
      c = 97 + i
   End loop.
   for i = 0 to n_nodes-1
      c = 97 + i
      for j = 0 to n_nodes-1
         Print adj[I][j]
      End loop
   End loop
End

ตัวอย่าง

#include<iostream>
using namespace std;
const int n_nodes = 20;
int main()
{
   int n_nodes, k, n;
   char i, j, res, c;
   int adj[10][10], path[10][10];
   cout << "\n\tMaximum number of nodes in the graph :";
   cin >> n;
   n_nodes = n;
   cout << "\nEnter 'y' for 'YES' and 'n' for 'NO' \n";
   for (i = 97; i < 97 + n_nodes; i++)
      for (j = 97; j < 97 + n_nodes; j++)
   {
      cout << "\n\tIs there an edge from " << i << " to "
      << j << " ? ";
      cin >> res;
      if (res == 'y')
         adj[i - 97][j - 97] = 1;
      else
         adj[i - 97][j - 97] = 0;
   }
   cout << "\n\nTransitive Closure of the Graph:\n";
   cout << "\n\t\t\t ";
   for (i = 0; i < n_nodes; i++)
   {
      c = 97 + i;
      cout << c << " ";
   }
   cout << "\n\n";
   for (int i = 0; i < n_nodes; i++)
   {
      c = 97 + i;
      cout << "\t\t\t" << c << " ";
      for (int j = 0; j < n_nodes; j++)
      cout << adj[i][j] << " ";
      cout << "\n";
   }
   return 0;
}

ผลลัพธ์

Maximum number of nodes in the graph :4
Enter 'y' for 'YES' and 'n' for 'NO'
Is there an edge from a to a ? y
Is there an edge from a to b ?y
Is there an edge from a to c ? n
Is there an edge from a to d ? n
Is there an edge from b to a ? y
Is there an edge from b to b ? n
Is there an edge from b to c ? y
Is there an edge from b to d ? n
Is there an edge from c to a ? y
Is there an edge from c to b ? n
Is there an edge from c to c ? n
Is there an edge from c to d ? n
Is there an edge from d to a ? y
Is there an edge from d to b ? n
Is there an edge from d to c ? y
Is there an edge from d to d ? n
Transitive Closure of the Graph:
a b c d
a 1 1 0 0
b 1 0 1 0
c 1 0 0 0
d 1 0 1 0