判断无向图是否有回路
发布时间
阅读量：
阅读量
如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度 >=2 。
n 算法：
第一步：删除所有度 <=1 的顶点及相关的边，并将另外与这些边相关的其它 顶点的度减一。
第二步：将度数变为 1 的顶点排入队列，并从该队列中取出一个顶点重复步 骤一。
如果最后还有未删除顶点，则存在环，否则没有环。
n 算法分析：
由于有 m 条边， n 个顶点。如果 m>=n ，则根据图论知识可直接判断存在 环路。
（证明：如果没有环路，则该图必然是 k 棵树 k>=1 。根据树的性质，边的数 目 m = n-k 。 k>=1 ，所以： m<n ）
如果 m<n 则按照上面的算法每删除一个度为 0 的顶点操作一次（最多 n 次），或每删除一个度为 1 的顶点（同时删一条边）操作一次（最多 m 次）。 这两种操作的总数不会超过 m+n 。由于 m<n ，所以算法复杂度为 O(n)
全部评论 (0)
还没有任何评论哟~