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. Idea is to 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. The DFS traversal 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. 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 of all the paths present in a directed acyclic graph
Java
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
class Graph {
private List<Integer> path;
private int dest;
private int src;
public void FindAllPaths(List<List<Integer>> graph) {
// Clear previously stored paths
path = new ArrayList<Integer>();
path.clear();
dest = graph.size() - 1;
System.out.print("Source : " + src + " Destination : " + dest);
path.add(src);
DFS(src, graph);
}
public void DFS(int src, List<List<Integer>> graph) {
if (src == dest) {
System.out.print("\nPath : " );
for (Integer node : path)
System.out.print(node + " ");
} else {
for (Integer adjnode : graph.get(src)) {
path.add(adjnode);
DFS(adjnode, graph);
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);
// 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);
// 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);
}
}
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
C++ Program for finding all the paths in a directed acyclic graph using depth first search (DFS) traversal and backtracking.
#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 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)
/* 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;
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