Printing pre and post visited times in DFS of a graph
Depth First Search (DFS) marks all the vertices of a graph as visited. So for making DFS useful, some additional information can also be stored. For instance, the order in which the vertices are visited while running DFS.
Pre-visit and Post-visit numbers are the extra information that can be stored while running a DFS on a graph and which turns out to be really useful. Pre-visit number tells the time at which the node gets into the recursion stack and Post-visit number tells the time at which the node comes out from recursion stack of DFS.
Example:
The numbers written in brackets denote [Pre-visit number, Post-visit number].
Pre and Post numbers are widely used in graph algorithms. For example, they can be used to find out whether a particular node lies in the sub-tree of another node.
To find whether u lies in the sub-tree of v or not we just compare the pre and post number of u and v. If pre[u] > pre[v] and post[u] < post[v] then u lies in the sub-tree of v otherwise not. You can see above example for more clarification.
Pre-visit and Post-visit numbers can be found by simple DFS. We will take two arrays one for storing pre numbers and one for post numbers and by taking a variable that will keep track of the time. The implementation of the same is given below:
Implementation:
C++
#include <bits/stdc++.h> using namespace std; // Variable to keep track of time int Time = 1; // Function to perform DFS starting from node u void dfs( int u, vector<vector< int >> aList, vector< int > &pre, vector< int > &post, vector< int > &vis) { // Storing the pre number whenever // the node comes into recursion stack pre[u] = Time; // Increment time Time++; vis[u] = 1; for ( int v : aList[u]) { if (vis[v] == 0) dfs(v, aList, pre, post, vis); } // Storing the post number whenever // the node goes out of recursion stack post[u] = Time; Time++; } // Driver Code int main() { // Number of nodes in graph int n = 6; // Adjacency list vector<vector< int >> aList(n + 1); vector< int > pre(n + 1); vector< int > post(n + 1); // Visited array vector< int > vis(n + 1); // Edges aList[1].push_back(2); aList[2].push_back(1); aList[2].push_back(4); aList[4].push_back(2); aList[1].push_back(3); aList[3].push_back(1); aList[3].push_back(4); aList[4].push_back(3); aList[3].push_back(5); aList[5].push_back(3); aList[5].push_back(6); aList[6].push_back(5); // DFS starting at Node 1 dfs(1, aList, pre, post, vis); // Number of nodes in graph for ( int i = 1; i <= n; i++) cout << "Node " << i << " Pre number " << pre[i] << " Post number " << post[i] << endl; return 0; } // This code is contributed by divyesh072019 |
Java
import java.util.*; public class GFG { // Variable to keep track of time static int time = 1 ; // Function to perform DFS starting from node u static void dfs( int u, ArrayList<ArrayList<Integer> > aList, int pre[], int post[], int vis[]) { // Storing the pre number whenever // the node comes into recursion stack pre[u] = time; // Increment time time++; vis[u] = 1 ; for ( int v : aList.get(u)) { if (vis[v] == 0 ) dfs(v, aList, pre, post, vis); } // Storing the post number whenever // the node goes out of recursion stack post[u] = time; time++; } // Driver code public static void main(String args[]) { // Number of nodes in graph int n = 6 ; // Adjacency list ArrayList<ArrayList<Integer> > aList = new ArrayList<ArrayList<Integer> >(n + 1 ); for ( int i = 1 ; i <= n; i++) { ArrayList<Integer> list = new ArrayList<>(); aList.add(list); } aList.add( new ArrayList<Integer>()); int pre[] = new int [n + 1 ]; int post[] = new int [n + 1 ]; // Visited array int vis[] = new int [n + 1 ]; // Edges aList.get( 1 ).add( 2 ); aList.get( 2 ).add( 1 ); aList.get( 2 ).add( 4 ); aList.get( 4 ).add( 2 ); aList.get( 1 ).add( 3 ); aList.get( 3 ).add( 1 ); aList.get( 3 ).add( 4 ); aList.get( 4 ).add( 3 ); aList.get( 3 ).add( 5 ); aList.get( 5 ).add( 3 ); aList.get( 5 ).add( 6 ); aList.get( 6 ).add( 5 ); // DFS starting at Node 1 dfs( 1 , aList, pre, post, vis); // Number of nodes in graph for ( int i = 1 ; i <= n; i++) System.out.println( "Node " + i + " Pre number " + pre[i] + " Post number " + post[i]); } } |
Python3
# Variable to keep track of time time = 1 # Function to perform DFS starting # from node u def dfs(u, aList, pre, post, vis): global time # Storing the pre number whenever # the node comes into recursion stack pre[u] = time # Increment time time + = 1 vis[u] = 1 for v in aList[u]: if (vis[v] = = 0 ): dfs(v, aList, pre, post, vis) # Storing the post number whenever # the node goes out of recursion stack post[u] = time time + = 1 # Driver code if __name__ = = '__main__' : # Number of nodes in graph n = 6 # Adjacency list aList = [[] for i in range (n + 1 )] pre = [ 0 for i in range (n + 1 )] post = [ 0 for i in range (n + 1 )] # Visited array vis = [ 0 for i in range (n + 1 )] # Edges aList[ 1 ].append( 2 ) aList[ 2 ].append( 1 ) aList[ 2 ].append( 4 ) aList[ 4 ].append( 2 ) aList[ 1 ].append( 3 ) aList[ 3 ].append( 1 ) aList[ 3 ].append( 4 ) aList[ 4 ].append( 3 ) aList[ 3 ].append( 5 ) aList[ 5 ].append( 3 ) aList[ 5 ].append( 6 ) aList[ 6 ].append( 5 ) # DFS starting at Node 1 dfs( 1 , aList, pre, post, vis) # Number of nodes in graph for i in range ( 1 , n + 1 ): print ( "Node " + str (i) + " Pre number " + str (pre[i]) + " Post number " + str (post[i])) # This code is contributed by rutvik_56 |
C#
using System; using System.Collections; using System.Collections.Generic; class GFG{ // Variable to keep track of time static int time = 1; // Function to perform DFS starting from node u static void dfs( int u, ArrayList aList, int []pre, int []post, int []vis) { // Storing the pre number whenever // the node comes into recursion stack pre[u] = time; // Increment time time++; vis[u] = 1; foreach ( int v in (ArrayList)aList[u]) { if (vis[v] == 0) dfs(v, aList, pre, post, vis); } // Storing the post number whenever // the node goes out of recursion stack post[u] = time; time++; } // Driver code public static void Main( string []args) { // Number of nodes in graph int n = 6; // Adjacency list ArrayList aList = new ArrayList(n + 1); for ( int i = 1; i <= n; i++) { ArrayList list = new ArrayList(); aList.Add(list); } aList.Add( new ArrayList()); int []pre = new int [n + 1]; int []post = new int [n + 1]; // Visited array int []vis = new int [n + 1]; // Edges ((ArrayList)aList[1]).Add(2); ((ArrayList)aList[2]).Add(1); ((ArrayList)aList[2]).Add(4); ((ArrayList)aList[4]).Add(2); ((ArrayList)aList[1]).Add(3); ((ArrayList)aList[3]).Add(1); ((ArrayList)aList[3]).Add(4); ((ArrayList)aList[4]).Add(3); ((ArrayList)aList[3]).Add(5); ((ArrayList)aList[5]).Add(3); ((ArrayList)aList[5]).Add(6); ((ArrayList)aList[6]).Add(5); // DFS starting at Node 1 dfs(1, aList, pre, post, vis); // Number of nodes in graph for ( int i = 1; i <= n; i++) Console.WriteLine( "Node " + i + " Pre number " + pre[i] + " Post number " + post[i]); } } // This code is contributed by pratham76 |
Javascript
<script> // Variable to keep track of time let time = 1; // Function to perform DFS starting // from node u function dfs(u, aList, pre, post, vis) { // Storing the pre number whenever // the node comes into recursion stack pre[u] = time; // Increment time time += 1; vis[u] = 1; for (let v = 0; v < aList[u].length; v++) { if (vis[aList[u][v]] == 0) dfs(aList[u][v], aList, pre, post, vis); } // Storing the post number whenever // the node goes out of recursion stack post[u] = time; time += 1; } // Number of nodes in graph let n = 6; // Adjacency list let aList = []; for (let i = 0; i < (n + 1); i++) { aList.push([]); } let pre = new Array(n+1); let post = new Array(n+1); pre.fill(0); post.fill(0); // Visited array let vis = new Array(n+1); vis.fill(0); // Edges aList[1].push(2); aList[2].push(1); aList[2].push(4); aList[4].push(2); aList[1].push(3); aList[3].push(1); aList[3].push(4); aList[4].push(3); aList[3].push(5); aList[5].push(3); aList[5].push(6); aList[6].push(5); // DFS starting at Node 1 dfs(1, aList, pre, post, vis); // Number of nodes in graph for (let i = 1; i < n + 1; i++) { document.write( "Node " + i + " Pre number " + pre[i] + " Post number " + post[i] + "</br>" ) } // This code is contributed by suresh07. </script> |
Node 1 Pre number 1 Post number 12 Node 2 Pre number 2 Post number 11 Node 3 Pre number 4 Post number 9 Node 4 Pre number 3 Post number 10 Node 5 Pre number 5 Post number 8 Node 6 Pre number 6 Post number 7
Time complexity: O(V + E), where V is the number of nodes or vertices and E is the number of edges in the graph.
Auxiliary Space: O(V)