주어진 그래프 G의 전이적 폐쇄를 찾는 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
   construct 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 << "\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