数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学图的传递闭包
传递闭包是图中从顶点 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<iostream>
#include<vector>
#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<NODE; i++)
for(int j = 0; j<NODE; j++)
result[i][j] = graph[i][j]; //initially copy the graph to the result matrix
for(int k = 0; k<NODE; k++)
for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++)
result[i][j] = result[i][j] || (result[i][k] && result[k][j]);
for(int i = 0; i<NODE; i++) { //print the result matrix
for(int j = 0; j<NODE; j++)
cout << result[i][j] << " ";
cout << endl;
}
}
int main() {
transClosure();
}输出
1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1
更新时间： 2020-06-16
1.7 万+ 浏览量
广告