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

Raleigh

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

Mozellemozes

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

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. – Hygrometry

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

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. – Iodide

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. – Serviceable

@Serviceable Only in a directed graph. – Pomology

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

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

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? – Jurisdiction

@Jurisdiction 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" – Pomology

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

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

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

Personalize

but still well answered and explained!! – Angellaangelle

The if statement at line 2 is always false( check the if statement at line 7 ) – Evieevil

for a directed graph, run topological search. if it succeeded: no cycles. otherwise: cycles exist. – Obregon

To say it explicitly: dfs is enough for undirected graph: "An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge)" – Traject

@J.F.Sebastian Another way of putting it is that in any graph, undirected or directed, a back edge exists iff a cycle exists. It's just that in an undirected graph, all edges are either "tree" edges or "back" edges, whereas in a directed graph edges can also be "forward" or "cross" edges, in the language of CLRS. So a simple DFS suffices for an undirected graph, but not for a directed graph (where we need to additionally keep track of the so-called "gray" nodes, or at least their discovery/finish times). – Michelinemichell

The objection noted here is eliminated when node of degree 1 are eliminated from the list of searchable nodes. That is, (a) would never be considered as a possible candidate for being a member of a cycle because by having degree = 1 it is impossible for it to be such. – Florencia

"again and conclude there is a cycle -- when there isn't." - . What do you mean? b->d->c->b is a cycle . Maybe you assumed its a directed graph, whereas the original question was about undirected graph .. And everybody in the crowd missed that !!! – Haemo

"and conclude there is a cycle -- when there isn't." - What? There obviously is a cycle. – Tody

Answer 3

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.

Vasilek

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? – Wide

Parallel edges themselves make a cycle. – Vasilek

Yes. Totally missed that somehow. Thanks! – Wide

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

Answer 4

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.

Lytton

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

Thanks. Indeed that was the observation. – Lytton

Answer 5

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

Brockman

Answer 6

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.

Cooperstein

Answer 7

A simple DFS does the work of checking if the given undirected graph has a cycle or not.

Here's the C++ code to the same.

The idea used in the above code is:

If a node which is already discovered/visited is found again and is not the parent node , then we have a cycle.

This can also be explained as below(mentioned by @Rafał Dowgird

If an unexplored edge leads to a node visited before, then the graph contains a cycle.

Hesperides

Answer 8

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

Nerveless

Answer 9

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

Communalize

Answer 10

Here is the code I've written in C based on DFS to find out whether a given graph is connected/cyclic or not. with some sample output at the end. Hope it'll be helpful :)

#include<stdio.h>
#include<stdlib.h>

/****Global Variables****/
int A[20][20],visited[20],v=0,count=0,n;
int seq[20],s=0,connected=1,acyclic=1;

/****DFS Function Declaration****/
void DFS();

/****DFSearch Function Declaration****/
void DFSearch(int cur);

/****Main Function****/
int main() 
   {    
    int i,j;

    printf("\nEnter no of Vertices: ");
    scanf("%d",&n);

    printf("\nEnter the Adjacency Matrix(1/0):\n");
    for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
        scanf("%d",&A[i][j]);

    printf("\nThe Depth First Search Traversal:\n");

    DFS();

    for(i=1;i<=n;i++)
        printf("%c,%d\t",'a'+seq[i]-1,i);

    if(connected && acyclic)    printf("\n\nIt is a Connected, Acyclic Graph!");
    if(!connected && acyclic)   printf("\n\nIt is a Not-Connected, Acyclic Graph!");
    if(connected && !acyclic)   printf("\n\nGraph is a Connected, Cyclic Graph!");
    if(!connected && !acyclic)  printf("\n\nIt is a Not-Connected, Cyclic Graph!");

    printf("\n\n");
    return 0;
   }

/****DFS Function Definition****/
void DFS()
    { 
    int i;
    for(i=1;i<=n;i++)
        if(!visited[i])
          {
        if(i>1) connected=0;
        DFSearch(i);    
              } 
    }

/****DFSearch Function Definition****/
void DFSearch(int cur) 
    {
    int i,j;
    visited[cur]=++count;

        seq[count]=cur; 
        for(i=1;i<count-1;i++)
                if(A[cur][seq[i]]) 
                   acyclic=0;

    for(i=1;i<=n;i++)
        if(A[cur][i] && !visited[i])
           DFSearch(i);

    }

