Detecting cycle in directed graphs using Depth-First-Search (DFS)

  • Cycle in directed graphs can be detected easily using a depth-first search traversal.
  • Idea
    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 of the current path, if we come to a node that was already marked visited then we have found a cycle.

Algorithm : Detect_Cycle ( 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, then
5.            Cycle found. Return.
6.        If the adjacent node has not been visited, then
7.            Detect_Cycle ( adjacent_node )
8.    Now that we are backtracking unmark the source_node in in_path as it might be revisited.

Example

DFS_Cycle_In_Directed_Graph

Time complexity : 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.

Program for detecting cycle in a directed graph 

from collections import defaultdict

class Graph:

    def __init__(self, nodes : int):
        # The default dictionary would create an empty list as a default (value) 
        # for the nonexistent keys.
        self.adjlist = defaultdict(list)
        self.nodes = nodes
        self.visited = [False] * nodes
        # inpath stores the visited nodes in the traversal path
        # for finding cycle in a directed graph.
        self.inpath = [False] * nodes
        self.cycle_present = False

    def AddEdge (self, src : int, dst : int, bidirectional : bool):

        self.adjlist[src].append(dst)

        if bidirectional: # Check if the edge is undirected (bidirectional)
            self.adjlist[dst].append(src)

    # Function detects cycle in a directed graph using
    # DFS technique at its core.
    def DetectCycle (self, src : int):

        self.visited[src] = True

        # Set the flag for the vertex visited in traversal path
        self.inpath[src] = True

        for adj_node in self.adjlist[src]:

            if self.inpath[adj_node] == True:
                self.cycle_present = True
                return
            elif self.visited[adj_node] == False:
                self.DetectCycle (adj_node)

        # Before we backtrack unset the flag for the src vertex as it
        # might be in the next traversal path
        self.inpath[src] = False

    # Mark nodes unvisited for the next traversal
    def MarkUnvisited (self):
        self.visited = [False] * nodes

    def CyclePresent (self):
        return self.cycle_present

def main():

    nodes = 7
    g1_directed = Graph(nodes)

    #  Graph 1
    #  6----------- 
    #  ^          |
    #  |          |
    #  4<------5<--  
    #  ^       ^
    #  |       |
    #  1<------3
    #  ^       ^
    #  |       |
    #  0 ----->2

    # 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.DetectCycle(0)

    if g1_directed.CyclePresent() == True:
       print("Cycle found in the directed graph g1")
    else:
       print("Cycle not found in the directed graph g1")

    # Graph 2
    # 4-
    # ^ \
    # |  \
    # 3   \
    # ^    \
    # |     \
    # 2      \
    # ^       \
    # |        \
    # 0--->1<---

    nodes = 5
    g2_directed = Graph(nodes)

    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.DetectCycle(0)

    if g2_directed.CyclePresent() == True:
        print("Cycle found in the directed graph g2")
    else:
        print("Cycle not found in the directed graph g2")

if __name__ == "__main__":
    main()

Output

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

#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
        // using DFS technique at its core
        void DetectCycle (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]) {
                    DetectCycle (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 CyclePresent() {
            return cycle_present;
        }
};

int main()
{
    Graph g1_directed (7);

    /*
    Graph 1
    6----------- 
    ^          |
    |          |
    4<------5<--  
    ^       ^
    |       |
    1<------3
    ^       ^
    |       |
    0 ----->2 */

    // 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.DetectCycle(0);

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

    Graph g2_directed (5);
    /*
    Graph 2
    4-
    ^ \
    |  \
    3   \
    ^    \
    |     \
    2      \
    ^       \
    |        \
    0--->1<---   
    */
    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.DetectCycle(0);

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

Output

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

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Graph {

    private int nodes;
    private List<List<Integer>> adjlist;
    private boolean visited[];

    // inpath stores the visited nodes in the traversal path before backtracking
    // for finding cycle in a directed graph.
    private boolean inpath[];

    boolean cycle_present;

    Graph (int arg_nodes) {

        nodes = arg_nodes;

        adjlist = new ArrayList<> (nodes);
        for(int i=0; i<nodes; i++) {
            adjlist.add(new ArrayList<>());
        }

        visited = new boolean[nodes];
        inpath  = new boolean[nodes];

        cycle_present = false;
    }   

    public void AddEdge (int src, int dst, boolean bidirectional) {

        adjlist.get(src).add(dst);

        if (bidirectional)
            adjlist.get(dst).add(src);
    }   

    // Function detects cycle in a directed graph
    // using DFS technique at its core.
    public void DetectCycle (int src) {

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

        for (int adj_node : adjlist.get(src)) {

            if (inpath[adj_node]) {
                cycle_present = true;
                return;
            } else if (!visited[adj_node]) {
                DetectCycle (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
    public void MarkUnvisited () {
        Arrays.fill(visited, false);
    }   

    public boolean CyclePresent() {
        return cycle_present;
    }   

    public static void main (String[] args) {
    
        Graph g1_directed = new Graph(7);
        /*
        Graph 1
        6----------- 
        ^          |
        |          |
        4<------5<--  
        ^       ^
        |       |
        1<------3
        ^       ^
        |       |
        0 ----->2 */

        // 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.DetectCycle(0);
    
        if (g1_directed.CyclePresent()) {
            System.out.println("Cycle found in the directed graph g1");
        } else {
            System.out.println("Cycle not found in the directed graph g1");
        }
    
        Graph g2_directed = new Graph(5);
        
        /*
        Graph 2
        4-
        ^ \
        |  \
        3   \
        ^    \
        |     \
        2      \
        ^       \
        |        \
        0--->1<---   
        */
        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.DetectCycle(0);
    
        if (g2_directed.CyclePresent()) {
           System.out.println("Cycle found in the directed graph g2");
        } else {
           System.out.println("Cycle not found in the directed graph g2");
        }
    }   
}

Output

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

Copyright (c) 2019-2024, Algotree.org.
All rights reserved.