Chương trình C ++ để tìm sự đóng cửa bắc cầu của một đồ thị G cho trước

Nếu một đồ thị có hướng được đưa ra, hãy xác định xem đỉnh j có thể đạt tới từ một đỉnh i khác đối với tất cả các cặp đỉnh (i, j) trong đồ thị đã cho hay không. Có thể tiếp cận có nghĩa là có một đường đi từ đỉnh i đến j. Ma trận khả năng tiếp cận này được gọi là đóng bắc cầu của một đồ thị. Thuật toán Warshall thường được sử dụng để tìm Bao hàm bắc cầu của một đồ thị cho trước G. Đây là một chương trình C ++ để thực hiện thuật toán này.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

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