有什么算法,如何在C语言中采用warshall算法判断一个无向图是否连通
答案:1 悬赏:10 手机版
解决时间 2021-05-17 04:09
- 提问者网友：凉末
- 2021-05-16 06:07
有什么算法,如何在C语言中采用warshall算法判断一个无向图是否连通
最佳答案
- 五星知识达人网友：低血压的长颈鹿
- 2021-05-16 06:46
所谓无向图连通，就是任意两个点都存在路径到达所以需要验证任意a,b两个点之间是否有路。
Warshall算法是一种动态规划算法。
首先设连通矩阵为M，i,j之间连通则Mij = 1,否则Mij = 0
设可能中间点的为c，c = 0
检查所有的ij组合，如果Mic == 1且 Mcj == 1则 Mij变为1，否则不变
然后c++，如果c大于点的数量则退出
最后如果M中全是1则为连通图
Warshall算法是一种动态规划算法。
首先设连通矩阵为M，i,j之间连通则Mij = 1,否则Mij = 0
设可能中间点的为c，c = 0
检查所有的ij组合，如果Mic == 1且 Mcj == 1则 Mij变为1，否则不变
然后c++，如果c大于点的数量则退出
最后如果M中全是1则为连通图
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