Cycles in an Undirected Graph

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:

Actually, depth first (or indeed breadth first) search isn't quite enough. You need a sightly more complex algorithm.

For instance, suppose there is graph with nodes {a,b,c,d} and edges {(a,b),(b,c),(b,d),(d,c)} where an edge (x,y) is an edge from x to y. (looks something like this, with all edges directed downwards.)

    (a)
     |
     |
    (b)
    / \ 
  (d)  |
   |   |
    \ /
    (c)

Then doing depth first search may visit node (a), then (b), then (c), then backtrack to (b), then visit (d), and finally visit (c) again and conclude there is a cycle -- when there isn't. A similar thing happens with breadth first.

What you need to do is keep track of which nodes your in the middle of visiting. In the example above, when the algorithm reaches (d) it has finished visiting (c) but not (a) or (b). So revisiting a finished node is fine, but visiting an unfinished node means you have a cycle. The usual way to do this is colour each node white(not yet visited), grey(visiting descendants) or black(finished visiting).

here is some pseudo code!

define visit(node n):
  if n.colour == grey: //if we're still visiting this node or its descendants
    throw exception("Cycle found")

  n.colour = grey //to indicate this node is being visited
  for node child in n.children():
    if child.colour == white: //if the child is unexplored
      visit(child)

  n.colour = black //to show we're done visiting this node
  return

then running visit(root_node) will throw an exception if and only if there is a cycle (initially all nodes should be white).

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.