Cycles in an Undirected Graph

Question

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

Solution 1

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.

Solution 2

A connected, undirected graph G that has no cycles is a tree! Any tree has exactly n − 1 edges, so we can simply traverse the edge list of the graph and count the edges. If we count n − 1 edges then we return “yes” but if we reach the nth edge then we return “no”. This takes O (n) time because we look at at most n edges.

But if the graph is not connected,then we would have to use DFS. We can traverse through the edges and if any unexplored edges lead to the visited vertex then it has cycle.

Solution 3

You can solve it using DFS. Time complexity: O(n)

The essence of the algorithm is that if a connected component/graph does NOT contain a CYCLE, it will always be a TREE.See here for proof

Let us assume the graph has no cycle, i.e. it is a tree. And if we look at a tree, each edge from a node:

1.either reaches to its one and only parent, which is one level above it.

2.or reaches to its children, which are one level below it.

So if a node has any other edge which is not among the two described above, it will obviously connect the node to one of its ancestors other than its parent. This will form a CYCLE.

Now that the facts are clear, all you have to do is run a DFS for the graph (considering your graph is connected, otherwise do it for all unvisited vertices), and IF you find a neighbor of the node which is VISITED and NOT its parent, then my friend there is a CYCLE in the graph, and you're DONE.

You can keep track of parent by simply passing the parent as parameter when you do DFS for its neighbors. And Since you only need to examine n edges at the most, the time complexity will be O(n).

Hope the answer helped.

Solution 4

By the way, if you happen to know that it is connected, then simply it is a tree (thus no cycles) if and only if |E|=|V|-1. Of course that's not a small amount of information :)

Solution 5

The answer is, really, breadth first search (or depth first search, it doesn't really matter). The details lie in the analysis.

Now, how fast is the algorithm?

First, imagine the graph has no cycles. The number of edges is then O(V), the graph is a forest, goal reached.

Now, imagine the graph has cycles, and your searching algorithm will finish and report success in the first of them. The graph is undirected, and therefore, the when the algorithm inspects an edge, there are only two possibilities: Either it has visited the other end of the edge, or it has and then, this edge closes a circle. And once it sees the other vertex of the edge, that vertex is "inspected", so there are only O(V) of these operations. The second case will be reached only once throughout the run of the algorithm.

View more solutions

Comments

[Eran Kampf]

right! I remembered it was something simple... Thanks a lot :)

[oz10]

and if you go the breadth first search route, then an unexplored edge leading to a node "discovered" before, then the graph contains a cycle. BTW, IIRC the runtime of graph algorithms is usually described in terms of V and E.

[Dineshkumar]

Hmmm...this could devolve into an O(n^2) algorithm if you aren't careful, no? If you check for a node visited before by keeping all of the nodes in a linked list (new nodes to the end) then you'll have to scan your node list (the scan is O(n) in itself) on each check. Ergo - O(n^2).

[rahulmehta95]

This condition is also known as a back edge. After running DFS, if the resulting DFS tree contains any back edges (an edge pointing to an ancestor in the tree), you know there's a cycle. This also works for a directed graph.

[Joshua Goldberg]

This doesn't seem right. First, did you mean <=? (A connected straight line 1-2-3-4-...-10 will always have |E|=|V|-1. And then, unless you restrict to fully connected, you can add any number of subgraphs to grow |E| slower than |V| and trick this test into missing a cycle. (I.e., If I add an edge A-B, I add 1 to |E| and 2 to |V|.)

[Joshua Goldberg]

Forgive me for noting that your name is amusingly eponymous for this question!

[Pikachu]

In the the graph: A-B, B-C, A-C, D, E we have |V| = 5 and |E| = 3, so your condition holds 3 < 5 - 1, even tough it has the cycle A-B-C-A

[Sky]

This answer is not correct. Doing a simple depth-first-search is not good enough to find a cycle. It is possible to visit a node multiple times in a DFS without a cycle existing.

[leo7r]

@Sky Only in a directed graph.

[Sky]

The question is about undirected graph but your answer only works in directed graph.

[leo7r]

@Sky It is the other way around - it only works in an undirected graph.

[Tomasz Gandor]

This is a nice observation with this tree. It means if you just want a yes/no answer, you can count the number of edges in every connected component, and compare it to (n-1), n = count of nodes in the component (or whole connected graph).

[mb1994]

Thanks. Indeed that was the observation.

[thebenman]

But what if the the graph has parallel edges? In that case the count of the edges would be greater than n-1 and still not have a cycle. Am I missing something?

[Ashish Pani]

Parallel edges themselves make a cycle.

[thebenman]

Yes. Totally missed that somehow. Thanks!

[sagittarian]

The question didn't specify that the graph is known to be connected, so just counting the edges won't work.

[VHS]

But DFS takes O(|V|) + O(|E|) time while the problem is asking for O(|V|) time complexity solution. How is this a correct answer?

[leo7r]

@VHS It is in the answer: "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"

[VHS]

@RafałDowgird, yeah, I figured it out on my own eventually.

[Anthony O]

In an undirected graph if there are two paths to a vertex then there is a cycle so this is correct. In a directed graph you must demonstrate a back edge (an edge from child to ancestor in a connected component).