All paths in a directed acyclic graph

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


Example of finding all the paths in a directed acyclic graph using depth-first search traversal

All_Paths_In_A_Graph

C++ : Finding all the paths in a directed acyclic graph using depth first search (DFS) traversal and backtracking. Implemented in C++14

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

class Graph {

private :
    vector<int> path;
    vector<vector<int>> allpaths;
    int dest;
    int src;

public:
    vector<vector<int>> FindAllPaths(vector<vector<int>>& graph) {
        // Clear an previously stored paths
        path.clear();
        allpaths.clear();

        dest = graph.size()-1;
        path.push_back(src);
        cout << "Source : " << src << " Destination : " << dest << endl;
        DFS(src, graph);
        return allpaths;
    }

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

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

void PrintAllPaths(vector<vector<int>> allpaths) {
    for (const auto& path : allpaths) {
        for (const auto& node : path)
            cout << node << " ";
        cout << endl;
    }
    cout << endl;
    allpaths.clear();
}

int main() {

    vector<vector<int>> g1 = {{1,2}, {3}, {3}, {}}; // 0 -> (1,2); 1 -> (3); 2 -> (3); 3 -> (None)
    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;
    allpaths = g.FindAllPaths(g1);
    PrintAllPaths(allpaths);
   
    cout << "All paths in graph G2" << endl;
    allpaths = g.FindAllPaths(g2);
    PrintAllPaths(allpaths);

    cout << "All paths in graph G3" << endl;
    allpaths = g.FindAllPaths(g3);
    PrintAllPaths(allpaths);

    return 0;
}

Output showing all the paths in a graph found using depth-first search traversal

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

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

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

Copyright (c) 2020, Algotree.org.
All rights reserved.