Open In App

Longest Path in a Directed Acyclic Graph

Last Updated : 14 Mar, 2024
Improve
Improve
Like Article
Like
Save
Share
Report
 

Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph.

The longest path problem for a general graph is not as easy as the shortest path problem because the longest path problem doesn’t have optimal substructure property. In fact, the Longest Path problem is NP-Hard for a general graph. However, the longest path problem has a linear time solution for directed acyclic graphs. The idea is similar to linear time solution for shortest path in a directed acyclic graph., we use Topological Sorting

We initialize distances to all vertices as minus infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.

Following figure shows step by step process of finding longest paths.
 

LongestPath

Following is complete algorithm for finding longest distances. 

  1. Initialize dist[] = {NINF, NINF, ….} and dist[s] = 0 where s is the source vertex. Here NINF means negative infinite. 
  2. Create a topological order of all vertices. 
  3. Do following for every vertex u in topological order. 
    • ..Do following for every adjacent vertex v of u 
    • ……if (dist[v] < dist[u] + weight(u, v)) 
    • ………dist[v] = dist[u] + weight(u, v) 

Following is C++ implementation of the above algorithm.

CPP




// A C++ program to find single source longest distances
// in a DAG
#include <iostream>
#include <limits.h>
#include <list>
#include <stack>
#define NINF INT_MIN
using namespace std;
  
// Graph is represented using adjacency list. Every 
// node of adjacency list contains vertex number of 
// the vertex to which edge connects. It also 
// contains weight of the edge 
class AdjListNode { 
    int v; 
    int weight; 
    
public
    AdjListNode(int _v, int _w) 
    
        v = _v; 
        weight = _w; 
    
    int getV() { return v; } 
    int getWeight() { return weight; } 
}; 
    
// Class to represent a graph using adjacency list 
// representation 
class Graph { 
    int V; // No. of vertices' 
    
    // Pointer to an array containing adjacency lists 
    list<AdjListNode>* adj; 
    
    // A function used by longestPath 
    void topologicalSortUtil(int v, bool visited[], 
                             stack<int>& Stack); 
    
public
    Graph(int V); // Constructor 
    ~Graph(); // Destructor
  
    // function to add an edge to graph 
    void addEdge(int u, int v, int weight); 
    
    // Finds longest distances from given source vertex 
    void longestPath(int s); 
}; 
    
Graph::Graph(int V) // Constructor 
    this->V = V; 
    adj = new list<AdjListNode>[V]; 
  
Graph::~Graph() // Destructor 
    delete [] adj; 
  
  
void Graph::addEdge(int u, int v, int weight) 
    AdjListNode node(v, weight); 
    adj[u].push_back(node); // Add v to u's list 
    
