无向图中的循环 [英] Cycles in an Undirected Graph

问题描述

给定一个具有 n 个顶点 (|V| = n)，你如何在O(n)中找到它是否包含一个循环?

Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?

推荐答案

我认为深度优先搜索可以解决这个问题.如果一条未探索的边导致之前访问过的节点，则该图包含一个循环.这个条件也使它成为 O(n)，因为您可以探索最大 n 条边，而无需将其设置为 true 或留下任何未探索的边.

I think that depth first search solves it. If an unexplored edge leads to a node visited before, then the graph contains a cycle. This condition also makes it O(n), since you can explore maximum n edges without setting it to true or being left with no unexplored edges.

这篇关于无向图中的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！