Consider a directed graph given in below, DFS of the below graph is 1 2 4 6 3 5 7 8. In below diagram if DFS is applied on this graph a tree is obtained which is connected using green edges.
- Tree Edge: It is an edge which is present in the tree obtained after applying DFS on the graph. All the Green edges are tree edges.
- Forward Edge: It is an edge (u, v) such that v is a descendant but not part of the DFS tree. An edge from 1 to 8 is a forward edge.
- Back edge: It is an edge (u, v) such that v is the ancestor of node u but is not part of the DFS tree. Edge from 6 to 2 is a back edge. Presence of back edge indicates a cycle in directed graph.
- Cross Edge: It is an edge that connects two nodes such that they do not have any ancestor and a descendant relationship between them. The edge from node 5 to 4 is a cross edge.
Time Complexity(DFS):
Since all the nodes and vertices are visited, the average time complexity for DFS on a graph is O(V + E), where V is the number of vertices and E is the number of edges. In case of DFS on a tree, the time complexity is O(V), where V is the number of nodes.
Algorithm(DFS):
- Pick any node. If it is unvisited, mark it as visited and recur on all its adjacent nodes.
- Repeat until all the nodes are visited, or the node to be searched is found.
Example: Implement DFS using an adjacency list take a directed graph of size n=10, and randomly select the number of edges in the graph varying from 9 to 45. Identify each edge as the forwarding edge, tree edge, back edge, and cross edge.
C++
// C++#include <bits/stdc++.h>#include <cstdlib>#include <ctime>using namespace std;class Graph{public: // instance variables int time = 0; vector<int> traversal_array; int v; int e; vector<vector<int>> graph_list; vector<vector<int>> graph_matrix; Graph(int v) { // v is the number of nodes/vertices this->v = v; // e is the number of edge (randomly chosen between 9 to 45) this->e = rand() % (45 - 9 + 1) + 9; // adj. list for graph this->graph_list.resize(v); // adj. matrix for graph this->graph_matrix.resize(v, vector<int>(v, 0)); } // function to create random graph void create_random_graph() { // add edges upto e for (int i = 0; i < this->e; i++) { // choose src and dest of each edge randomly int src = rand() % this->v; int dest = rand() % this->v; // re-choose if src and dest are same or src and dest already has an edge while (src == dest && this->graph_matrix[src][dest] == 1) { src = rand() % this->v; dest = rand() % this->v; } // add the edge to graph this->graph_list[src].push_back(dest); this->graph_matrix[src][dest] = 1; } } // function to print adj list void print_graph_list() { cout << "Adjacency List Representation:" << endl; for (int i = 0; i < this->v; i++) { cout << i << "-->"; for (int j = 0; j < this->graph_list[i].size(); j++) { cout << this->graph_list[i][j] << " "; } cout << endl; } cout << endl; } // function to print adj matrix void print_graph_matrix() { cout << "Adjacency Matrix Representation:" << endl; for (int i = 0; i < this->graph_matrix.size(); i++) { for (int j = 0; j < this->graph_matrix[i].size(); j++) { cout << this->graph_matrix[i][j] << " "; } cout << endl; } cout << endl; } // function the get number of edges int number_of_edges() { return this->e; } // function for dfs void dfs() { this->visited.resize(this->v); this->start_time.resize(this->v); this->end_time.resize(this->v); fill(this->visited.begin(), this->visited.end(), false); for (int node = 0; node < this->v; node++) { if (!this->visited[node]) { this->traverse_dfs(node); } } cout << endl; cout << "DFS Traversal: "; for (int i = 0; i < this->traversal_array.size(); i++) { cout << this->traversal_array[i] << " "; } cout << endl; } void traverse_dfs(int node) { // mark the node visited this->visited[node] = true; // add the node to traversal this->traversal_array.push_back(node); // get the starting time this->start_time[node] = this->time; // increment the time by 1 this->time++; // traverse through the neighbours for (int neighbour = 0; neighbour < this->graph_list[node].size(); neighbour++) { // if a node is not visited if (!this->visited[this->graph_list[node][neighbour]]) { // marks the edge as tree edge cout << "Tree Edge:" << node << "-->" << this->graph_list[node][neighbour] << endl; // dfs from that node this->traverse_dfs(this->graph_list[node][neighbour]); } else { // when the parent node is traversed after the neighbour node if (this->start_time[node] > this->start_time[this->graph_list[node][neighbour]] && this->end_time[node] < this->end_time[this->graph_list[node][neighbour]]) { cout << "Back Edge:" << node << "-->" << this->graph_list[node][neighbour] << endl; } // when the neighbour node is a descendant but not a part of tree else if (this->start_time[node] < this->start_time[this->graph_list[node][neighbour]] && this->end_time[node] > this->end_time[this->graph_list[node][neighbour]]) { cout << "Forward Edge:" << node << "-->" << this->graph_list[node][neighbour] << endl; } // when parent and neighbour node do not have any ancestor and a descendant relationship between them else if (this->start_time[node] > this->start_time[this->graph_list[node][neighbour]] && this->end_time[node] > this->end_time[this->graph_list[node][neighbour]]) { cout << "Cross Edge:" << node << "-->" << this->graph_list[node][neighbour] << endl; } } this->end_time[node] = this->time; this->time++; } }private: vector<bool> visited; vector<int> start_time; vector<int> end_time;};int main(){ srand(time(NULL)); int n = 10; Graph g(n); g.create_random_graph(); g.print_graph_list(); g.print_graph_matrix(); g.dfs(); return 0;}// This code is contributed by akashish__ |
Python3
# codeimport randomclass Graph: # instance variables def __init__(self, v): # v is the number of nodes/vertices self.time = 0 self.traversal_array = [] self.v = v # e is the number of edge (randomly chosen between 9 to 45) self.e = random.randint(9, 45) # adj. list for graph self.graph_list = [[] for _ in range(v)] # adj. matrix for graph self.graph_matrix = [[0 for _ in range(v)] for _ in range(v)] # function to create random graph def create_random_graph(self): # add edges upto e for i in range(self.e): # choose src and dest of each edge randomly src = random.randrange(0, self.v) dest = random.randrange(0, self.v) # re-choose if src and dest are same or src and dest already has an edge while src == dest and self.graph_matrix[src][dest] == 1: src = random.randrange(0, self.v) dest = random.randrange(0, self.v) # add the edge to graph self.graph_list[src].append(dest) self.graph_matrix[src][dest] = 1 # function to print adj list def print_graph_list(self): print("Adjacency List Representation:") for i in range(self.v): print(i, "-->", *self.graph_list[i]) print() # function to print adj matrix def print_graph_matrix(self): print("Adjacency Matrix Representation:") for i in self.graph_matrix: print(i) print() # function the get number of edges def number_of_edges(self): return self.e # function for dfs def dfs(self): self.visited = [False]*self.v self.start_time = [0]*self.v self.end_time = [0]*self.v for node in range(self.v): if not self.visited[node]: self.traverse_dfs(node) print() print("DFS Traversal: ", self.traversal_array) print() def traverse_dfs(self, node): # mark the node visited self.visited[node] = True # add the node to traversal self.traversal_array.append(node) # get the starting time self.start_time[node] = self.time # increment the time by 1 self.time += 1 # traverse through the neighbours for neighbour in self.graph_list[node]: # if a node is not visited if not self.visited[neighbour]: # marks the edge as tree edge print('Tree Edge:', str(node)+'-->'+str(neighbour)) # dfs from that node self.traverse_dfs(neighbour) else: # when the parent node is traversed after the neighbour node if self.start_time[node] > self.start_time[neighbour] and self.end_time[node] < self.end_time[neighbour]: print('Back Edge:', str(node)+'-->'+str(neighbour)) # when the neighbour node is a descendant but not a part of tree elif self.start_time[node] < self.start_time[neighbour] and self.end_time[node] > self.end_time[neighbour]: print('Forward Edge:', str(node)+'-->'+str(neighbour)) # when parent and neighbour node do not have any ancestor and a descendant relationship between them elif self.start_time[node] > self.start_time[neighbour] and self.end_time[node] > self.end_time[neighbour]: print('Cross Edge:', str(node)+'-->'+str(neighbour)) self.end_time[node] = self.time self.time += 1if __name__ == "__main__": n = 10 g = Graph(n) g.create_random_graph() g.print_graph_list() g.print_graph_matrix() g.dfs() |
Javascript
class Graph{ // instance variables constructor(v) { // v is the number of nodes/vertices this.time = 0; this.traversal_array = []; this.v = v; // e is the number of edge (randomly chosen between 9 to 45) this.e = Math.floor(Math.random() * (45 - 9 + 1)) + 9; // adj. list for graph this.graph_list = Array.from({ length: v }, () => []); // adj. matrix for graph this.graph_matrix = Array.from({ length: v }, () => Array.from({ length: v }, () => 0) ); } // function to create random graph create_random_graph() { // add edges upto e for (let i = 0; i < this.e; i++) { // choose src and dest of each edge randomly // choose src and dest of each edge randomly let src = Math.floor(Math.random() * this.v); let dest = Math.floor(Math.random() * this.v); // re-choose if src and dest are same or src and dest already has an edge while (src === dest || this.graph_matrix[src][dest] === 1) { src = Math.floor(Math.random() * this.v); dest = Math.floor(Math.random() * this.v); } // add the edge to graph this.graph_list[src].push(dest); this.graph_matrix[src][dest] = 1; } } // function to print adj list print_graph_list() { console.log("Adjacency List Representation:"+"<br>"); for (let i = 0; i < this.v; i++) { console.log(i, "-->", ...this.graph_list[i]); } console.log("<br>"); } // function to print adj matrix print_graph_matrix() { console.log("Adjacency Matrix Representation:"+"<br>"); for (let i = 0; i < this.graph_matrix.length; i++) { console.log(this.graph_matrix[i]); } console.log("<br>"); } // function the get number of edges number_of_edges() { return this.e; } // function for dfs dfs() { this.visited = Array.from({ length: this.v }, () => false); this.start_time = Array.from({ length: this.v }, () => 0); this.end_time = Array.from({ length: this.v }, () => 0); for (let node = 0; node < this.v; node++) { if (!this.visited[node]) { this.traverse_dfs(node); } } console.log(); console.log("DFS Traversal: ", this.traversal_array+"<br>"); console.log(); }// function to traverse the graph using DFStraverse_dfs(node) {// mark the node as visitedthis.visited[node] = true;// add the node to the traversal arraythis.traversal_array.push(node);// get the starting time for the nodethis.start_time[node] = this.time;// increment the time by 1this.time += 1;// loop through the neighbours of the nodefor (let i = 0; i < this.graph_list[node].length; i++){let neighbour = this.graph_list[node][i];// if the neighbour node is not visitedif (!this.visited[neighbour]){// mark the edge as a tree edgeconsole.log("Tree Edge: " + node + "-->" + neighbour+"<br>");// traverse through the neighbour nodethis.traverse_dfs(neighbour);} else {// if parent node is traversed after the neighbour nodeif (this.start_time[node] >this.start_time[neighbour] &&this.end_time[node] < this.end_time[neighbour]) {console.log("Back Edge: " + node + "-->" + neighbour+"<br>");}// if the neighbour node is a descendant but not a part of the treeelse if (this.start_time[node] <this.start_time[neighbour] &&this.end_time[node] > this.end_time[neighbour]) {console.log("Forward Edge: " + node + "-->" + neighbour+"<br>");}// if parent and neighbour node do not // have any ancestor and descendant relationship between themelse if (this.start_time[node] >this.start_time[neighbour] &&this.end_time[node] > this.end_time[neighbour]) {console.log("Cross Edge: " + node + "-->" + neighbour+"<br>");}}}// get the ending time for the nodethis.end_time[node] = this.time;// increment the time by 1this.time += 1;}}// mainconst n = 10;const g = new Graph(n);g.create_random_graph();g.print_graph_list();g.print_graph_matrix();g.dfs(); |
Output
Adjacency List Representation: 0 --> 5 1 --> 3 7 2 --> 4 3 8 9 3 --> 3 4 --> 0 5 --> 2 0 6 --> 0 7 --> 7 4 3 8 --> 8 9 9 --> 9 Adjacency Matrix Representation: [0, 0, 0, 0, 0, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0, 0, 1, 0, 0] [0, 0, 0, 1, 1, 0, 0, 0, 1, 1] [0, 0, 0, 1, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 0, 1, 0, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 1, 1, 0, 0, 1, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 1, 1] [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] Tree Edge: 0-->5 Tree Edge: 5-->2 Tree Edge: 2-->4 Tree Edge: 2-->3 Tree Edge: 2-->8 Tree Edge: 8-->9 Forward Edge: 2-->9 Cross Edge: 5-->0 Back Edge: 1-->3 Tree Edge: 1-->7 Cross Edge: 7-->4 Cross Edge: 7-->3 Back Edge: 6-->0 DFS Traversal: [0, 5, 2, 4, 3, 8, 9, 1, 7, 6]
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!
