Depth First Traversal for a Graph
The problem at hand involves performing Depth First Traversal (DFS) on a directed graph. DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. The goal is to visit all the vertices of the graph starting from a given vertex and to print the sequence of visited vertices.
Problem Statement
Given a directed graph, we need to implement a Depth First Traversal algorithm to traverse all its vertices starting from a specified vertex. We want to output the sequence of visited vertices in the DFS traversal.
Example Scenario
Let's consider a simple directed graph with 6 vertices numbered from 0 to 5 and the following edges:

- Vertex 0 is connected to vertices 1 and 5.
- Vertex 1 is connected to itself.
- Vertex 2 is connected to vertex 1.
- Vertex 3 is connected to itself and vertex 0.
- Vertex 4 is connected to vertices 2 and 3.
- Vertex 5 is connected to vertex 1.
Solving the Problem
To solve this problem, we need to implement the Depth First Traversal algorithm. Here's a step-by-step explanation:
Step 1: Define Graph RepresentationWe represent the graph using an adjacency list. The graph is structured as a collection of vertices, each having a data value and a linked list of adjacent nodes.
Step 2: Implement Graph CreationWe create a new graph with a specified number of vertices using the newGraph
function. This
function initializes the graph and allocates memory for vertices.
We connect the vertices by adding edges between them using the addEdge
function. This
function takes two vertices as input and creates an edge between them by updating their adjacency lists.
The DFS algorithm starts from a given vertex and explores as deeply as possible along each branch
before backtracking. We implement the dfs
function that recursively traverses the graph
using DFS. It maintains an array visit
to track visited vertices to avoid revisiting
them.
The printDFS
function initiates the DFS traversal from a specific vertex. It prints
the sequence of visited vertices during the traversal.
Pseudocode
DFS(graph, vertex, visited):
if vertex is visited:
return
mark vertex as visited
print vertex
for each adjacentNode in vertex's adjacency list:
DFS(graph, adjacentNode, visited)
PrintDFS(graph, startVertex):
initialize an array visited[] with all vertices unvisited
DFS(graph, startVertex, visited)
Algorithm Explanation
- Initialize a graph
g
using thenewGraph
function with 6 vertices. - Add the specified edges using the
addEdge
function. - Print the adjacency list of the graph using the
printGraph
function. - Call the
printDFS
function with a starting vertex (e.g., vertex 4). - The DFS traversal is initiated, and the visited vertices sequence is printed.
Code Solution
-
1) DFS traversal of directed graph in c
2) DFS traversal of directed graph in c++
3) DFS traversal of directed graph in java
4) DFS traversal of directed graph in c#
5) DFS traversal of directed graph in go
6) DFS traversal of directed graph in kotlin
7) DFS traversal of directed graph in swift
8) DFS traversal of directed graph in scala
9) DFS traversal of directed graph in ruby
10) DFS traversal of directed graph in python
11) DFS traversal of directed graph in TypeScript
12) DFS traversal of directed graph in node js
13) DFS traversal of directed graph in php
14) DFS traversal of directed graph in vb.net
Resultant Output Explanation
The adjacency lists of the graph are printed first, showing which vertices are connected to each vertex. Then, the DFS traversal is performed starting from vertex 4. The visited vertices sequence is printed as 4 -> 2 -> 1 -> 3 -> 0 -> 5.
Time Complexity
The time complexity of DFS traversal in a graph depends on the number of vertices and edges. In the worst case, where all vertices and edges are explored, the time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment