Detecting cycle in directed graphs using DFS

Detecting cycle in directed graphs using depth-first search (DFS) algorithm

Cycle in directed graphs can be detected easily using a depth-first search traversal. While doing a depth-first search traversal, we keep track of the nodes visited in the current traversal path in addition to the list of all the visited nodes. During the traversal if we visit a node that was already in the current path of the traversal a cycle is found.


Algorithm : DFS Detect Cycle In A Directed Graph (Node source_node)
1.    Mark the source_node as visited.
2.    Mark the source_node as in_path node.
3.    For all the adjacent nodes to the source_node do
4.        If the adjacent node has been marked as in_path node.
5.            Cycle found. Return.
6.        If the adjacent node has not been visited
7.            DFS Detect Cycle In A Directed Graph (adjacent_node)
8.    Now that we are back-tracking unmark the source_node in in_path as it might be revisited.


Example of detecting cycles in a directed graph using depth-first search traversal

DFS_Cycle_In_Directed_Graph

Time complexity of detecting cycles in a directed 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 E for a directed graph. Thus the time complexity is O(E+V) for a directed graph.


C++14 Detect cycle in a directed graph using depth-first search (DFS)

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

using namespace std;

class Graph {

    private:

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

        // inpath stores the visited nodes in the traversal path before backtracking
        // for finding cycle in a directed graph.
        vector<bool> inpath;

        bool cycle_present;

    public:

        Graph() {
        }

        Graph (int arg_nodes) {

            this->nodes = arg_nodes;
            adjlist = new list<int> [nodes];
            visited.resize(nodes, false);
            inpath.resize(nodes, false);
            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 a directed graph
        //
        void DFS_DetectCycleInDirectedGraph (int src) {

            visited[src] = true;
            // Set the flag for the vertex visited in traversal path
            //
            inpath[src] = true;

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

                if (inpath[adj_node]) {
                    cycle_present = true;
                    return;
                } else if (!visited[adj_node]) {
                    DFS_DetectCycleInDirectedGraph (adj_node);
                }
            }
            // Before we backtrack unset the flag for the src vertex as it will
            // not be in the next traversal path
            inpath[src] = false;
        }

        // Mark nodes unvisited for the next traversal
        void MarkUnvisited () {
            fill(visited.begin(), visited.end(), false);
        }

        bool IsCyclePresent() {
            return cycle_present;
        }
};

int main()
{
    Graph g1_directed (7);

    // Add edges to the directed graph
    g1_directed.AddEdge(0, 1, false);
    g1_directed.AddEdge(0, 2, false);
    g1_directed.AddEdge(1, 4, false);
    g1_directed.AddEdge(2, 3, false);
    g1_directed.AddEdge(3, 1, false);
    g1_directed.AddEdge(3, 5, false);
    g1_directed.AddEdge(4, 6, false);
    g1_directed.AddEdge(5, 4, false);
    g1_directed.AddEdge(6, 5, false);

    g1_directed.DFS_DetectCycleInDirectedGraph(0);

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

    Graph g2_directed (5);

    g2_directed.AddEdge(0, 1, false);
    g2_directed.AddEdge(0, 2, false);
    g2_directed.AddEdge(2, 3, false);
    g2_directed.AddEdge(3, 4, false);
    g2_directed.AddEdge(4, 1, false);

    g2_directed.DFS_DetectCycleInDirectedGraph(0);

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

    return 0;
}

Output showing detection of cycles in an directed graph using depth-first search traversal

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

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