图的传递闭包

2023-06-21 05:57:03 344

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

图的传递闭包

输入和输出

算法

热门推荐

随机推荐