グラフの推移閉包を見つけるための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:
   // 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