---

/*Sample Output:

majid@majid-K53SC:~/Desktop$ gcc BFS.c

majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 10

Enter the Adjacency Matrix(1/0):

0 0 1 1 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 0 0 0 

The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10    

It is a Not-Connected, Cyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 4

Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1

The Depth First Search Traversal:
a,1 c,2 b,3 d,4 

It is a Connected, Acyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 5

Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0 
0 0 1 0 0

The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5 

It is a Not-Connected, Acyclic Graph!

*/

Mischievous

Answer 11

An undirected graph is acyclic (i.e., a forest) if a DFS yields no back edges. Since back edges are those edges (u, v) connecting a vertex u to an ancestor v in a depth-first tree, so no back edges means there are only tree edges, so there is no cycle. So we can simply run DFS. If find a back edge, there is a cycle. The complexity is O(V) instead of O(E + V). Since if there is a back edge, it must be found before seeing |V| distinct edges. This is because in a acyclic (undirected) forest, |E| ≤ |V| + 1.

Whitehot

Answer 12

As others have mentioned... A depth first search will solve it. In general depth first search takes O(V + E) but in this case you know the graph has at most O(V) edges. So you can simply run a DFS and once you see a new edge increase a counter. When the counter has reached V you don't have to continue because the graph has certainly a cycle. Obviously this takes O(v).

Beeline

Answer 13

I believe using DFS correctly also depends on how are you going to represent your graph in the code. For example suppose you are using adjacent lists to keep track of neighbor nodes and your graph has 2 vertices and only one edge: V={1,2} and E={(1,2)}. In this case starting from vertex 1, DFS will mark it as VISITED and will put 2 in the queue. After that it will pop vertex 2 and since 1 is adjacent to 2, and 1 is VISITED, DFS will conclude that there is a cycle (which is wrong). In other words in Undirected graphs (1,2) and (2,1) are the same edge and you should code in a way for DFS not to consider them different edges. Keeping parent node for each visited node will help to handle this situation.

Cyprio

Answer 14

I started studying graphs recently. I wrote a piece of code in java that could determine if a graph has cycles. I used DFT to find cycles in the graph. Instead of recurssion I used a stack to traverse the graph.

At a high level DFT using a stack is done in the following steps

1. Visit a Node
2. If the node is not in the visited list add it to the list and push it to the top of the stack
3. Mark the node at the top of the stack as the current node.
4. Repeat the above for each adjacent node of the current node
5. If all the nodes have been visited pop the current node off the stack

I performed a DFT from each node of the Graph and during the traversal if I encountered a vertex that I visited earlier, I checked if the vertex had a stack depth greater than one. I also checked if a node had an edge to itself and if there were multiple edges between nodes. The stack version that I originally wrote was not very elegant. I read the pseudo code of how it could be done using recursion and it was neat. Here is a java implementation. The LinkedList array represents a graph. with each node and it's adjacent vertices denoted by the index of the array and each item respectively

class GFG {
Boolean isCyclic(int V, LinkedList<Integer>[] alist) {
    List<Integer> visited = new ArrayList<Integer>();
    for (int i = 0; i < V; i++) {
        if (!visited.contains(i)) {
            if (isCyclic(i, alist, visited, -1))
                return true;
        }
    }
    return false;
}

Boolean isCyclic(int vertex, LinkedList<Integer>[] alist, List<Integer> visited, int parent) {
    visited.add(vertex);
    for (Iterator<Integer> iterator = alist[vertex].iterator(); iterator.hasNext();) {
        int element = iterator.next();
        if (!visited.contains(element)) {
            if (isCyclic(element, alist, visited, vertex))
                return true;
        } else if (element != parent)
            return true;
    }
    return false;
}

}

Claybourne

Answer 15

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.

Drizzle

Answer 16

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

Giantism

Answer 17

An undirected graph without cycle has |E| < |V|-1.

public boolean hasCycle(Graph g) {

   int totalEdges = 0;
   for(Vertex v : g.getVertices()) {
     totalEdges += v.getNeighbors().size();
   }
   return totalEdges/2 > g.getVertices().size - 1;

}

Kelda

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

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

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 – Adjunction