Given a Directed Acyclic Graph (DAG), having N vertices and M edges, The task is to print all path starting from vertex whose in-degree is zero.
Indegree of a vertex is the total number of incoming edges to a vertex.
Example:
Input: N = 6, edges[] = {{5, 0}, {5, 2}, {4, 0}, {4, 1}, {2, 3}, {3, 1}}
Output: All possible paths:
4 0
4 1
5 0
5 2 3 1
Explanation:
The given graph can be represented as:
There are two vertices whose indegree are zero i.e vertex 5 and 4, after exploring these vertices we got the fallowing path:
4 -> 0
4 -> 1
5 -> 0
5 -> 2 -> 3 -> 1Input: N = 6, edges[] = {{0, 5}}
Output: All possible paths:
0 5
Explanation:
There will be only one possible path in the graph.
Approach:
- Create a boolean array indeg0 which store a true value for all those vertex whose indegree is zero.
- Apply DFS on all those vertex whose indegree is 0.
- Print all path starting from a vertex whose indegree is 0 to a vertex whose outdegrees are zero.
Illustration:
For the above graph:
indeg0[] = {False, False, False, False, True, True}
Since indeg[4] = True, so applying DFS on vertex 4 and printing all path terminating to 0 outdegree vertex are as follow:
4 -> 0
4 -> 1
Also indeg[5] = True, so applying DFS on vertex 5 and printing all path terminating to 0 outdegree vertex are as follow:
5 -> 0
5 -> 2 -> 3 -> 1
Here is the implementation of the above approach:
C++
// C++ program to print// all possible paths in a DAG#include <bits/stdc++.h>using namespace std;vector<int> path;vector<bool> indeg0, outdeg0;vector<vector<int> > adj;vector<bool> visited;// Recursive function to print all pathsvoid dfs(int s){ // Append the node in path // and set visited path.push_back(s); visited[s] = true; // Path started with a node // having in-degree 0 and // current node has out-degree 0, // print current path if (outdeg0[s] && indeg0[path[0]]) { for (auto x : path) cout << x << " "; cout << '\n'; } for (auto node : adj[s]) { if (!visited[node]) dfs(node); } path.pop_back(); visited[s] = false;}void print_all_paths(int n){ for (int i = 0; i < n; i++) { // for each node with in-degree 0 // print all possible paths if (indeg0[i] && !adj[i].empty()) { dfs(i); } }}// Driver Codeint main(){ int n; n = 6; // set all nodes unvisited visited = vector<bool>(n, false); // adjacency list for nodes adj = vector<vector<int> >(n); // indeg0 and outdeg0 arrays indeg0 = vector<bool>(n, true); outdeg0 = vector<bool>(n, true); // edges vector<pair<int, int> > edges = { { 5, 0 }, { 5, 2 }, { 2, 3 }, { 4, 0 }, { 4, 1 }, { 3, 1 } }; for (int i = 0; i < edges.size(); i++) { int u = edges[i].first; int v = edges[i].second; adj[u].push_back(v); // set indeg0[v] <- false indeg0[v] = false; // set outdeg0[u] <- false outdeg0[u] = false; } cout << "All possible paths:\n"; print_all_paths(n); return 0;} |
Java
// Java program to print all possible paths in a DAGimport java.io.*;import java.util.*;class GFG { static List<List<Integer> > adjList; static boolean[] inDeg0; static boolean[] outDeg0; // Recursive function static void dfs(int s, List<Integer> localPath, boolean[] localVisited) { // Append the node in path and set visited localPath.add(s); localVisited[s] = true; // Path started with a node having in-degree 0 and // current node has out-degree 0, print current path if (outDeg0[s] && inDeg0[localPath.get(0)]) { for (int i = 0; i < localPath.size(); i++) { System.out.print(localPath.get(i) + " "); } System.out.println(); } for (int v : adjList.get(s)) { if (!localVisited[v]) { dfs(v, localPath, localVisited); } } localPath.remove(localPath.size() - 1); localVisited[s] = false; } static void print_all_paths(int n) { for (int i = 0; i < n; i++) { // for each node with in-degree 0 print all // possible paths if (inDeg0[i] && !adjList.get(i).isEmpty()) { List<Integer> localPath = new ArrayList<>(); boolean[] localVisited = new boolean[n]; dfs(i, localPath, localVisited); } } } public static void main(String[] args) { int n = 6; // adjacency list for nodes adjList = new ArrayList<>(); // indeg0 and outdeg0 arrays inDeg0 = new boolean[n]; outDeg0 = new boolean[n]; for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); inDeg0[i] = true; outDeg0[i] = true; } // edges int[][] edges = { { 5, 0 }, { 5, 2 }, { 2, 3 }, { 4, 0 }, { 4, 1 }, { 3, 1 } }; for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; adjList.get(u).add(v); // set indeg0[v] = false inDeg0[v] = false; // set outdeg0[u] = false outDeg0[u] = false; } System.out.println("All possible paths:"); print_all_paths(n); }}// This code is contributed by lokeshmvs21. |
Python3
# Python program to print all# possible paths in a DAG# Recursive function to print all pathsdef dfs(s): # Append the node in path # and set visited path.append(s) visited[s] = True # Path started with a node # having in-degree 0 and # current node has out-degree 0, # print current path if outdeg0[s] and indeg0[path[0]]: print(*path) # Recursive call to print all paths for node in adj[s]: if not visited[node]: dfs(node) # Remove node from path # and set unvisited path.pop() visited[s] = Falsedef print_all_paths(n): for i in range(n): # for each node with in-degree 0 # print all possible paths if indeg0[i] and adj[i]: path = [] visited = [False] * (n + 1) dfs(i)# Driver codefrom collections import defaultdictn = 6# set all nodes unvisitedvisited = [False] * (n + 1)path = []# edges = (a, b): a -> bedges = [(5, 0), (5, 2), (2, 3), (4, 0), (4, 1), (3, 1)]# adjacency list for nodesadj = defaultdict(list)# indeg0 and outdeg0 arraysindeg0 = [True]*noutdeg0 = [True]*nfor edge in edges: u, v = edge[0], edge[1] # u -> v adj[u].append(v) # set indeg0[v] <- false indeg0[v] = False # set outdeg0[u] <- false outdeg0[u] = Falseprint('All possible paths:')print_all_paths(n) |
C#
// C# program to print all possible paths in a DAGusing System;using System.Collections.Generic;public class GFG { static List<List<int> > adjList; static bool[] inDeg0; static bool[] outDeg0; // Recursive function static void DFS(int s, List<int> localPath, bool[] localVisited) { // Append the node in path and set visited localPath.Add(s); localVisited[s] = true; // Path started with a node having in-degree 0 and // current node has out-degree 0, print current path if (outDeg0[s] && inDeg0[localPath[0]]) { for (int i = 0; i < localPath.Count; i++) { Console.Write(localPath[i] + " "); } Console.WriteLine(); } foreach(int v in adjList[s]) { if (!localVisited[v]) { DFS(v, localPath, localVisited); } } localPath.RemoveAt(localPath.Count - 1); localVisited[s] = false; } static void PrintAllPaths(int n) { for (int i = 0; i < n; i++) { // for each node with in-degree 0 print all // possible paths if (inDeg0[i] && adjList[i].Count > 0) { List<int> localPath = new List<int>(); bool[] localVisited = new bool[n]; DFS(i, localPath, localVisited); } } } static public void Main() { // Code int n = 6; // adjacency list for nodes adjList = new List<List<int> >(); // indeg0 and outdeg0 arrays inDeg0 = new bool[n]; outDeg0 = new bool[n]; for (int i = 0; i < n; i++) { adjList.Add(new List<int>()); inDeg0[i] = true; outDeg0[i] = true; } // edges int[][] edges = { new int[] { 5, 0 }, new int[] { 5, 2 }, new int[] { 2, 3 }, new int[] { 4, 0 }, new int[] { 4, 1 }, new int[] { 3, 1 } }; foreach(int[] edge in edges) { int u = edge[0]; int v = edge[1]; adjList[u].Add(v); // set indeg0[v] = false inDeg0[v] = false; // set outdeg0[u] = false outDeg0[u] = false; } Console.WriteLine("All possible paths:"); PrintAllPaths(n); }}// This code is contributed by karthik |
Javascript
// Javascript program to print all possible paths in a DAGconst path = [];let indeg0 = [];let outdeg0 = [];let adj = [];let visited = [];// Recursive function to print all pathsfunction dfs(s) { // Append the node in path // and set visited path.push(s); visited[s] = true; // Path started with a node // having in-degree 0 and // current node has out-degree 0, // print current path if (outdeg0[s] && indeg0[path[0]]) { console.log(path.join(" ")); } adj[s].forEach((node) => { if (!visited[node]) { dfs(node); } }); path.pop(); visited[s] = false;}function print_all_paths(n) { for (let i = 0; i < n; i++) { // for each node with in-degree 0 // print all possible paths if (indeg0[i] && adj[i].length > 0) { dfs(i); } }}// Driver code const n = 6; // set all nodes unvisited visited = Array(n).fill(false); // adjacency list for nodes adj = Array(n).fill(null).map(() => []); // indeg0 and outdeg0 arrays indeg0 = Array(n).fill(true); outdeg0 = Array(n).fill(true); // edges const edges = [[5, 0], [5, 2], [2, 3], [4, 0], [4, 1], [3, 1]]; edges.forEach(([u, v]) => { adj[u].push(v); // set indeg0[v] <- false indeg0[v] = false; // set outdeg0[u] <- false outdeg0[u] = false; }); console.log("All possible paths:"); print_all_paths(n);// This code is contributed by divyansh2212 |
Output:
All possible paths: 4 0 4 1 5 0 5 2 3 1
Time Complexity: O (N + E)2
Auxiliary Space: O (N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
