Loading... # 一、判断图中的两点是否连通 ### 1.Floyed 算法 时间复杂度:$O(N^3)$ 算法实现: 把相连的两点间的距离设为 dis[i][j] = true,不相连的两点设为 dis[i][j] = false,用 Floyde 算法的变形实现: ```cpp for(k = 1; k <=n; k++) for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]); ``` 最后如果 dis[i][j] = true 的话,那么就说明 i、j 两点之间有路径连通。 有向图和无向图都适用。 ### 2.遍历算法 时间复杂度:$O(N^2)$ 算法实现: 从任意一个顶点出发,进行一次遍历,能够从这个点出发到达的点就与起点是连通的。就这样就可以求出此顶点和其他各个顶点的连通情况。所以只要把每个顶点作为出发点都进行一次遍历,就能知道任意两个顶点之间是否有路存在。 可以使用 DFS 算法实现。 有向图 和 无向图 都适用。 # 二、最小环问题 最小环就是指在一张图中找出一个环,使得这个环上的各条边的权值之和最小。在 Floyed 的同时,可以顺便算出最小环。 记两点间的最短路径为 dis[i][j],g[i][j] 边为<i,j> 的权值。 ```cpp for(k = 1; k <= n; k++) { for(i = 1; i <= k - 1; i++) for(j = 1; j <= k - 1; j++) answer = min(answer,dis[i][j] + g[j][k] + g[k][i]); for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); } ``` answer 即为这张图的最小环。 一个环中的最大结点为 k (编号最大),它与相连的两个点为 i、j,这两个环的最短长度为g[i][k] + g[k][i] + (i 到 j 的路程中,所有结点编号都小于 k 的最短路径长度)。 根据 Floyed 的原理,在最外层循环做了 k - 1 次之后,dis[i][j]则代表了 i 到 j 的最短路径中,所有结点都小于 k 的最短路径。 综上所述,该算法一定能找到图中最小环。 **这里还有一个知识,就是 求有向图的强连通分路,我不太明白,先放下。** 最后修改:2021 年 09 月 12 日 © 禁止转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