# 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 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.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
``````