实现Warshell传递闭包算法注释C语言
时间: 2023-10-01 10:08:35 浏览: 47
以下是使用C语言实现Warshall传递闭包算法的代码,并附有注释:
```
#include <stdio.h>
#define MAXSIZE 10
void WarshallClosure(int graph[MAXSIZE][MAXSIZE], int n)
{
int i, j, k;
// 针对每一个点,检查它和其他点的连通性,并记录到传递闭包数组中
for(k = 0; k < n; k++)
{
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
// 如果i和j原本不相连,但是它们通过k点的连通,则更新传递闭包数组
if(graph[i][j] == 0 && graph[i][k] == 1 && graph[k][j] == 1)
{
graph[i][j] = 1;
}
}
}
}
}
int main()
{
int n, i, j;
int graph[MAXSIZE][MAXSIZE];
// 获取图形的大小
printf("请输入图形的大小:\n");
scanf("%d",&n);
// 获取图形的邻接矩阵
printf("请输入图形的邻接矩阵:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
scanf("%d",&graph[i][j]);
}
}
// 使用Warshall传递闭包算法更新传递闭包数组
WarshallClosure(graph, n);
// 打印传递闭包数组
printf("传递闭包数组如下:\n");
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
printf("%d ", graph[i][j]);
}
printf("\n");
}
return 0;
}
```
本算法的时间复杂度为O(n^3),不适用于较大规模的图形。传递闭包算法的本质是通过检测点之间的连通性来构建传递闭包图。在这个过程中,算法维护两个矩阵:邻接矩阵和传递闭包矩阵。邻接矩阵描述了图形的边缘关系,而传递闭包矩阵包含了所有由矩阵中任意两个点之间的连通所引起的连通性。当一个新的关系被检测到时,它将被添加到传递闭包矩阵中。在Warshall算法中,对于每一个点k,其余的点都会被遍历一遍,以便检查它们之间的连通关系,并更新传递闭包矩阵。 在本例中,邻接矩阵是graph,传递闭包矩阵被计算并输出给用户。