Data Modelling & AI Data Structure & Algorithm

Tree, Back, Edge and Cross Edges in DFS of Graph

20 June 2025

1

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

# code
import random
 
 
class 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 += 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() {
    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 DFS
traverse_dfs(node) 
{
 
// mark the node as visited
this.visited[node] = true;
 
// add the node to the traversal array
this.traversal_array.push(node);
 
// get the starting time for the node
this.start_time[node] = this.time;
 
// increment the time by 1
this.time += 1;
 
// loop through the neighbours of the node
for (let i = 0; i < this.graph_list[node].length; i++)
{
let neighbour = this.graph_list[node][i];
 
// if the neighbour node is not visited
if (!this.visited[neighbour])
{
 
// mark the edge as a tree edge
console.log("Tree Edge: " + node + "-->" + neighbour+"<br>");
 
// traverse through the neighbour node
this.traverse_dfs(neighbour);
} else {
 
// if parent node is traversed after the neighbour node
if (
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 tree
else 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 them
else 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 node
this.end_time[node] = this.time;
 
// increment the time by 1
this.time += 1;
}
 
}
 
// main
const 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]

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Tree, Back, Edge and Cross Edges in DFS of Graph

C++

Python3

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

This is how Google Maps will use Gemini during navigation

The Pixel 10 Pro Fold tips the scales on the Android Police podcast

One UI 8.5 will bring big lock screen customization upgrades

Google is developing a Messages feature aimed at saving your time

EDITOR PICKS

This is how Google Maps will use Gemini during navigation

The Pixel 10 Pro Fold tips the scales on the Android Police podcast

One UI 8.5 will bring big lock screen customization upgrades

POPULAR POSTS

This is how Google Maps will use Gemini during navigation

The Pixel 10 Pro Fold tips the scales on the Android Police podcast

One UI 8.5 will bring big lock screen customization upgrades

POPULAR CATEGORY

ABOUT US

FOLLOW US