Print all possible paths in a DAG from vertex whose indegree is 0

0 0 7 minutes read

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 -> 1

Input: 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 paths
void 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 Code
int 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 DAG
import 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 paths
def 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] = False
 
 
def 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 code
from collections import defaultdict
 
n = 6
# set all nodes unvisited
visited = [False] * (n + 1)
path = []
 
# edges = (a, b): a -> b
edges = [(5, 0), (5, 2), (2, 3),
         (4, 0), (4, 1), (3, 1)]
 
# adjacency list for nodes
adj = defaultdict(list)
 
# indeg0 and outdeg0 arrays
indeg0 = [True]*n
outdeg0 = [True]*n
 
for 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] = False
 
print('All possible paths:')
print_all_paths(n)

C#

// C# program to print all possible paths in a DAG
using 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 DAG
const path = [];
let indeg0 = [];
let outdeg0 = [];
let adj = [];
let visited = [];
 
// Recursive function to print all paths
function 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)²
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 zambiatek!