C ++程序来查找图形的传递闭合

如果给出了有向图，则对于给定图中的所有顶点对(i,j)，确定一个顶点j是否可以从另一个顶点i到达。可达到意味着从顶点i到j有一条路径。此可及性矩阵称为图的传递闭合。Warshall算法通常用于查找给定图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:
   //a的ASCII码是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