C++ 程序查找图的传递闭包

c++server side programmingprogramming

如果给定一个有向图,确定对于给定图中的所有顶点对 (i, j),顶点 j 是否可从另一个顶点 i 到达。可达意味着从顶点 i 到 j 有一条路径。此可达性矩阵称为图的传递闭包。Warshall 算法通常用于查找给定图 G 的传递闭包。这是一个实现此算法的 C++ 程序。

算法

开始
   1. 以最大数量的节点作为输入。
​​   2. 将节点标记为 a、b、c……
   3. 检查节点之间是否存在任何边
   创建一个 for 循环:
   // a 的 ASCII 码为 97
   for i = 97 到 (97 + n_nodes)-1
      for j = 97 到 (97 + n_nodes)-1
         如果存在边,则执行
            adj[i - 97][j - 97] = 1
         else
            adj[i - 97][j - 97] = 0
      结束循环
   结束循环。
   4. 打印图的传递闭包:
   for i = 0 to n_nodes-1
      c = 97 + i
   结束循环。
   for i = 0 to n_nodes-1
      c = 97 + i
      for j = 0 to n_nodes-1
         打印 adj[I][j]
      结束循环
   结束循环
结束

示例

#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 (= 97; i < 97 + n_nodes; i++)
      for (= 97; j < 97 + n_nodes; j++)
   {
      cout << "\n\tIs there an edge from " << i << " to "
      << j << " ? ";
      cin >> res;
      if (res == 'y')
         adj[- 97][- 97] = 1;
      else
         adj[- 97][- 97] = 0;
   }
   cout << "\n\nTransitive Closure of the Graph:\n";
   cout << "\n\t\t\t ";
   for (= 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

相关文章