Cycles in an Undirected Graph

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.

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).

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.

DFS APPROACH WITH A CONDITION(parent != next node) Let's see the code and then understand what's going on :

bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
    // Mark the current node as visited 
    visited[v] = true; 

    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // If an adjacent is not visited, then recur for that adjacent 
        if (!visited[*i]) 
        { 
           if (isCyclicUtil(*i, visited, v)) 
              return true; 
        } 

        // If an adjacent is visited and not parent of current vertex, 
        // then there is a cycle. 
        else if (*i != parent) 
           return true; 
    } 
    return false; 
} 

The above code explains itself but I will try to explain one condition i.e *i != parent Here if suppose graph is

1--2

Then when we are at 1 and goes to 2, the parent for 2 becomes 1 and when we go back to 1 as 1 is in adj matrix of 2 then since next vertex 1 is also the parent of 2 Therefore cycle will not be detected for the immediate parent in this DFS approach. Hence Code works fine

I believe that the assumption that the graph is connected can be handful. thus, you can use the proof shown above, that the running time is O(|V|). if not, then |E|>|V|. reminder: the running time of DFS is O(|V|+|E|).

Here is a simple implementation in C++ of algorithm that checks if a graph has cycle(s) in O(n) time (n is number of vertexes in the Graph). I do not show here the Graph data structure implementation (to keep answer short). The algorithms expects the class Graph to have public methods, vector<int> getAdj(int v) that returns vertexes adjacent to the v and int getV() that returns total number of vertexes. Additionally, the algorithms assumes the vertexes of the Graph are numbered from 0 to n - 1.

class CheckCycleUndirectedGraph
{
private:
    bool cyclic;
    vector<bool> visited;

    void depthFirstSearch(const Graph& g, int v, int u) {
        visited[v] = true;
        for (auto w : g.getAdj(v)) {
            if (!visited[w]) {
                depthFirstSearch(g, w, v);
            }
            else if (w != u) {
                cyclic = true;
                return;
            }
        }
    }

public:
    CheckCycleUndirectedGraph(const Graph& g) : cyclic(false) {
        visited = vector<bool>(g.getV(), false);
        for (int v = 0; v < g.getV(); v++) {
            if (!visited[v]){
                depthFirstSearch(g, v, v);
                if(cyclic)
                  break;
            }
        }
    }

    bool containsCycle() const {
        return cyclic;
    }
};

Keep in mind that Graph may consist of several not connected components and there may be cycles inside of the components. The shown algorithms detects cycles in such graphs as well.

You can use boost graph library and cyclic dependencies. It has the solution for finding cycles with back_edge function.