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>  usingnamespacestd;  classGraph{  public:    // instance variables    inttime= 0;    vector<int> traversal_array;    intv;    inte;    vector<vector<int>> graph_list;    vector<vector<int>> graph_matrix;      Graph(intv)    {        // 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    voidcreate_random_graph()    {        // add edges upto e        for(inti = 0; i < this->e; i++)        {            // choose src and dest of each edge randomly            intsrc = rand() % this->v;            intdest = 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    voidprint_graph_list()    {        cout << "Adjacency List Representation:"<< endl;        for(inti = 0; i < this->v; i++)        {            cout << i << "-->";            for(intj = 0; j < this->graph_list[i].size(); j++)            {                cout << this->graph_list[i][j] << " ";            }            cout << endl;        }        cout << endl;    }      // function to print adj matrix    voidprint_graph_matrix()    {        cout << "Adjacency Matrix Representation:"<< endl;        for(inti = 0; i < this->graph_matrix.size(); i++)        {            for(intj = 0; j < this->graph_matrix[i].size(); j++)            {                cout << this->graph_matrix[i][j] << " ";            }            cout << endl;        }        cout << endl;    }      // function the get number of edges    intnumber_of_edges()    {        returnthis->e;    }      // function for dfs    voiddfs()    {        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(intnode = 0; node < this->v; node++)        {            if(!this->visited[node])            {                this->traverse_dfs(node);            }        }        cout << endl;        cout << "DFS Traversal: ";        for(inti = 0; i < this->traversal_array.size(); i++)        {            cout << this->traversal_array[i] << " ";        }        cout << endl;    }      voidtraverse_dfs(intnode)    {        // 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(intneighbour = 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                elseif(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                elseif(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;};  intmain(){    srand(time(NULL));    intn = 10;    Graph g(n);    g.create_random_graph();    g.print_graph_list();    g.print_graph_matrix();    g.dfs();    return0;}  // This code is contributed by akashish__ | 
Python3
| # codeimportrandom    classGraph:    # 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_ inrange(v)]        # adj. matrix for graph        self.graph_matrix =[[0for_ inrange(v)] for_ inrange(v)]      # function to create random graph    defcreate_random_graph(self):        # add edges upto e        fori inrange(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            whilesrc ==dest andself.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    defprint_graph_list(self):        print("Adjacency List Representation:")        fori inrange(self.v):            print(i, "-->", *self.graph_list[i])        print()      # function to print adj matrix    defprint_graph_matrix(self):        print("Adjacency Matrix Representation:")        fori inself.graph_matrix:            print(i)        print()      # function the get number of edges    defnumber_of_edges(self):        returnself.e      # function for dfs    defdfs(self):        self.visited =[False]*self.v        self.start_time =[0]*self.v        self.end_time =[0]*self.v          fornode inrange(self.v):            ifnotself.visited[node]:                self.traverse_dfs(node)        print()        print("DFS Traversal: ", self.traversal_array)        print()      deftraverse_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        forneighbour inself.graph_list[node]:            # if a node is not visited            ifnotself.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                ifself.start_time[node] > self.start_time[neighbour] andself.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                elifself.start_time[node] < self.start_time[neighbour] andself.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                elifself.start_time[node] > self.start_time[neighbour] andself.end_time[node] > self.end_time[neighbour]:                    print('Cross Edge:', str(node)+'-->'+str(neighbour))            self.end_time[node] =self.time            self.time +=1    if__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() {    returnthis.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 treeelseif(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 themelseif(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 = newGraph(n);g.create_random_graph();g.print_graph_list();g.print_graph_matrix();g.dfs(); | 
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]
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

 
                                    








