如何在C语言中采用warshall算法判断一个无向图是否连通

来源:学生作业帮助网 编辑:作业帮 时间:2024/04/26 19:25:22
如何在C语言中采用warshall算法判断一个无向图是否连通

如何在C语言中采用warshall算法判断一个无向图是否连通
如何在C语言中采用warshall算法判断一个无向图是否连通

如何在C语言中采用warshall算法判断一个无向图是否连通
所谓无向图连通,就是任意两个点都存在路径到达
所以需要验证任意a,b两个点之间是否有路.
Warshall算法是一种动态规划算法.
首先设连通矩阵为M,i,j之间连通则Mij = 1,否则Mij = 0
设可能中间点的为c,c = 0
检查所有的ij组合,如果Mic == 1且 Mcj == 1则 Mij变为1,否则不变
然后c++,如果c大于点的数量则退出
最后如果M中全是1则为连通图