Detecting cycle in an undirected graphs using DFS

Detecting cycle in an undirected graph using depth-first search (DFS) algorithm

Cycle in undirected graphs can be detected easily using a depth-first search traversal. While doing a depth-first search traversal, we keep track of the visited node’s parent along with the list of visited nodes. During the traversal, if an adjacent node is found visited that is not the parent of the source node, then we have found a cycle in the current path.


Algorithm : DFS Detect Cycle In An Undirected Graph (Node source_node)
1.    Mark the source_node as visited.
2.    For all the adjacent nodes to the source_node do
3.        If the adjacent_node has not been visited
4.            Set parent [adjacent_node] = source_node.
5.            DFS Detect Cycle In An Undirected Graph (adjacent_node)
6.        Else If the parent[source_node] != adjacent_node
7.            Cycle found. Return.


Example of detecting cycles in an undirected graph using depth-first search traversal DFS_Cycle_In_Undirected_Graph

Time complexity of detecting cycles in an undirected graph using depth-first search : O(E+V). This algorithm uses a depth-first search traversal for traversing all the nodes in the graph. As the graph is stored in an adjacency list, the neighbors of a vertex on the outgoing edge are explored successively/linearly. As each vertex is explored only once, all the vertices are explored in O(V) time. The total number of edges (maintained in the adjacency list) are 2*E for an undirected graph. Thus the time complexity is O(2E+V) for a directed graph.


C++14 Detecting cycle in an undirected graph using Depth First Search (DFS) algorithm

#include<iostream>
#include<list>
#include<vector>
#include<stack>

using namespace std;

class Graph {

    private:

        int nodes;
        list<int> *adjlist;
        vector<bool> visited;

        // parent stores the parent node of the visited node, this is used
        // for finding cycle in an un-directed graph.
        vector<int> parent;

        bool cycle_present;

    public:

        Graph() {
        }

        Graph (int arg_nodes) {

            this->nodes = arg_nodes;
            adjlist = new list<int> [nodes];
            visited.resize(nodes, false);
            parent.resize(nodes, -1);
            cycle_present = false;
        }

        ~Graph () {
            delete [] adjlist;
        }

        void AddEdge (int src, int dst, bool bidirectional) {

            adjlist[src].push_back(dst);

            if (bidirectional)
                adjlist[dst].push_back(src);
        }

        // Function detects cycle in an undirected graph
        //
        void DFS_DetectCycleInUndirectedGraph (int src) {

            visited[src] = true;

            for (auto& adj_node : adjlist[src]) {

                if (!visited[adj_node]) {

                    parent[adj_node] = src;
                    DFS_DetectCycleInUndirectedGraph (adj_node);

                } else if (parent[src] != adj_node) {

                   cycle_present = true;
                   return;

                }
            }
         }

        bool IsCyclePresent() {
            return cycle_present;
        }
};

int main()
{
    Graph g1_undirected (7);

    /* Undirected graph 1
               0
              / \
             1   2
                / \
               3   4
                  / \
                 5   6 */
    g1_undirected.AddEdge(0, 1, true);
    g1_undirected.AddEdge(0, 2, true);
    g1_undirected.AddEdge(2, 3, true);
    g1_undirected.AddEdge(2, 4, true);
    g1_undirected.AddEdge(4, 5, true);
    g1_undirected.AddEdge(4, 6, true);

    g1_undirected.DFS_DetectCycleInUndirectedGraph(0);

    if (g1_undirected.IsCyclePresent()) {
       cout << "Cycle found in the undirected graph g1" << endl;
    } else {
       cout << "Cycle not found in the undirected graph g1" << endl;
    }

    Graph g2_undirected (4);

    /* Undirected graph 2     
               0
              / \
             1   2
              \ / 
               3      */
    g2_undirected.AddEdge(0, 1, true);
    g2_undirected.AddEdge(0, 2, true);
    g2_undirected.AddEdge(1, 3, true);
    g2_undirected.AddEdge(2, 3, true);

    g2_undirected.DFS_DetectCycleInUndirectedGraph(0);

    if (g2_undirected.IsCyclePresent()) {
       cout << "Cycle found in the undirected graph g2" << endl;
    } else {
       cout << "Cycle not found in the undirected graph g2" << endl;
    }

    return 0;
}

Output showing detecting of cycles in an undirected graph using depth-first search traversal

Cycle not found in the undirected graph g1
Cycle found in the undirected graph g2

Copyright © 2019-2020, Algotree.org.
All rights reserved.