设G是一个无向图。它的传递闭包(tansitive closure )是一个0/1 数组tc,当且仅当G存在一条边数大于1的从i到j的路径时,tc[i][j]=1。用c++编写一个方法 graph: undirectedTCo,计算且返回 G 的传递闭包。方法的复杂性应为O(n2)
时间: 2023-03-01 17:00:09 浏览: 76
这道题可以用邻接矩阵来实现。具体实现方法如下:
1. 创建一个邻接矩阵,将原图G的每一条边对应的点都标记为1。
2. 对于每一个点,将其作为中间点,遍历整个邻接矩阵,如果存在从i到j的路径,则将tc[i][j]设为1。
3. 返回传递闭包矩阵tc。
算法的时间复杂度为O(n^3),因为需要遍历整个邻接矩阵。
以下是C语言的代码实现:
```
#include <stdio.h>
#include <stdlib.h>
#define V 4
void printSolution(int tc[][V])
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
printf("%d ", tc[i][j]);
printf("\n");
}
}
void transitiveClosure(int graph[][V])
{
int tc[V][V];
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
tc[i][j] = graph[i][j];
for (int k = 0; k < V; k++)
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
tc[i][j] = tc[i][j] || (tc[i][k] && tc[k][j]);
}
}
printSolution(tc);
}
int main()
{
int graph[V][V] = { {1, 1, 0, 1},
{0, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1}
};
transitiveClosure(graph);
return 0;
}
```