Algotree > Algorithms > Tree & Graph Traversal > Depth First Search ( DFS ) > All paths in a directed acyclic graph

All paths in a directed acyclic graph

Finding all the paths in a directed acyclic graph from a source node to a destination node

All paths in a directed acyclic graph can be found using Depth-First-Search traversal.

Start from the source node and use DFS to reach the destination while storing the nodes along the path. Once the destination node is found, the path is stored.
Note
While finding all the paths, the DFS traversal techinique used here does not mark the nodes as visited while searching for the destination as a node in between can be revisited if it is present in a different path.

Algorithm Find_All_Paths (Graph g)
1. Push the source node ‘src’ in the path.
2. DFS (src, dest, g)

DFS (Source src, Destination dest, Graph g)
1.  If (src == dest) then
2.      A path has been found. Push the path in the list of all_the_paths.
3.  Else
4.     For every adjacent node ‘adj_node’ that is adjacent to src do
5.        Push ‘adj_node’ in the path.
6.        DFS (adj_node, dest, g)
7.        Pop ‘adj_node’ from the path. This is essentially a backtracing mechanism to find a different path from the source (‘src’) node.

Consider the below graph G2. The DFS traversal starts from the source 0 before the destination 3 is found. During the traversal, nodes 1 and 2 are visited before the desitnation 3 is reached. Since no nodes are marked visited, a different path is found that may pass through nodes 1 or 2 before reaching the desination 3.
Thus the DFS finds out the below paths..
[ 0 -> 1 -> 2 -> 3 ], path found.
Popout node 3 & 2. Next node ‘3’ adjacent to node 1 is visited.
[ 0 -> 1 -> 3 ], path found.
Popout node 3 & 1. Next node ‘2’ adjacent to node 0 is visited.
[ 0 -> 2 -> 3 ], path found.

Example

All_Paths_In_A_Graph

Implementation of finding all paths in a graph.

import copy

class Graph :

    def __init__ (self):
        self.allpaths = []

    def FindAllPaths (self, graph, src, dst):
        # Clear previously stored paths
        path = []
        path.append(src)
        print("Source : " + str(src) + " Destination : " +  str(dst))

        # Use depth first search (with backtracking) to find all the paths in the graph
        self.DFS (graph, src, dst, path)

        # Print all paths
        self.Print ()

    def Print (self):
        # print (self.allpaths)
        for path in self.allpaths:
            print("Path : " + str(path))
        self.allpaths.clear()

    # This function uses DFS at its core to find all the paths in a graph
    def DFS (self, graph, src, dst, path):
        if (src == dst):
            self.allpaths.append(copy.deepcopy(path))
        else:
            for adjnode in graph[src]:
                path.append(adjnode)
                self.DFS (graph, adjnode, dst, path)
                path.pop()

def main():

    g1 = { 0 : [1, 2], 1 : [3], 2 : [3], 3 :[] } # 0 -> (1,2); 1 -> (3); 2 -> (3); 3 -> (None)
    #    2 ---> 3
    #    ^      ^   
    #    |      |        
    #    0 ---> 1
    #
    g2 = { 0 : [1, 2], 1 : [2, 3], 2 : [3], 3 : [] } # 0 -> (1,2); 1 -> (2,3); 2 -> (3); 3 -> (None)
    g3 = { 0 : [4, 3, 1], 1 : [3, 2, 4], 2 : [3], 3 : [4], 4 : [] }

    g = Graph()

    print("All paths in graph G1")
    g.FindAllPaths(g1, 0, 3)

    print("\nAll paths in graph G2")
    g.FindAllPaths(g2, 0, 3)

    print( "\nAll paths in graph G3")
    g.FindAllPaths(g3, 0, 4)

if __name__ == "__main__":
    main()

Output

All paths in graph G1
Source : 0 Destination : 3
Path : [0, 1, 3]
Path : [0, 2, 3]

All paths in graph G2
Source : 0 Destination : 3
Path : [0, 1, 2, 3]
Path : [0, 1, 3]
Path : [0, 2, 3]

All paths in graph G3
Source : 0 Destination : 4
Path : [0, 4]
Path : [0, 3, 4]
Path : [0, 1, 3, 4]
Path : [0, 1, 2, 3, 4]
Path : [0, 1, 4]

#include<iostream>
#include<vector>
using namespace std;

class Graph {

private :
    vector<vector<int>> allpaths;

public:
    void FindAllPaths (vector<vector<int>>& graph, int src, int dst) {
        // Clear previously stored paths if any
        allpaths.clear();
        vector<int> path;

        // As the path begins with source, push the source node into the path
        path.push_back(src);
        cout << "Source : " << src << " Destination : " << dst << endl;
        DFS (graph, src, dst, path);
        // Print all paths in the graph
        Print ();
    }

    void Print() {
        // Print all the paths
        for (const auto& path : allpaths) {
            cout << "Path : ";
            for (const auto& node : path)
                cout << node << " ";
            cout << endl;
        }
    }

    void DFS (vector<vector<int>>& graph, int src, int dst, vector<int>& path) {

        if (src == dst) {
            allpaths.push_back(path);
        } else {
            for (const auto& adjnode : graph[src]) {
                path.push_back(adjnode);
                DFS (graph, adjnode, dst, path);
                path.pop_back();
            }
        }
    }
};

