图的传递闭包
Transitive关闭可达性矩阵,以从图的顶点u到达顶点v。给定一个图,我们必须为所有顶点对(u,v)找到从另一个顶点u可达的顶点v。
最后一个矩阵是布尔类型。当顶点u到顶点v的值为1时,表示至少存在一条从u到v的路径。
输入和输出
Input: 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 Output: The matrix of transitive closure 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1
算法
transColsure(graph)
输入:给定的图形。
输出:传递闭包矩阵。
Begin copy the adjacency matrix into another matrix named transMat for any vertex k in the graph, do for each vertex i in the graph, do for each vertex j in the graph, do transMat[i, j] := transMat[i, j] OR (transMat[i, k]) AND transMat[k, j]) done done done Display the transMat End
<2>示例
#include#include #define NODE 4 using namespace std; /* int graph[NODE][NODE] = { {0, 1, 1, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}, {0, 0, 0, 0} }; */ int graph[NODE][NODE] = { {1, 1, 0, 1}, {0, 1, 1, 0}, {0, 0, 1, 1}, {0, 0, 0, 1} }; int result[NODE][NODE]; void transClosure() { for(int i = 0; i 输出结果 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1