// A recursive function used by longestPath. See below 
// link for details 
void Graph::topologicalSortUtil(int v, bool visited[], 
                                stack<int>& Stack) 
    // Mark the current node as visited 
    visited[v] = true
    
    // Recur for all the vertices adjacent to this vertex 
    list<AdjListNode>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) { 
        AdjListNode node = *i; 
        if (!visited[node.getV()]) 
            topologicalSortUtil(node.getV(), visited, Stack); 
    
    
    // Push current vertex to stack which stores topological 
    // sort 
    Stack.push(v); 
    
// The function to find longest distances from a given vertex. 
// It uses recursive topologicalSortUtil() to get topological 
// sorting. 
void Graph::longestPath(int s) 
    stack<int> Stack; 
    int dist[V]; 
    
    // Mark all the vertices as not visited 
    bool* visited = new bool[V]; 
    for (int i = 0; i < V; i++) 
        visited[i] = false
    
    // Call the recursive helper function to store Topological 
    // Sort starting from all vertices one by one 
    for (int i = 0; i < V; i++) 
        if (visited[i] == false
            topologicalSortUtil(i, visited, Stack); 
    
    // Initialize distances to all vertices as infinite and 
    // distance to source as 0 
    for (int i = 0; i < V; i++) 
        dist[i] = NINF; 
    dist[s] = 0; 
    // Process vertices in topological order 
    while (Stack.empty() == false) { 
        // Get the next vertex from topological order 
        int u = Stack.top(); 
        Stack.pop(); 
    
        // Update distances of all adjacent vertices 
        list<AdjListNode>::iterator i; 
        if (dist[u] != NINF) { 
            for (i = adj[u].begin(); i != adj[u].end(); ++i){ 
              
                if (dist[i->getV()] < dist[u] + i->getWeight()) 
                    dist[i->getV()] = dist[u] + i->getWeight();
            }
        
    
    
    // Print the calculated longest distances 
    for (int i = 0; i < V; i++) 
        (dist[i] == NINF) ? cout << "INF " : cout << dist[i] << " ";
      
    delete [] visited;
    
// Driver program to test above functions 
int main() 
    // Create a graph given in the above diagram. 
    // Here vertex numbers are 0, 1, 2, 3, 4, 5 with 
    // following mappings: 
    // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z 
    Graph g(6); 
    g.addEdge(0, 1, 5); 
    g.addEdge(0, 2, 3); 
    g.addEdge(1, 3, 6); 
    g.addEdge(1, 2, 2); 
    g.addEdge(2, 4, 4); 
    g.addEdge(2, 5, 2); 
    g.addEdge(2, 3, 7); 
    g.addEdge(3, 5, 1); 
    g.addEdge(3, 4, -1); 
    g.addEdge(4, 5, -2); 
    
    int s = 1; 
    cout << "Following are longest distances from "
            "source vertex "
         << s << " \n"
    g.longestPath(s); 
    
    return 0; 
}


Java




// A Java program to find single source longest distances
// in a DAG
import java.util.*;
class GFG
{
    
  // Graph is represented using adjacency list. Every 
  // node of adjacency list contains vertex number of 
  // the vertex to which edge connects. It also 
  // contains weight of the edge 
  static class AdjListNode { 
    int v; 
    int weight; 
  
    AdjListNode(int _v, int _w) 
    
      v = _v; 
      weight = _w; 
    
    int getV() { return v; } 
    int getWeight() { return weight; } 
  }
  
  // Class to represent a graph using adjacency list 
  // representation 
  static class Graph { 
    int V; // No. of vertices' 
  
    // Pointer to an array containing adjacency lists 
    ArrayList<ArrayList<AdjListNode>> adj; 
  
    Graph(int V) // Constructor 
    
      this.V = V; 
      adj = new ArrayList<ArrayList<AdjListNode>>(V); 
  
      for(int i = 0; i < V; i++){
        adj.add(new ArrayList<AdjListNode>());
      }
    
  
    void addEdge(int u, int v, int weight) 
    
      AdjListNode node = new AdjListNode(v, weight); 
      adj.get(u).add(node); // Add v to u's list 
    
  
    // A recursive function used by longestPath. See below 
    // link for details 
    void topologicalSortUtil(int v, boolean visited[], 
                             Stack<Integer> stack) 
    
      // Mark the current node as visited 
      visited[v] = true
  
      // Recur for all the vertices adjacent to this vertex 
      for (int i = 0; i<adj.get(v).size(); i++) { 
        AdjListNode node = adj.get(v).get(i);
        if (!visited[node.getV()]) 
          topologicalSortUtil(node.getV(), visited, stack); 
      
  
      // Push current vertex to stack which stores topological 
      // sort 
      stack.push(v); 
    
  
    // The function to find longest distances from a given vertex. 
    // It uses recursive topologicalSortUtil() to get topological 
    // sorting. 
    void longestPath(int s) 
    
      Stack<Integer> stack = new Stack<Integer>(); 
      int dist[] = new int[V]; 
  
      // Mark all the vertices as not visited 
      boolean visited[] = new boolean[V]; 
      for (int i = 0; i < V; i++) 
        visited[i] = false
  
      // Call the recursive helper function to store Topological 
      // Sort starting from all vertices one by one 
      for (int i = 0; i < V; i++) 
        if (visited[i] == false
          topologicalSortUtil(i, visited, stack); 
  
      // Initialize distances to all vertices as infinite and 
      // distance to source as 0 
      for (int i = 0; i < V; i++) 
        dist[i] = Integer.MIN_VALUE; 
  
      dist[s] = 0
        
      // Process vertices in topological order 
      while (stack.isEmpty() == false
      {
          
        // Get the next vertex from topological order 
        int u = stack.peek(); 
        stack.pop(); 
  
        // Update distances of all adjacent vertices ; 
        if (dist[u] != Integer.MIN_VALUE) 
        
          for (int i = 0; i<adj.get(u).size(); i++)
          
            AdjListNode node = adj.get(u).get(i);
            if (dist[node.getV()] < dist[u] + node.getWeight()) 
              dist[node.getV()] = dist[u] + node.getWeight();
          }
        
      
  
      // Print the calculated longest distances 
      for (int i = 0; i < V; i++) 
        if(dist[i] == Integer.MIN_VALUE)
          System.out.print("INF ");
      else
        System.out.print(dist[i] + " ");
    
  }
  
  // Driver program to test above functions 
  public static void main(String args[]) 
  
    // Create a graph given in the above diagram. 
    // Here vertex numbers are 0, 1, 2, 3, 4, 5 with 
    // following mappings: 
    // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z 
    Graph g = new Graph(6); 
    g.addEdge(0, 1, 5); 
    g.addEdge(0, 2, 3); 
    g.addEdge(1, 3, 6); 
    g.addEdge(1, 2, 2); 
    g.addEdge(2, 4, 4); 
    g.addEdge(2, 5, 2); 
    g.addEdge(2, 3, 7); 
    g.addEdge(3, 5, 1); 
    g.addEdge(3, 4, -1); 
    g.addEdge(4, 5, -2); 
  
    int s = 1
    System.out.print("Following are longest distances from source vertex "+ s + " \n" );
    g.longestPath(s); 
  
  }
}
  
// This code is contribute by adityapande88.


Python3




# A recursive function used by longestPath. See below
# link for details
# https:#www.geeksforgeeks.org/topological-sorting/
def topologicalSortUtil(v):
    global Stack, visited, adj
    visited[v] = True
  
    # Recur for all the vertices adjacent to this vertex
    # list<AdjListNode>::iterator i
    for i in adj[v]:
        if (not visited[i[0]]):
            topologicalSortUtil(i[0])
  
    # Push current vertex to stack which stores topological
    # sort
    Stack.append(v)
  
# The function to find longest distances from a given vertex.
# It uses recursive topologicalSortUtil() to get topological
# sorting.
def longestPath(s):
    global Stack, visited, adj, V
    dist = [-10**9 for i in range(V)]
  
    # Call the recursive helper function to store Topological
    # Sort starting from all vertices one by one
    for i in range(V):
        if (visited[i] == False):
            topologicalSortUtil(i)
    # print(Stack)
  
    # Initialize distances to all vertices as infinite and
    # distance to source as 0
    dist[s] = 0
    # Stack.append(1)
  
    # Process vertices in topological order
    while (len(Stack) > 0):
        
        # Get the next vertex from topological order
        u = Stack[-1]
        del Stack[-1]
        #print(u)
  
        # Update distances of all adjacent vertices
        # list<AdjListNode>::iterator i
        if (dist[u] != 10**9):
            for i in adj[u]:
                # print(u, i)
                if (dist[i[0]] < dist[u] + i[1]):
                    dist[i[0]] = dist[u] + i[1]
  
    # Print calculated longest distances
    # print(dist)
    for i in range(V):
        print("INF ",end="") if (dist[i] == -10**9) else print(dist[i],end=" ")
  
# Driver code
if __name__ == '__main__':
    V, Stack, visited = 6, [], [False for i in range(7)]
    adj = [[] for i in range(7)]
      
    # Create a graph given in the above diagram.
    # Here vertex numbers are 0, 1, 2, 3, 4, 5 with
    # following mappings:
    # 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
    adj[0].append([1, 5])
    adj[0].append([2, 3])
    adj[1].append([3, 6])
    adj[1].append([2, 2])
    adj[2].append([4, 4])
    adj[2].append([5, 2])
    adj[2].append([3, 7])
    adj[3].append([5, 1])
    adj[3].append([4, -1])
    adj[4].append([5, -2])
  
    s = 1
    print("Following are longest distances from source vertex ",s)
    longestPath(s)
  
    # This code is contributed by mohit kumar 29.


C#




// C# program to find single source longest distances
// in a DAG
  
using System;
using System.Collections.Generic;
  
// Graph is represented using adjacency list. Every
// node of adjacency list contains vertex number of
// the vertex to which edge connects. It also
// contains weight of the edge
class AdjListNode {
    private int v;
    private int weight;
  
    public AdjListNode(int _v, int _w)
    {
        v = _v;
        weight = _w;
    }
    public int getV() { return v; }
    public int getWeight() { return weight; }
}
  
// Class to represent a graph using adjacency list
// representation
class Graph {
    private int V; // No. of vertices'
  
    // Pointer to an array containing adjacency lists
    private List<AdjListNode>[] adj;
  
    public Graph(int V) // Constructor
    {
        this.V = V;
        adj = new List<AdjListNode>[ V ];
  
        for (int i = 0; i < V; i++) {
            adj[i] = new List<AdjListNode>();
        }
    }
  
    public void AddEdge(int u, int v, int weight)
    {
        AdjListNode node = new AdjListNode(v, weight);
        adj[u].Add(node); // Add v to u's list
    }
  
    // A recursive function used by longestPath. See below
    // link for details
    private void TopologicalSortUtil(int v, bool[] visited,
                                     Stack<int> stack)
    {
        // Mark the current node as visited
        visited[v] = true;
  
        // Recur for all the vertices adjacent to this
        // vertex
        for (int i = 0; i < adj[v].Count; i++) {
            AdjListNode node = adj[v][i];
            if (!visited[node.getV()])
                TopologicalSortUtil(node.getV(), visited,
                                    stack);
        }
  
        // Push current vertex to stack which stores
        // topological sort
        stack.Push(v);
    }
  
    // The function to find longest distances from a given
    // vertex. It uses recursive topologicalSortUtil() to
    // get topological sorting.
    public void LongestPath(int s)
    {
        Stack<int> stack = new Stack<int>();
        int[] dist = new int[V];
  
        // Mark all the vertices as not visited
        bool[] visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
  
        // Call the recursive helper function to store
        // Topological Sort starting from all vertices one
        // by one
        for (int i = 0; i < V; i++) {
            if (visited[i] == false)
                TopologicalSortUtil(i, visited, stack);
        }
  
        // Initialize distances to all vertices as infinite
        // and distance to source as 0
        for (int i = 0; i < V; i++)
            dist[i] = Int32.MinValue;
  
        dist[s] = 0;
  
        // Process vertices in topological order
        while (stack.Count > 0) {
  
            // Get the next vertex from topological order
            int u = stack.Pop();
  
            // Update distances of all adjacent vertices ;
            if (dist[u] != Int32.MinValue) {
                for (int i = 0; i < adj[u].Count; i++) {
                    AdjListNode node = adj[u][i];
                    if (dist[node.getV()]
                        < dist[u] + node.getWeight())
                        dist[node.getV()]
                            = dist[u] + node.getWeight();
                }
            }
        }
  
        // Print the calculated longest distances
        for (int i = 0; i < V; i++) {
            if (dist[i] == Int32.MinValue)
                Console.Write("INF ");
            else
                Console.Write(dist[i] + " ");
        }
        Console.WriteLine();
    }
}
  
public class GFG {
    // Driver program to test above functions
    static void Main(string[] args)
    {
        // Create a graph given in the above diagram.
        // Here vertex numbers are 0, 1, 2, 3, 4, 5 with
        // following mappings:
        // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
        Graph g = new Graph(6);
        g.AddEdge(0, 1, 5);
        g.AddEdge(0, 2, 3);
        g.AddEdge(1, 3, 6);
        g.AddEdge(1, 2, 2);
        g.AddEdge(2, 4, 4);
        g.AddEdge(2, 5, 2);
        g.AddEdge(2, 3, 7);
        g.AddEdge(3, 5, 1);
        g.AddEdge(3, 4, -1);
        g.AddEdge(4, 5, -2);
  
        int s = 1;
        Console.WriteLine(
            "Following are longest distances from source vertex {0}",
            s);
        g.LongestPath(s);
    }
}
  
// This code is contributed by cavi4762


Javascript




// A Javascript program to find single source longest distances in a DAG
 
   // program to implement stack data structure
   class stack {
     constructor() {
       this.items = [];
     }
 
     // add element to the stack
     push(element) {
       return this.items.push(element);
     }
 
     // remove element from the stack
     pop() {
       if (this.items.length > 0) {
         return this.items.pop();
       }
     }
 
     // view the last element
     top() {
       return this.items[this.items.length - 1];
     }
 
     // check if the stack is empty
     empty() {
       return this.items.length == 0;
     }
 
     // the size of the stack
     size() {
       return this.items.length;
     }
 
     // empty the stack
     clear() {
       this.items = [];
     }
   }
 
   let NINF = Number.MIN_VALUE;
 
   // Graph is represented using adjacency list. Every
   // node of adjacency list contains vertex number of
   // the vertex to which edge connects. It also
   // contains weight of the edge
   class AdjListNode {
     constructor(_v, _w) {
       this.v = _v;
       this.weight = _w;
     }
     getV() {
       return this.v;
     }
     getWeight() {
       return this.weight;
     }
   }
 
   // Class to represent a graph using adjacency list
   // representation
   class Graph {
     // Constructor
     constructor(V) {
       this.V = V; // No. of vertices'
       // Pointer to an array containing adjacency lists
       this.adj = Array.from(Array(V), () => new Array());
     }
 
     // A function used by longestPath
     topologicalSortUtil(v, visited, Stack) {
       // Mark the current node as visited
       visited[v] = true;
 
       // Recur for all the vertices adjacent to this vertex
 
       for (let j in this.adj[v]) {
         let i = this.adj[v][j];
         let node = i;
         if (!visited[node.getV()])
           this.topologicalSortUtil(node.getV(), visited, Stack);
       }
 
       // Push current vertex to stack which stores topological
       // sort
       Stack.push(v);
     }
 
     // function to add an edge to graph
     addEdge(u, v, weight) {
       let node = new AdjListNode(v, weight);
       this.adj[u].push(node); // Add v to u's list
     }
 
       
     // The function to find longest distances from a given vertex.
     // It uses recursive topologicalSortUtil() to get topological
     // sorting.
     longestPath(s) {
       let Stack = new stack();
       let dist = new Array(this.V);
 
       // Mark all the vertices as not visited
       let visited = new Array(this.V);
       for (let i = 0; i < this.V; i++) {
         visited[i] = false;
       }
 
       // Call the recursive helper function to store Topological
       // Sort starting from all vertices one by one
       for (let i = 0; i < this.V; i++)
         if (visited[i] == false)
           this.topologicalSortUtil(i, visited, Stack);
 
       // Initialize distances to all vertices as infinite and
       // distance to source as 0
       for (let i = 0; i < this.V; i++) dist[i] = NINF;
       dist[s] = 0;
       // Process vertices in topological order
       while (Stack.empty() == false) {
         // Get the next vertex from topological order
         let u = Stack.top();
         Stack.pop();
 
         // Update distances of all adjacent vertices
 
         if (dist[u] != NINF) {
           for (let j in this.adj[u]) {
             let i = this.adj[u][j];
             if (dist[i.getV()] < dist[u] + i.getWeight())
               dist[i.getV()] = dist[u] + i.getWeight();
           }
         }
       }
 
       // Print the calculated longest distances
       for (let i = 0; i < this.V; i++)
         dist[i] == NINF ? console.log("INF ") : console.log(dist[i] + " ");
     }
   }
 
   // Driver program to test above functions
 
   // Create a graph given in the above diagram.
   // Here vertex numbers are 0, 1, 2, 3, 4, 5 with
   // following mappings:
   // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
   let g = new Graph(6);
   g.addEdge(0, 1, 5);
   g.addEdge(0, 2, 3);
   g.addEdge(1, 3, 6);
   g.addEdge(1, 2, 2);
   g.addEdge(2, 4, 4);
   g.addEdge(2, 5, 2);
   g.addEdge(2, 3, 7);
   g.addEdge(3, 5, 1);
   g.addEdge(3, 4, -1);
   g.addEdge(4, 5, -2);
 
   let s = 1;
   console.log("Following are longest distances from source vertex " + s);
   g.longestPath(s);
     
   // This code is contributed by satwiksuman.


Output

Following are longest distances from source vertex 1 
INF 0 2 9 8 10 

Time Complexity: Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).

Space complexity : O(V + E), where V is the number of vertices and E is the number of edges in the graph. 

Exercise: The above solution print longest distances, extend the code to print paths also. 

Micro Focus


Previous Article
Next Article

Similar Reads

Longest path in a directed Acyclic graph | Dynamic Programming
Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph.Note: Length of a directed path is the number of edges in it. Examples: Input: N = 4, M = 5 Output: 3 The directed path 1-&gt;3-&gt;2-&gt;4 Input: N = 5, M = 8 Output: 3 Simple Approach: A naive approach is to calculate the len
8 min read
Longest Path in a Directed Acyclic Graph | Set 2
Given a Weighted Directed Acyclic Graph (DAG) and a source vertex in it, find the longest distances from source vertex to all other vertices in the given graph. We have already discussed how we can find Longest Path in Directed Acyclic Graph(DAG) in Set 1. In this post, we will discuss another interesting solution to find longest path of DAG that u
14 min read
Shortest Path in Directed Acyclic Graph
Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest paths from given source to all other vertices. Recommended PracticeShortest path from 1 to nTry It! For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weigh
15 min read
What is Directed Graph? | Directed Graph meaning
A directed graph is defined as a type of graph where the edges have a direction associated with them. Characteristics of Directed Graph Directed graphs have several characteristics that make them different from undirected graphs. Here are some key characteristics of directed graphs: Directed edges: In a directed graph, edges have a direction associ
3 min read
Assign directions to edges so that the directed graph remains acyclic
Given a graph with both directed and undirected edges. It is given that the directed edges don't form cycle. How to assign directions to undirected edges so that the graph (with all directed edges) remains acyclic even after the assignment? For example, in the below graph, blue edges don't have directions. We strongly recommend to minimize your bro
1 min read
Number of paths from source to destination in a directed acyclic graph
Given a Directed Acyclic Graph with n vertices and m edges. The task is to find the number of different paths that exist from a source vertex to destination vertex. Examples: Input: source = 0, destination = 4 Output: 3 Explanation: 0 -&gt; 2 -&gt; 3 -&gt; 4 0 -&gt; 3 -&gt; 4 0 -&gt; 4 Input: source = 0, destination = 1 Output: 1 Explanation: There
15+ min read
Maximum difference between node and its ancestor in a Directed Acyclic Graph ( DAG )
Given a 2D array Edges[][], representing a directed edge between the pair of nodes in a Directed Acyclic Connected Graph consisting of N nodes valued from [1, N] and an array arr[] representing weights of each node, the task is to find the maximum absolute difference between the weights of any node and any of its ancestors. Examples: Input: N = 5,
8 min read
Count nodes with prime weight in a Directed Acyclic Graph
Given a directed acyclic graph (DAG) with N nodes with integer representations 0 to N-1 and an integer array arr[], where arr[i] is the parent of node i. The root of the DAG is node i if arr[i] is 0. The weight of a node is calculated as the sum of the node's value and the number of parent nodes it has, the task is to determine the number of nodes,
8 min read
Introduction to Directed Acyclic Graph
A Directed Acyclic Graph, often abbreviated as DAG, is a fundamental concept in graph theory. DAGs are used to show how things are related or depend on each other in a clear and organized way. In this article, we are going to learn about Directed Acyclic Graph, its properties, and application in real life. What is Directed Acyclic Graph?A Directed
3 min read
All Topological Sorts of a Directed Acyclic Graph
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. Given a DAG, print all topological sorts of the graph. For example, consider the below graph. All topological
11 min read
Practice Tags :
three90RightbarBannerImg