int main() {

    vector<vector<int>> g1 = {{1,2}, {3}, {3}, {}}; // 0 -> (1,2); 1 -> (3); 2 -> (3); 3 -> (None)
    /*  2 ---> 3
        ^      ^   
        |      |        
        0 ---> 1
    */
    vector<vector<int>> g2 = {{1,2}, {2,3}, {3}, {}}; // 0 -> (1,2); 1 -> (2,3); 2 -> (3); 3 -> (None)
    vector<vector<int>> g3 = {{4,3,1}, {3,2,4}, {3}, {4}, {}};

    Graph g;
    vector<vector<int>> allpaths;

    cout << "All paths in graph G1" << endl;
    g.FindAllPaths(g1, 0, 3);

    cout << "\nAll paths in graph G2" << endl;
    g.FindAllPaths(g2, 0, 3);

    cout << "\nAll paths in graph G3" << endl;
    g.FindAllPaths(g3, 0, 4);

    return 0;
}

Output

All paths in graph G1
Source : 0 Destination : 3
Path : 0 1 3 
Path : 0 2 3 

All paths in graph G2
Source : 0 Destination : 3
Path : 0 1 2 3 
Path : 0 1 3 
Path : 0 2 3 

All paths in graph G3
Source : 0 Destination : 4
Path : 0 4 
Path : 0 3 4 
Path : 0 1 3 4 
Path : 0 1 2 3 4 
Path : 0 1 4

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

class Graph {

    private List<Integer> path;

    public void FindAllPaths (List<List<Integer>> graph, int src, int dst) {

        // Clear previously stored paths
        path = new ArrayList<Integer>();
        path.clear();

        System.out.print("Source : " + src + " Destination : " + dst);

        path.add(src);

        DFS (graph, src, dst, path);
    }

    public void DFS (List<List<Integer>> graph, int src , int dst, List<Integer> path) {

        if (src == dst) {
            System.out.print("\nPath : " );
            for (Integer node : path)
                 System.out.print(node + " ");
        } else {
            for (Integer adjnode : graph.get(src)) {
                path.add(adjnode);
                DFS (graph, adjnode, dst, path);
                path.remove(path.size()-1);
            }
        }
    }

    public static void ClearConnections(List<Integer> node1, List<Integer> node2, List<Integer> node3,
                                 List<Integer> node4, List<Integer> node5) {
        node1.clear();
        node2.clear();
        node3.clear();
        node4.clear();
        node5.clear();
    }

    public static void main (String[] args) {

        Graph obj = new Graph();
        List<Integer> from_node_0, from_node_1, from_node_2, from_node_3, from_node_4;

        from_node_0 = new ArrayList<Integer>();
        from_node_1 = new ArrayList<Integer>();
        from_node_2 = new ArrayList<Integer>();
        from_node_3 = new ArrayList<Integer>();
        from_node_4 = new ArrayList<Integer>();

        List<List<Integer>> graph1 = new ArrayList<List<Integer>>();
        // Graph 1

        /*  2 ---> 3
            ^      ^   
            |      |        
            0 ---> 1 */

        //  {{1,2}, {3}, {3}, {}}; // 0 -> (1,2); 1 -> (3); 2 -> (3); 3 -> (None)

        from_node_0.add(1);
        from_node_0.add(2);
        from_node_1.add(3);
        from_node_2.add(3);

        graph1.add(from_node_0);
        graph1.add(from_node_1);
        graph1.add(from_node_2);
        graph1.add(from_node_3);

        System.out.println("\n\nAll paths in graph G1");
        obj.FindAllPaths (graph1, 0, 3);

        // Graph 2
        //  {{1,2}, {2,3}, {3}, {}}; // 0 -> (1,2); 1 -> (2,3); 2 -> (3); 3 -> (None)
        ClearConnections(from_node_0, from_node_1, from_node_2, from_node_3, from_node_4);

        from_node_0.add(1);
        from_node_0.add(2);
        from_node_1.add(2);
        from_node_1.add(3);
        from_node_2.add(3);

        List<List<Integer>> graph2 = new ArrayList<List<Integer>>();

        graph2.add(from_node_0);
        graph2.add(from_node_1);
        graph2.add(from_node_2);
        graph2.add(from_node_3);

        System.out.println("\n\nAll paths in graph G2");
        obj.FindAllPaths (graph2, 0 , 3);

        // Graph 3       
        //  {{4, 3, 1}, {3, 2, 4}, {3}, {4}}; // 0 -> (4, 3, 1); 1 -> (3, 2, 4); 2 -> (3); 3 -> (4)
        ClearConnections(from_node_0, from_node_1, from_node_2, from_node_3, from_node_4);
        from_node_0.add(4);
        from_node_0.add(3);
        from_node_0.add(1);
        from_node_1.add(3);
        from_node_1.add(2);
        from_node_1.add(4);
        from_node_2.add(3);
        from_node_3.add(4);

        List<List<Integer>> graph3 = new ArrayList<List<Integer>>();

        graph3.add(from_node_0);
        graph3.add(from_node_1);
        graph3.add(from_node_2);
        graph3.add(from_node_3);
        graph3.add(from_node_4);

        System.out.println("\n\nAll paths in graph G3");
        obj.FindAllPaths (graph3, 0, 4);
    }
}

Output

All paths in graph G1
Source : 0 Destination : 3
Path : 0 1 3 
Path : 0 2 3 

All paths in graph G2
Source : 0 Destination : 3
Path : 0 1 2 3 
Path : 0 1 3 
Path : 0 2 3 

All paths in graph G3
Source : 0 Destination : 4
Path : 0 4 
Path : 0 3 4 
Path : 0 1 3 4 
Path : 0 1 2 3 4 
Path : 0 1 4