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 (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
