Parenthesis Theorem is used in DFS of graph. It states that the descendants in a depth-first-search tree have an interesting property. If v is a descendant of u, then the discovery time of v is later than the discovery time of u.
In any DFS traversal of a graph g = (V, E), for any two vertices u and v exactly one of the following holds:
- The intervals [d[u], f[u]] and [d[v], f[v]] are entirely disjoint and neither u nor v is a descendant of the other in the depth-first forest.
- The interval [d[u], f[u]] is contained within the interval [d[v], f[v]], and u is a descendant of v in a depth-first tree.
- The interval [d[v], f[v]] is contained entirely within the interval [d[u], f[u]], and v is a descendant of u in a depth-first tree.
Classification of Edges:
DFS traversal can be used to classify the edges of input graph G=(V, E). Four edge types can be defined in terms of a depth-first forest:
- Tree Edge: It is an edge that is present in the tree obtained after applying DFS on the graph.
- Forward Edge: It is an edge (u, v) such that v is descendant but not part of the DFS tree.
- Back edge: It is an edge (u, v) such that v is the ancestor of edge u but not part of the DFS tree. The presence of the back edge indicates a cycle in a directed graph.
- Cross Edge: It is an edge that connects two-node such that they do not have any ancestor and a descendant relationship between them.
Given a graph of N vertices and M Edges, the task is to classify the M edges into Tree edges, Forward edges, Backward edges and Cross edges.
Examples:
Input: N = 5, M = 7, arr[][] = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 1, 4 }, { 2, 5 }, { 5, 1 }, { 3, 2 } } }
Output:
{1, 2} -> Tree Edge
{1, 3} -> Tree Edge
{3, 4} -> Tree Edge
{1, 4} -> Forward Edge
{2, 5} -> Tree Edge
{5, 1} -> Backward Edge
{3, 2} -> Cross Edge
Explanation:
1. Green Edges: Tree Edge
2. Blue Edges: Forward Edge
3. Black Edges: Backward Edge
4. Red Edges: Cross Edge
Below is the given graph for the above information:
Input: N = 5, M = 4, arr[][] = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 1, 4 } }
Output:
{1, 2} -> Tree Edge
{1, 3} -> Tree Edge
{3, 4} -> Tree Edge
{1, 4} -> Forward Edge
Explanation:
1. Green Edges: Tree Edge
2. Blue Edges: Forward Edge
3. Black Edges: Backward Edge
4. Red Edges: Cross Edge
Below is the given graph for the above information:
Approach:
- Use DFS Traversal on the given graph to find discovery time and finishing time and parent of each node.
- By using Parenthesis Theorem classify the given edges on the below conditions:
- Tree Edge: For any Edge (U, V), if node U is the parent of node V, then (U, V) is the Tree Edge of the given graph.
- Forward Edge: For any Edge (U, V), if discovery time and finishing time of node V fully overlaps with discovery time and finishing time of node U, then (U, V) is the Forward Edge of the given graph.
- Backward Edge: For any Edge (U, V), if discovery time and finishing time of node U fully overlaps with discovery time and finishing time of node V, then (U, V) is the Backward Edge of the given graph.
- Cross Edge: For any Edge (U, V), if discovery time and finishing time of node U doesn’t overlaps with discovery time and finishing time of node V, then (U, V) is the Cross Edge of the given graph.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include "bits/stdc++.h"using namespace std;// For recording timeint tim = 0;// For creating Graphvector<list<int> > G;// For calculating Discovery time// and finishing time of nodesvector<int> disc, fin;// For finding Parent of nodevector<int> Par;// For storing color of nodevector<char> Color;// Recursive function for DFS// to update thevoid DFS_Visit(int v){ // Make the current nodes as visited Color[v] = 'G'; // Increment the time tim = tim + 1; // Assign the Discovery node of // node v disc[v] = tim; // Traverse the adjacency list of // vertex v for (auto& it : G[v]) { // If the nodes is not visited, // then mark the parent of the // current node and call DFS_Visit // for the current node if (Color[it] == 'W') { Par[it] = v; DFS_Visit(it); } } Color[v] = 'B'; tim = tim + 1; fin[v] = tim;}void DFS(vector<list<int> >& G){ // Initialise Par, disc, fin and // Color vector to size of graph Par.resize(G.size()); disc.resize(G.size()); fin.resize(G.size()); Color.resize(G.size()); // Initialise the Par[], Color[], // disc[], fin[] for (int i = 1; i < G.size(); i++) { Color[i] = 'W'; Par[i] = 0; disc[i] = 0; fin[i] = 0; } // For every vertex if nodes is // not visited then call DFS_Visit // to update the discovery and // finishing time of the node for (int i = 1; i < G.size(); i++) { // If color is 'W', then // node is not visited if (Color[i] == 'W') { DFS_Visit(i); } }}// Function to check whether// time intervals of x and y overlaps// or notbool checkOverlap(int x, int y){ // Find the time intervals int x1 = disc[x], y1 = fin[x]; int x2 = disc[y], y2 = fin[y]; // Complete overlaps if (x2 > x1 && y1 > y2) { return true; } else { return false; }}// Function to check which Edges// (x, y) belongsstring checkEdge(int x, int y){ // For Tree Edge // If x is parent of y, then it // is Tree Edge if (Par[y] == x) { return "Tree Edge"; } // For Forward Edge else if (checkOverlap(x, y)) { return "Forward Edge"; } // For Backward Edge else if (checkOverlap(y, x)) { return "Backward Edge"; } else { return "Cross Edge"; }}// Function call to find the Tree Edge,// Back Edge, Forward Edge, and Cross Edgevoid solve(int arr[][2], int N, int M){ // Create graph of N size G.resize(N + 1); // Traverse each edges for (int i = 0; i < M; i++) { int x = arr[i][0]; int y = arr[i][1]; // Make Directed graph G[x].push_back(y); } // DFS call to calculate discovery // and finishing time for each node DFS(G); // Condition for Tree Edge, Forward // Edges, Backward Edge and Cross Edge for (int i = 0; i < M; i++) { int x = arr[i][0]; int y = arr[i][1]; // Function call to check Edges cout << "{" << x << ", " << y << "} -> " << checkEdge(x, y) << endl; }}// Driver Codeint main(){ // Number of Nodes int N = 5; // Number of Edges int M = 7; // Edges for the graph int arr[M][2] = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 1, 4 }, { 2, 5 }, { 5, 1 }, { 3, 1 } }; // Function Call solve(arr, N, M); return 0;} |
Java
import java.util.*;public class Main { // For recording time static int tim = 0; // For creating Graph static ArrayList<Integer>[] G; // For calculating Discovery time and finishing time of nodes static int[] disc, fin; // For finding Parent of node static int[] Par; // For storing color of node static char[] Color; // Recursive function for DFS to update the static void DFS_Visit(int v) { // Make the current nodes as visited Color[v] = 'G'; // Increment the time tim += 1; // Assign the Discovery node of node v disc[v] = tim; // Traverse the adjacency list of vertex v for(int i = 0; i < G[v].size(); i++) { int it = G[v].get(i); // If the nodes is not visited, then mark the parent of the current node and call DFS_Visit for the current node if(Color[it] == 'W') { Par[it] = v; DFS_Visit(it); } } Color[v] = 'B'; tim = tim + 1; fin[v] = tim; } static void DFS(ArrayList<Integer>[] graph) { // Initialise Par, disc, fin and Color vector to size of graph Par = new int[graph.length]; disc = new int[graph.length]; fin = new int[graph.length]; Color = new char[graph.length]; // Initialise the Par[], Color[], disc[], fin[] for (int i = 1; i < graph.length; i++) { Color[i] = 'W'; Par[i] = 0; disc[i] = 0; fin[i] = 0; } // For every vertex if nodes is not visited then call DFS_Visit to update the discovery and finishing time of the node for (int i = 1; i < graph.length; i++) { // If color is 'W', then node is not visited if (Color[i] == 'W') { DFS_Visit(i); } } } // Function to check whether time intervals of x and y overlaps or not static boolean checkOverlap(int x, int y) { // Find the time intervals int x1 = disc[x], y1 = fin[x]; int x2 = disc[y], y2 = fin[y]; // Complete overlaps if (x2 > x1 && y1 > y2) { return true; } else { return false; } } // Function to check which Edges (x, y) belongs static String checkEdge(int x, int y) { // For Tree Edge If x is parent of y, then it is Tree Edge if (Par[y] == x) { return "Tree Edge"; } // For Forward Edge else if (checkOverlap(x, y)) { return "Forward Edge"; } // For Backward Edge else if (checkOverlap(y, x)) { return "Backward Edge"; } else { return "Cross Edge"; } } // Function call to find the Tree Edge, Back Edge, Forward Edge, and Cross Edge static void solve(int[][] arr, int N, int M) { // Create graph of G = new ArrayList[N + 1]; for (int i = 0; i < N + 1; i++) { G[i] = new ArrayList<Integer>(); } // Traverse each edges for (int i = 0; i < M; i++) { int x = arr[i][0]; int y = arr[i][1]; // Make Directed graph G[x].add(y); } // DFS call to calculate discovery and finishing time for each node DFS(G); // Condition for Tree Edge, Forward Edges, Backward Edge and Cross Edge for (int i = 0; i < M; i++) { int x = arr[i][0]; int y = arr[i][1]; // Function call to check Edges System.out.println("(" + x + "," + y + ")->" + checkEdge(x, y)); } } public static void main(String[] args) { // Number of Nodes int N = 5; // Number of Edges int M = 7; // Edges for the graph int[][] arr= {{1, 2} , {1, 3 }, {3, 4} , {1, 4 }, {2, 5} , {5, 1 }, {3, 1}}; // Function Call solve(arr, N, M); }} |
Python3
# Python3 program for the above approach For recording timetim = 0# For creating GraphG=[]# For calculating Discovery time and finishing time of nodesdisc, fin=[],[]# For finding Parent of nodePar=[]# For storing color of nodeColor=[]# Recursive function for DFS to update thedef DFS_Visit(v): global tim # Make the current nodes as visited Color[v] = 'G' # Increment the time tim += 1 # Assign the Discovery node of node v disc[v] = tim # Traverse the adjacency list of vertex v for it in G[v]: # If the nodes is not visited, then mark the parent of the current node and call DFS_Visit for the current node if (Color[it] == 'W') : Par[it] = v DFS_Visit(it) Color[v] = 'B' tim = tim + 1 fin[v] = timdef DFS(G): global Par,disc,fin,Color # Initialise Par, disc, fin and Color vector to size of graph Par=[-1]*len(G) disc=[-1]*len(G) fin=[-1]*len(G) Color=['']*len(G) # Initialise the Par[], Color[], disc[], fin[] for i in range(1,len(G)): Color[i] = 'W' Par[i] = 0 disc[i] = 0 fin[i] = 0 # For every vertex if nodes is not visited then call DFS_Visit to update the discovery and finishing time of the node for i in range(1,len(G)): # If color is 'W', then node is not visited if (Color[i] == 'W') : DFS_Visit(i)# Function to check whether time intervals of x and y overlaps or notdef checkOverlap(x, y): # Find the time intervals x1 = disc[x]; y1 = fin[x] x2 = disc[y]; y2 = fin[y] # Complete overlaps if (x2 > x1 and y1 > y2) : return True else : return False# Function to check which Edges (x, y) belongsdef checkEdge(x, y): # For Tree Edge If x is parent of y, then it is Tree Edge if (Par[y] == x) : return "Tree Edge" # For Forward Edge elif (checkOverlap(x, y)) : return "Forward Edge" # For Backward Edge elif (checkOverlap(y, x)) : return "Backward Edge" else : return "Cross Edge" # Function call to find the Tree Edge, Back Edge, Forward Edge, and Cross Edgedef solve(arr, N, M): global G # Create graph of N size G=[[] for _ in range(N + 1)] # Traverse each edges for i in range(M): x = arr[i][0] y = arr[i][1] # Make Directed graph G[x].append(y) # DFS call to calculate discovery and finishing time for each node DFS(G) # Condition for Tree Edge, Forward Edges, Backward Edge and Cross Edge for i in range(M): x = arr[i][0] y = arr[i][1] # Function call to check Edges print("({0},{1})->".format(x,y),checkEdge(x, y))# Driver Codeif __name__ == '__main__': # Number of Nodes N = 5 # Number of Edges M = 7 # Edges for the graph arr= [[1, 2] , [1, 3 ], [3, 4] , [1, 4 ], [2, 5] , [5, 1 ], [3, 1]] # Function Call solve(arr, N, M) |
Javascript
// For recording timelet tim = 0;// For creating Graphlet G = [];// For calculating Discovery time// and finishing time of nodeslet disc = [];let fin = [];// For finding Parent of nodelet Par = [];// For storing color of nodelet Color = [];// Recursive function for DFS// to update thefunction DFS_Visit(v) { // Make the current nodes as visited Color[v] = "G"; // Increment the time tim++; // Assign the Discovery node of // node v disc[v] = tim; // Traverse the adjacency list of // vertex v for (let it of G[v]) { // If the nodes is not visited, // then mark the parent of the // current node and call DFS_Visit // for the current node if (Color[it] === "W") { Par[it] = v; DFS_Visit(it); } } Color[v] = "B"; tim = tim + 1; fin[v] = tim;}function DFS(G) { // Initialise Par, disc, fin and // Color vector to size of graph Par = Array(G.length).fill(-1); disc = Array(G.length).fill(-1); fin = Array(G.length).fill(-1); Color = Array(G.length).fill(""); // Initialise the Par[], Color[], // disc[], fin[] for (let i = 1; i < G.length; i++) { Color[i] = "W"; Par[i] = 0; disc[i] = 0; fin[i] = 0; } // For every vertex if nodes is // not visited then call DFS_Visit // to update the discovery and // finishing time of the node for (let i = 1; i < G.length; i++) { // If color is 'W', then // node is not visited if (Color[i] === "W") { DFS_Visit(i); } }}// Function to check whether// time intervals of x and y overlaps// or notfunction checkOverlap(x, y) { // Find the time intervals let x1 = disc[x]; let y1 = fin[x]; let x2 = disc[y]; let y2 = fin[y]; // Complete overlaps if (x2 > x1 && y1 > y2) { return true; } else { return false; }}// Function to check whether// time intervals of x and y overlaps// or notfunction checkOverlap(x, y) { // Find the time intervals const x1 = disc[x]; const y1 = fin[x]; const x2 = disc[y]; const y2 = fin[y]; // Complete overlaps if (x2 > x1 && y1 > y2) { return true; } else { return false; }}// Function to check which Edges (x, y) belongsfunction checkEdge(x, y) { // For Tree Edge // If x is parent of y, then it // is Tree Edge if (Par[y] === x) { return "Tree Edge"; } // For Forward Edge else if (checkOverlap(x, y)) { return "Forward Edge"; } // For Backward Edge else if (checkOverlap(y, x)) { return "Backward Edge"; } else { return "Cross Edge"; }}// Function call to find the Tree Edge, Back Edge, Forward Edge, and Cross Edgefunction solve(arr, N, M) { // Create graph of N size G = Array.from({length: N + 1}, () => []); // Traverse each edges for (let i = 0; i < M; i++) { let x = arr[i][0]; let y = arr[i][1]; // Make Directed graph G[x].push(y); } // DFS call to calculate discovery and finishing time for each node DFS(G); // Condition for Tree Edge, Forward Edges, Backward Edge and Cross Edge for (let i = 0; i < M; i++) { let x = arr[i][0]; let y = arr[i][1]; // Function call to check Edges console.log(`(${x},${y})->`, checkEdge(x, y)); }}// Driver code // Number of Nodes let N = 5; // Number of Edges let M = 7; // Edges for the graph let arr = [[1, 2], [1, 3], [3, 4], [1, 4], [2, 5], [5, 1], [3, 1]]; // Function call solve(arr, N, M); |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG {// For recording timestatic int tim = 0;// For creating Graphstatic List<int>[] G;// For calculating Discovery time// and finishing time of nodesstatic int[] disc, fin;// For finding Parent of nodestatic int[] Par;// For storing color of nodestatic char[] Color;// Recursive function for DFS// to update thestatic void DFS_Visit(int v) { // Make the current nodes as visited Color[v] = 'G'; // Increment the time tim += 1; // Assign the Discovery node of // node v disc[v] = tim; // Traverse the adjacency list of // vertex v for (int i = 0; i < G[v].Count; i++) { int it = G[v][i]; // If the nodes is not visited, // then mark the parent of the // current node and call DFS_Visit // for the current node if (Color[it] == 'W') { Par[it] = v; DFS_Visit(it); } } Color[v] = 'B'; tim = tim + 1; fin[v] = tim;}static void DFS(List<int>[] graph) { // Initialise Par, disc, fin and // Color vector to size of graph Par = new int[graph.Length]; disc = new int[graph.Length]; fin = new int[graph.Length]; Color = new char[graph.Length]; // Initialise the Par[], Color[], // disc[], fin[] for (int i = 1; i < graph.Length; i++) { Color[i] = 'W'; Par[i] = 0; disc[i] = 0; fin[i] = 0; } // For every vertex if nodes is // not visited then call DFS_Visit // to update the discovery and // finishing time of the node for (int i = 1; i < graph.Length; i++) { // If color is 'W', then // node is not visited if (Color[i] == 'W') { DFS_Visit(i); } }}// Function to check whether// time intervals of x and y overlaps// or notstatic bool checkOverlap(int x, int y) { int x1 = disc[x], y1 = fin[x]; int x2 = disc[y], y2 = fin[y]; if (x2 > x1 && y1 > y2) { return true; } else { return false; }}// Function to check which Edges// (x, y) belongsstatic string checkEdge(int x, int y) { // For Tree Edge // If x is parent of y, then it // is Tree Edge if (Par[y] == x) { return "Tree Edge"; } // For Forward Edge else if (checkOverlap(x, y)) { return "Forward Edge"; } // For Backward Edge else if (checkOverlap(y, x)) { return "Backward Edge"; } //// For Cross Edge else { return "Cross Edge"; }}// Function to check which Edges// (x, y) belongsstatic void solve(int[][] arr, int N, int M) { // Create graph of N size G = new List<int>[N + 1]; for (int i = 0; i < N + 1; i++) { G[i] = new List<int>(); } for (int i = 0; i < M; i++) { int x = arr[i][0]; int y = arr[i][1]; G[x].Add(y); } // DFS call to calculate discovery // and finishing time for each node DFS(G); for (int i = 0; i < M; i++) { int x = arr[i][0]; int y = arr[i][1]; Console.WriteLine("(" + x + "," + y + ")->" + checkEdge(x, y)); }}//Driver codepublic static void Main(string[] args) { int N = 5; int M = 7; int[][] arr = new int[][]{ new int[]{1, 2}, new int[] {1, 3}, new int[] {3, 4}, new int[]{1, 4}, new int[] {2, 5}, new int[] {5, 1}, new int[]{3, 1} }; solve(arr, N, M);}} |
Output:
{1, 2} -> Tree Edge
{1, 3} -> Tree Edge
{3, 4} -> Tree Edge
{1, 4} -> Forward Edge
{2, 5} -> Tree Edge
{5, 1} -> Backward Edge
{3, 1} -> Backward Edge
Time Complexity: O(N), Where N is the total number of nodes in the graph.
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!
