Posted on by Kalkicode
Code Graph

# Print the DFS traversal step wise

Graph traversal is a fundamental concept in computer science and is used to explore and analyze relationships between various entities. Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along a branch before backtracking. This article provides a detailed explanation of DFS traversal, step by step, using a C code implementation as an example.

## Problem Statement

The problem at hand is to implement and illustrate the Depth-First Search traversal algorithm for a given graph. The graph is represented as an adjacency list, and the goal is to traverse the graph in a depth-first manner, visiting all nodes and displaying the traversal steps.

## Description with Example

Consider a scenario where we have a graph with vertices representing different locations, and edges representing connections between these locations. We want to explore this graph using DFS traversal to find a path that visits each location while following the edges. Let's visualize this graph: ## Idea to Solve

The DFS traversal algorithm can be solved using recursion. Starting from a source vertex, we visit an unvisited adjacent vertex and continue this process until all vertices are visited. We maintain an array to keep track of visited vertices and print each vertex as we visit it.

## Pseudocode

``````function DFS(graph, vertex, visited):
if visited[vertex] is true:
return
print vertex
visited[vertex] = true

## Algorithm Explanation

1. Initialize an array `visited` of size `n` (number of vertices) with all elements set to `false`.
2. Start DFS traversal from vertex `0` and call the DFS function.
3. Inside the DFS function: a. Check if the current vertex is already visited. If yes, return. b. Print the current vertex. c. Mark the current vertex as visited. d. Iterate through each adjacent vertex of the current vertex:
• Recursively call the DFS function for unvisited adjacent vertices.

## Program Solution

``````// C Program
// Print the DFS traversal step wise
#include <stdio.h>

#include <stdlib.h>

// Define edge of graph node
struct AjlistNode
{
int id; //Vertices id
struct AjlistNode *next;
};
// Define node of graph
struct GraphNode
{
int data; //node key value
struct AjlistNode *edge;
};
// Define structure of graph
struct MyGraph
{
int size; // Number of graph nodes
struct GraphNode *node;
};
// This are return a new graph with given number of nodes
struct MyGraph *newGraph(int size)
{
if (size < 0)
{
printf("\n Invalid size of nodes %d \n", size);
return NULL;
}
// Create a graph
struct MyGraph *graph = (struct MyGraph *) malloc(sizeof(struct MyGraph));
if (graph != NULL)
{
// Set node size
graph->size = size;
// Allocate memory to graph node
graph->node = (struct GraphNode *) malloc(sizeof(struct GraphNode) *size);
// Loop controlling variable
int i = 0;
// Set graph node level and e
for (i = 0; i < graph->size; i++)
{
// Set node level (0...size-1)
graph->node[i].data = i;
// Set the node [i] have no edge
graph->node[i].edge = NULL;
}
}
else
{
printf("\n Graph of nodes %d is not created (memory overflow problem)\n", size);
}
return graph;
}
//This function are connect nodes with one edge
void connect_edge(struct MyGraph *graph, int a, int b)
{
if (graph->node == NULL)
{
printf("\n Graph have no nodes \n");
return;
}
struct AjlistNode *newEdge = (struct AjlistNode *) malloc(sizeof(struct AjlistNode));
if (newEdge != NULL)
{
newEdge->next = NULL;
newEdge->id = b;
// Get first edge of [i] node
struct AjlistNode *edge = graph->node[a].edge;
if (edge == NULL)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
graph->node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge->next != NULL)
{
edge = edge->next;
}
// Add edge at last position
edge->next = newEdge;
}
}
else
{
printf("\nMemory overflow, when connect a new edge from ( %d to %d ) nodes.\n", a, b);
}
}
// This is handles the request of connecting Edges between given node a to b
void add_edge(struct MyGraph *graph, int a, int b)
{
if (a < graph->size && b < graph->size)
{
// connect edge
// a---->b
connect_edge(graph, a, b);
if (a == b)
{
//self loop
return;
}
// connect edge
// a <---- b
connect_edge(graph, b, a);
}
else
{
//not valid Vertices
printf("Invalid Node Vertices %d  %d", a, b);
}
}
void print_graph(struct MyGraph *graph)
{
if (graph->node != NULL)
{
struct AjlistNode *temp = NULL;
// Loop controlling variable
int i = 0;
for (i = 0; i < graph->size; i++)
{
printf("\n Adjacency list of vertex %d  :", i);
// Get first edge of [i] node
temp = graph->node[i].edge;
while (temp != NULL)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
printf("  %d", graph->node[temp->id].data);
temp = temp->next;
}
}
}
else
{
printf("Empty GraphNode");
}
}
// Print all steps process in dfs
void print_dfs(struct MyGraph *graph, int visit[], int i)
{
if (i >= graph->size || visit[i] == 1)
{
return;
}
struct AjlistNode *temp = graph->node[i].edge;
visit[i] = 1;
while (temp != NULL)
{
if (visit[temp->id] == 0)
{
printf("  %d", i);
print_dfs(graph, visit, temp->id);
}
temp = temp->next;
}
printf("  %d", i);
}
// handles the request of find all steps in DFS process
void dfs(struct MyGraph *graph)
{
if (graph->size > 0)
{
int visit[graph->size];
for (int i = 0; i < graph->size; ++i)
{
visit[i] = 0;
}
printf("\n DFS \n");
print_dfs(graph, visit, 0);
}
}
int main()
{
struct MyGraph *graph = newGraph(11);
//Connected two node with Edges
print_graph(graph);
dfs(graph);
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0  :  1  2  3
Adjacency list of vertex 1  :  0  5
Adjacency list of vertex 2  :  0  9
Adjacency list of vertex 3  :  0  8
Adjacency list of vertex 4  :  9
Adjacency list of vertex 5  :  1  6
Adjacency list of vertex 6  :  5  7  10
Adjacency list of vertex 7  :  6  10
Adjacency list of vertex 8  :  3
Adjacency list of vertex 9  :  2  4
Adjacency list of vertex 10  :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````/*
Java Program
Print the DFS traversal step wise
*/
// Define edge of graph node
class AjlistNode
{
//Vertices id
public int id;
public AjlistNode next;
public AjlistNode(int id)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
class GraphNode
{
//node key value
public int data;
public AjlistNode edge;
public GraphNode(int data)
{
this.data = data;
this.edge = null;
}
}
// Define structure of graph
public class MyGraph
{
// Number of graph nodes
public int size;
public GraphNode[] node;
public MyGraph(int size)
{
if (size < 0)
{
System.out.print("\n Invalid size of nodes " + size + " \n");
}
else
{
this.size = size;
this.node = new GraphNode[this.size];
int i = 0;
// Set graph node level and e
for (i = 0; i < this.size; i++)
{
this.node[i] = new GraphNode(i);
}
}
}
//This function are connect nodes with one edge
public void connectEdge(int a, int b)
{
if (this.size <= 0)
{
System.out.print("\n Graph have no nodes \n");
return;
}
AjlistNode newEdge = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
AjlistNode edge = this.node[a].edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
System.out.print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
}
}
// This is handles the request of connecting Edges between given node a to b
public void addEdge(int a, int b)
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
connectEdge(a, b);
if (a == b)
{
//self loop
return;
}
// connect edge
// a <---- b
connectEdge(b, a);
}
else
{
//not valid Vertices
System.out.print("Invalid Node Vertices " + a + " " + b);
}
}
public void printGraph()
{
if (this.size > 0)
{
AjlistNode temp = null;
// Loop controlling variable
int i = 0;
for (i = 0; i < this.size; i++)
{
System.out.print("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i].edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
System.out.print("  " + this.node[temp.id].data);
temp = temp.next;
}
}
}
else
{
System.out.print("Empty Graph Node");
}
}
// Print all steps process in dfs
public void printDFS(boolean[] visit, int i)
{
if (i >= this.size || visit[i] == true)
{
return;
}
AjlistNode temp = this.node[i].edge;
visit[i] = true;
while (temp != null)
{
if (visit[temp.id] == false)
{
System.out.print("  " + i);
printDFS(visit, temp.id);
}
temp = temp.next;
}
System.out.print("  " + i);
}
// handles the request of find all steps in DFS process
public void dfs()
{
if (this.size > 0)
{
boolean[] visit = new boolean[this.size];
for (int i = 0; i < this.size; ++i)
{
visit[i] = false;
}
System.out.print("\n DFS \n");
printDFS(visit, 0);
}
}
public static void main(String[] args)
{
// 11 is number of nodes
MyGraph graph = new MyGraph(11);
//Connected two node with Edges
graph.printGraph();
graph.dfs();
}
}``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Print the DFS traversal step wise
*/
// Define edge of graph node
class AjlistNode
{
public:
// Vertices id
int id;
AjlistNode *next;
AjlistNode(int id)
{
this->id = id;
this->next = NULL;
}
};
// Define node of graph
class GraphNode
{
public:
// node key value
int data;
AjlistNode *edge;
GraphNode()
{
this->data = 0;
this->edge = NULL;

}
GraphNode(int data)
{
this->data = data;
this->edge = NULL;
}
};
// Define structure of graph
class MyGraph
{
public:
// Number of graph nodes
int size;
GraphNode *node;
MyGraph(int size)
{
if (size < 0)
{
cout << "\n Invalid size of nodes " << size << " \n";
}
else
{
this->size = size;
this->node = new GraphNode[this->size];
int i = 0;
//   Set graph node level and e
i = 0;
while (i < this->size)
{
this->node[i].data = i;
this->node[i].edge = NULL;
i++;
}
}
}
//This function are connect nodes with one edge
void connectEdge(int a, int b)
{
if (this->size <= 0)
{
cout << "\n Graph have no nodes \n";
return;
}
AjlistNode *newEdge = new AjlistNode(b);
if (newEdge != NULL)
{
// Get first edge of [i] node
AjlistNode *edge = this->node[a].edge;
if (edge == NULL)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this->node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge->next != NULL)
{
edge = edge->next;
}
// Add edge at last position
edge->next = newEdge;
}
}
else
{
cout << "\nMemory overflow, when connect a new edge from ( " << a << " to " << b << " ) nodes.\n";
}
}
// This is handles the request of connecting Edges between given node a to b
{
if (this->size > 0 && a < this->size && b < this->size)
{
// connect edge
// a---->b
this->connectEdge(a, b);
//self loop
if (a == b)
{
return;
}
// connect edge
// a <---- b
this->connectEdge(b, a);
}
else
{
//not valid Vertices
cout << "Invalid Node Vertices " << a << " " << b;
}
}
void printGraph()
{
if (this->size > 0)
{
AjlistNode *temp = NULL;
// Loop controlling variable
int i = 0;
for (i = 0; i < this->size; i++)
{
cout << "\n Adjacency list of vertex " << i << " :";
// Get first edge of [i] node
temp = this->node[i].edge;
while (temp != NULL)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
cout << "  " << this->node[temp->id].data;
temp = temp->next;
}
}
}
else
{
cout << "Empty Graph Node";
}
}
// Print all steps process in dfs
void printDFS(bool visit[], int i)
{
if (i >= this->size || visit[i] == true)
{
return;
}
AjlistNode *temp = this->node[i].edge;
visit[i] = true;
while (temp != NULL)
{
if (visit[temp->id] == false)
{
cout << "  " << i;
this->printDFS(visit, temp->id);
}
temp = temp->next;
}
cout << "  " << i;
}
// handles the request of find all steps in DFS process
void dfs()
{
if (this->size > 0)
{
bool visit[this->size];
for (int i = 0; i < this->size; ++i)
{
visit[i] = false;
}
cout << "\n DFS \n";
this->printDFS(visit, 0);
}
}
};
int main()
{
// 11 is number of nodes
MyGraph graph = MyGraph(11);
// Connected two node with Edges
graph.printGraph();
graph.dfs();
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````// Include namespace system
using System;
/*
C# Program
Print the DFS traversal step wise
*/
// Define edge of graph node
public class AjlistNode
{
//Vertices id
public int id;
public AjlistNode next;
public AjlistNode(int id)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
public class GraphNode
{
//node key value
public int data;
public AjlistNode edge;
public GraphNode(int data)
{
this.data = data;
this.edge = null;
}
}
// Define structure of graph
public class MyGraph
{
// Number of graph nodes
public int size;
public GraphNode[] node;
public MyGraph(int size)
{
if (size < 0)
{
Console.Write("\n Invalid size of nodes " + size + " \n");
}
else
{
this.size = size;
this.node = new GraphNode[this.size];
int i = 0;
// Set graph node level and e
for (i = 0; i < this.size; i++)
{
this.node[i] = new GraphNode(i);
}
}
}
//This function are connect nodes with one edge
public void connectEdge(int a, int b)
{
if (this.size <= 0)
{
Console.Write("\n Graph have no nodes \n");
return;
}
AjlistNode newEdge = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
AjlistNode edge = this.node[a].edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
Console.Write("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
}
}
// This is handles the request of connecting Edges between given node a to b
public void addEdge(int a, int b)
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
connectEdge(a, b);
//self loop
if (a == b)
{
return;
}
// connect edge
// a <---- b
connectEdge(b, a);
}
else
{
//not valid Vertices
Console.Write("Invalid Node Vertices " + a + " " + b);
}
}
public void printGraph()
{
if (this.size > 0)
{
AjlistNode temp = null;
// Loop controlling variable
int i = 0;
for (i = 0; i < this.size; i++)
{
Console.Write("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i].edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
Console.Write("  " + this.node[temp.id].data);
temp = temp.next;
}
}
}
else
{
Console.Write("Empty Graph Node");
}
}
// Print all steps process in dfs
public void printDFS(Boolean[] visit, int i)
{
if (i >= this.size || visit[i] == true)
{
return;
}
AjlistNode temp = this.node[i].edge;
visit[i] = true;
while (temp != null)
{
if (visit[temp.id] == false)
{
Console.Write("  " + i);
printDFS(visit, temp.id);
}
temp = temp.next;
}
Console.Write("  " + i);
}
// handles the request of find all steps in DFS process
public void dfs()
{
if (this.size > 0)
{
Boolean[] visit = new Boolean[this.size];
for (int i = 0; i < this.size; ++i)
{
visit[i] = false;
}
Console.Write("\n DFS \n");
printDFS(visit, 0);
}
}
public static void Main(String[] args)
{
// 11 is number of nodes
MyGraph graph = new MyGraph(11);
//Connected two node with Edges
graph.printGraph();
graph.dfs();
}
}``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````<?php
/*
Php Program
Print the DFS traversal step wise
*/
// Define edge of graph node
class AjlistNode
{
//Vertices id
public \$id;
public \$next;

function __construct(\$id)
{
\$this->id = \$id;
\$this->next = null;
}
}
// Define node of graph
class GraphNode
{
//node key value
public \$data;
public \$edge;

function __construct(\$data)
{
\$this->data = \$data;
\$this->edge = null;
}
}
// Define structure of graph
class MyGraph
{
// Number of graph nodes
public \$size;
public \$node;

function __construct(\$size)
{
if (\$size < 0)
{
echo "\n Invalid size of nodes ". \$size ." \n";
}
else
{
\$this->size = \$size;
\$this->node = array_fill(0, \$this->size, null);
\$i = 0;
// Set graph node level and e
for (\$i = 0; \$i < \$this->size; \$i++)
{
\$this->node[\$i] = new GraphNode(\$i);
}
}
}
//This function are connect nodes with one edge
public	function connectEdge(\$a, \$b)
{
if (\$this->size <= 0)
{
echo "\n Graph have no nodes \n";
return;
}
\$newEdge = new AjlistNode(\$b);
if (\$newEdge != null)
{
// Get first edge of [i] node
\$edge = \$this->node[\$a]->edge;
if (\$edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
\$this->node[\$a]->edge = \$newEdge;
}
else
{
//Find last location to add new edge
while (\$edge->next != null)
{
\$edge = \$edge->next;
}
// Add edge at last position
\$edge->next = \$newEdge;
}
}
else
{
echo "\nMemory overflow, when connect a new edge from ( ". \$a ." to ". \$b ." ) nodes.\n";
}
}
// This is handles the request of connecting Edges between given node a to b
{
if (\$this->size > 0 && \$a < \$this->size && \$b < \$this->size)
{
// connect edge
// a---->b
\$this->connectEdge(\$a, \$b);
//self loop
if (\$a == \$b)
{
return;
}
// connect edge
// a <---- b
\$this->connectEdge(\$b, \$a);
}
else
{
//not valid Vertices
echo "Invalid Node Vertices ". \$a ." ". \$b;
}
}
public	function printGraph()
{
if (\$this->size > 0)
{
\$temp = null;
// Loop controlling variable
\$i = 0;
for (\$i = 0; \$i < \$this->size; \$i++)
{
echo "\n Adjacency list of vertex ". \$i ." :";
// Get first edge of [i] node
\$temp = \$this->node[\$i]->edge;
while (\$temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
echo "  ". \$this->node[\$temp->id]->data;
\$temp = \$temp->next;
}
}
}
else
{
echo "Empty Graph Node";
}
}
// Print all steps process in dfs
public	function printDFS( & \$visit, \$i)
{
if (\$i >= \$this->size || \$visit[\$i] == true)
{
return;
}
\$temp = \$this->node[\$i]->edge;
\$visit[\$i] = true;
while (\$temp != null)
{
if (\$visit[\$temp->id] == false)
{
echo "  ". \$i;
\$this->printDFS(\$visit, \$temp->id);
}
\$temp = \$temp->next;
}
echo "  ". \$i;
}
// handles the request of find all steps in DFS process
public	function dfs()
{
if (\$this->size > 0)
{
\$visit = array_fill(0, \$this->size, false);
echo "\n DFS \n";
\$this->printDFS(\$visit, 0);
}
}
}

function main()
{
// 11 is number of nodes
\$graph = new MyGraph(11);
//Connected two node with Edges
\$graph->printGraph();
\$graph->dfs();
}
main();``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````/*
Node Js Program
Print the DFS traversal step wise
*/
// Define edge of graph node
class AjlistNode
{
//Vertices id
constructor(id)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
class GraphNode
{
//node key value
constructor(data)
{
this.data = data;
this.edge = null;
}
}
// Define structure of graph
class MyGraph
{
// Number of graph nodes
constructor(size)
{
if (size < 0)
{
process.stdout.write("\n Invalid size of nodes " + size + " \n");
}
else
{
this.size = size;
this.node = Array(this.size).fill(null);
var i = 0;
// Set graph node level and e
for (i = 0; i < this.size; i++)
{
this.node[i] = new GraphNode(i);
}
}
}
//This function are connect nodes with one edge
connectEdge(a, b)
{
if (this.size <= 0)
{
process.stdout.write("\n Graph have no nodes \n");
return;
}
var newEdge = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
var edge = this.node[a].edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a].edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
process.stdout.write("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
}
}
// This is handles the request of connecting Edges between given node a to b
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
this.connectEdge(a, b);
//self loop
if (a == b)
{
return;
}
// connect edge
// a <---- b
this.connectEdge(b, a);
}
else
{
//not valid Vertices
process.stdout.write("Invalid Node Vertices " + a + " " + b);
}
}
printGraph()
{
if (this.size > 0)
{
var temp = null;
// Loop controlling variable
var i = 0;
for (i = 0; i < this.size; i++)
{
process.stdout.write("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i].edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
process.stdout.write("  " + this.node[temp.id].data);
temp = temp.next;
}
}
}
else
{
process.stdout.write("Empty Graph Node");
}
}
// Print all steps process in dfs
printDFS(visit, i)
{
if (i >= this.size || visit[i] == true)
{
return;
}
var temp = this.node[i].edge;
visit[i] = true;
while (temp != null)
{
if (visit[temp.id] == false)
{
process.stdout.write("  " + i);
this.printDFS(visit, temp.id);
}
temp = temp.next;
}
process.stdout.write("  " + i);
}
// handles the request of find all steps in DFS process
dfs()
{
if (this.size > 0)
{
var visit = Array(this.size).fill(false);
process.stdout.write("\n DFS \n");
this.printDFS(visit, 0);
}
}
}

function main()
{
// 11 is number of nodes
var graph = new MyGraph(11);
//Connected two node with Edges
graph.printGraph();
graph.dfs();
}
main();``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````#   Python 3 Program
#   Print the DFS traversal step wise

#  Define edge of graph node
class AjlistNode :
# Vertices id

def __init__(self, id) :
self.id = id
self.next = None

#  Define node of graph
class GraphNode :
# node key value

def __init__(self, data) :
self.data = data
self.edge = None

#  Define structure of graph
class MyGraph :
#  Number of graph nodes

def __init__(self, size) :
if (size < 0) :
print("\n Invalid size of nodes ", size ," ")
else :
self.size = size
self.node = [None] * (self.size)
i = 0
#  Set graph node level and e
while (i < self.size) :
self.node[i] = GraphNode(i)
i += 1

# This function are connect nodes with one edge
def connectEdge(self, a, b) :
if (self.size <= 0) :
print("\n Graph have no nodes ")
return

newEdge = AjlistNode(b)
if (newEdge != None) :
#  Get first edge of [i] node
edge = self.node[a].edge
if (edge == None) :
#  Whe no edge of graph node [i] then
#  Add a first edge of a [i] node
self.node[a].edge = newEdge
else :
# Find last location to add new edge
while (edge.next != None) :
edge = edge.next

#  Add edge at last position
edge.next = newEdge

else :
print("\nMemory overflow, when connect a new edge from ( ", a ," to ", b ," ) nodes.")

#  This is handles the request of connecting Edges between given node a to b
if (self.size > 0 and a < self.size and b < self.size) :
#  connect edge
#  a---->b
self.connectEdge(a, b)
# self loop
if (a == b) :
return

#  connect edge
#  a <---- b
self.connectEdge(b, a)
else :
# not valid Vertices
print("Invalid Node Vertices ", a ," ", b, end = "")

# Display Adjacency list of vertex
def printGraph(self) :
if (self.size > 0) :
temp = None
#  Loop controlling variable
i = 0
i = 0
while (i < self.size) :
print("\n Adjacency list of vertex ", i ," :", end = "")
#  Get first edge of [i] node
temp = self.node[i].edge
while (temp != None) :
# temp->id is graph node vertices
# in this case temp->id is same as
# node[temp->id].data
print("  ", self.node[temp.id].data, end = "")
temp = temp.next

i += 1

else :
print("Empty Graph Node", end = "")

#  Print all steps process in dfs
def printDFS(self, visit, i) :
if (i >= self.size or visit[i] == True) :
return

temp = self.node[i].edge
visit[i] = True
while (temp != None) :
if (visit[temp.id] == False) :
print("  ", i, end = "")
self.printDFS(visit, temp.id)

temp = temp.next

print("  ", i, end = "")

#  handles the request of find all steps in DFS process
def dfs(self) :
if (self.size > 0) :
visit = [False] * (self.size)
print("\n DFS ")
self.printDFS(visit, 0)

def main() :
#  11 is number of nodes
graph = MyGraph(11)
# Connected two node with Edges
graph.printGraph()
graph.dfs()

if __name__ == "__main__": main()``````

#### Output

`````` Adjacency list of vertex  0  :   1   2   3
Adjacency list of vertex  1  :   0   5
Adjacency list of vertex  2  :   0   9
Adjacency list of vertex  3  :   0   8
Adjacency list of vertex  4  :   9
Adjacency list of vertex  5  :   1   6
Adjacency list of vertex  6  :   5   7   10
Adjacency list of vertex  7  :   6   10
Adjacency list of vertex  8  :   3
Adjacency list of vertex  9  :   2   4
Adjacency list of vertex  10  :   6   7
DFS
0   1   5   6   7   10   7   6   5   1   0   2   9   4   9   2   0   3   8   3   0``````
``````#   Ruby Program
#   Print the DFS traversal step wise

#  Define edge of graph node
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_accessor :id, :next

# Vertices id

def initialize(id)
self.id = id
self.next = nil
end

end

#  Define node of graph
class GraphNode
# Define the accessor and reader of class GraphNode
attr_accessor :data, :edge

# node key value

def initialize(data)
self.data = data
self.edge = nil
end

end

#  Define structure of graph
class MyGraph
# Define the accessor and reader of class MyGraph
attr_accessor :size, :node

#  Number of graph nodes

def initialize(size)
if (size < 0)
print("\n Invalid size of nodes ", size ," \n")
else
self.size = size
self.node = Array.new(self.size) {nil}
i = 0
#  Set graph node level and e
while (i < self.size)
self.node[i] = GraphNode.new(i)
i += 1
end

end

end

# This function are connect nodes with one edge
def connectEdge(a, b)
if (self.size <= 0)
print("\n Graph have no nodes \n")
return
end

newEdge = AjlistNode.new(b)
if (newEdge != nil)
#  Get first edge of [i] node
edge = self.node[a].edge
if (edge == nil)
#  Whe no edge of graph node [i] then
#  Add a first edge of a [i] node
self.node[a].edge = newEdge
else
# Find last location to add new edge
while (edge.next != nil)
edge = edge.next
end

#  Add edge at last position
edge.next = newEdge
end

else
print("\nMemory overflow, when connect a new edge from ( ", a ," to ", b ," ) nodes.\n")
end

end

#  This is handles the request of connecting Edges between given node a to b
if (self.size > 0 && a < self.size && b < self.size)
#  connect edge
#  a---->b
self.connectEdge(a, b)
# self loop
if (a == b)
return
end

#  connect edge
#  a <---- b
self.connectEdge(b, a)
else
# not valid Vertices
print("Invalid Node Vertices ", a ," ", b)
end

end

# Display Adjacency list of vertex
def printGraph()
if (self.size > 0)
temp = nil
#  Loop controlling variable
i = 0
i = 0
while (i < self.size)
print("\n Adjacency list of vertex ", i ," :")
#  Get first edge of [i] node
temp = self.node[i].edge
while (temp != nil)
# temp->id is graph node vertices
# in this case temp->id is same as
# node[temp->id].data
print("  ", self.node[temp.id].data)
temp = temp.next
end

i += 1
end

else
print("Empty Graph Node")
end

end

#  Print all steps process in dfs
def printDFS(visit, i)
if (i >= self.size || visit[i] == true)
return
end

temp = self.node[i].edge
visit[i] = true
while (temp != nil)
if (visit[temp.id] == false)
print("  ", i)
self.printDFS(visit, temp.id)
end

temp = temp.next
end

print("  ", i)
end

#  handles the request of find all steps in DFS process
def dfs()
if (self.size > 0)
visit = Array.new(self.size) {false}
print("\n DFS \n")
self.printDFS(visit, 0)
end

end

end

def main()
#  11 is number of nodes
graph = MyGraph.new(11)
# Connected two node with Edges
graph.printGraph()
graph.dfs()
end

main()``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````/*
Scala Program
Print the DFS traversal step wise
*/
// Define edge of graph node
class AjlistNode(var id: Int , var next: AjlistNode)
{
def this(id: Int)
{
this(id, null);
}
}
// Define node of graph
class GraphNode(var data: Int , var edge: AjlistNode)
{
def this(data: Int)
{
this(data, null);
}
}
// Define structure of graph
class MyGraph(var size: Int , var node: Array[GraphNode])
{
def this(size: Int)
{
this(size, Array.fill[GraphNode](size)(null));

if (size > 0)
{
var i: Int = 0;
//  Set graph node level and e
while (i < this.size)
{
this.node(i) = new GraphNode(i);
i += 1;
}
}
}
//This function are connect nodes with one edge
def connectEdge(a: Int, b: Int): Unit = {
if (this.size <= 0)
{
print("\n Graph have no nodes \n");
return;
}
var newEdge: AjlistNode = new AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
var edge: AjlistNode = this.node(a).edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node(a).edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge.next = newEdge;
}
}
else
{
print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
}
}
// This is handles the request of connecting Edges between given node a to b
def addEdge(a: Int, b: Int): Unit = {
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
this.connectEdge(a, b);
//self loop
if (a == b)
{
return;
}
// connect edge
// a <---- b
this.connectEdge(b, a);
}
else
{
//not valid Vertices
print("Invalid Node Vertices " + a + " " + b);
}
}
def printGraph(): Unit = {
if (this.size > 0)
{
var temp: AjlistNode = null;
// Loop controlling variable
var i: Int = 0;
i = 0;
while (i < this.size)
{
print("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node(i).edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
print("  " + this.node(temp.id).data);
temp = temp.next;
}
i += 1;
}
}
else
{
print("Empty Graph Node");
}
}
// Print all steps process in dfs
def printDFS(visit: Array[Boolean], i: Int): Unit = {
if (i >= this.size || visit(i) == true)
{
return;
}
var temp: AjlistNode = this.node(i).edge;
visit(i) = true;
while (temp != null)
{
if (visit(temp.id) == false)
{
print("  " + i);
this.printDFS(visit, temp.id);
}
temp = temp.next;
}
print("  " + i);
}
// handles the request of find all steps in DFS process
def dfs(): Unit = {
if (this.size > 0)
{
var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
print("\n DFS \n");
this.printDFS(visit, 0);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// 11 is number of nodes
var graph: MyGraph = new MyGraph(11);
//Connected two node with Edges
graph.printGraph();
graph.dfs();
}
}``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````
``````/*
Swift 4 Program
Print the DFS traversal step wise
*/
// Define edge of graph node
class AjlistNode
{
//Vertices id
var id: Int;
var next: AjlistNode? ;
init(_ id: Int)
{
self.id = id;
self.next = nil;
}
}
// Define node of graph
class GraphNode
{
//node key value
var data: Int;
var edge: AjlistNode? ;
init(_ data: Int)
{
self.data = data;
self.edge = nil;
}
}
// Define structure of graph
class MyGraph
{
// Number of graph nodes
var size: Int;
var node: [GraphNode? ];
init(_ size: Int)
{
if (size < 0)
{
print("\n Invalid size of nodes ", size, " ");
self.size = 0;
self.node = Array(repeating: nil, count: 1);
}
else
{
self.size = size;
self.node = Array(repeating: nil, count: self.size);
var i: Int = 0;
//   Set graph node level and e
i = 0;
while (i < self.size)
{
self.node[i] = GraphNode(i);
i += 1;
}
}
}
//This function are connect nodes with one edge
func connectEdge(_ a: Int, _ b: Int)
{
if (self.size <= 0)
{
print("\n Graph have no nodes ");
return;
}
let newEdge: AjlistNode? = AjlistNode(b);
if (newEdge  != nil)
{
// Get first edge of [i] node
var edge: AjlistNode? = self.node[a]!.edge;
if (edge == nil)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
self.node[a]!.edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge!.next  != nil)
{
edge = edge!.next;
}
// Add edge at last position
edge!.next = newEdge;
}
}
else
{
print("\nMemory overflow, when connect a new edge from ( ", a, " to ", b, " ) nodes.");
}
}
// This is handles the request of connecting Edges between given node a to b
func addEdge(_ a: Int, _ b: Int)
{
if (self.size > 0 && a < self.size && b < self.size)
{
// connect edge
// a---->b
self.connectEdge(a, b);
//self loop
if (a == b)
{
return;
}
// connect edge
// a <---- b
self.connectEdge(b, a);
}
else
{
//not valid Vertices
print("Invalid Node Vertices ", a, " ", b, terminator: "");
}
}
func printGraph()
{
if (self.size > 0)
{
var temp: AjlistNode? = nil;
// Loop controlling variable
var i: Int = 0;
i = 0;
while (i < self.size)
{
print("\n Adjacency list of vertex ", i, " :", terminator: "");
// Get first edge of [i] node
temp = self.node[i]!.edge;
while (temp  != nil)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
print("  ", self.node[temp!.id]!.data, terminator: "");
temp = temp!.next;
}
i += 1;
}
}
else
{
print("Empty Graph Node", terminator: "");
}
}
// Print all steps process in dfs
func printDFS(_ visit: inout[Bool], _ i: Int)
{
if (i >= self.size || visit[i] == true)
{
return;
}
var temp: AjlistNode? = self.node[i]!.edge;
visit[i] = true;
while (temp  != nil)
{
if (visit[temp!.id] == false)
{
print(" ", i, terminator: "");
self.printDFS(&visit, temp!.id);
}
temp = temp!.next;
}
print("  ", i, terminator: "");
}
// handles the request of find all steps in DFS process
func dfs()
{
if (self.size > 0)
{
var visit: [Bool] = Array(repeating: false, count: self.size);
print("\n DFS ");
self.printDFS(&visit, 0);
}
}
}
func main()
{
// 11 is number of nodes
let graph: MyGraph = MyGraph(11);
//Connected two node with Edges
graph.printGraph();
graph.dfs();
}
main();``````

#### Output

`````` Adjacency list of vertex  0  :   1   2   3
Adjacency list of vertex  1  :   0   5
Adjacency list of vertex  2  :   0   9
Adjacency list of vertex  3  :   0   8
Adjacency list of vertex  4  :   9
Adjacency list of vertex  5  :   1   6
Adjacency list of vertex  6  :   5   7   10
Adjacency list of vertex  7  :   6   10
Adjacency list of vertex  8  :   3
Adjacency list of vertex  9  :   2   4
Adjacency list of vertex  10  :   6   7
DFS
0  1  5  6  7   10   7   6   5   1  0  2  9   4   9   2  0  3   8   3   0``````
``````/*
Kotlin Program
Print the DFS traversal step wise
*/
// Define edge of graph node
class AjlistNode
{
var id: Int;
var next: AjlistNode ? ;
constructor(id: Int)
{
this.id = id;
this.next = null;
}
}
// Define node of graph
class GraphNode
{
var data: Int;
var edge: AjlistNode ? ;
constructor(data: Int)
{
this.data = data;
this.edge = null;
}
}
// Define structure of graph
class MyGraph
{
var size: Int;
var node: Array<GraphNode?>;
constructor(size: Int)
{
if (size < 0)
{
print("\n Invalid size of nodes " + size + " \n");
this.size = 0;
this.node = Array(1)
{
null
};
}
else
{
this.size = size;
this.node = Array(this.size)
{
null
};
var i: Int = 0;
//   Set graph node level and e
while (i<this.size)
{
this.node[i] = GraphNode(i);
i += 1;
}
}
}
//This function are connect nodes with one edge
fun connectEdge(a: Int, b: Int): Unit
{
if (this.size <= 0)
{
print("\n Graph have no nodes \n");
return;
}
var newEdge: AjlistNode ? = AjlistNode(b);
if (newEdge != null)
{
// Get first edge of [i] node
var edge: AjlistNode ? = this.node[a]?.edge;
if (edge == null)
{
// Whe no edge of graph node [i] then
// Add a first edge of a [i] node
this.node[a]?.edge = newEdge;
}
else
{
//Find last location to add new edge
while (edge?.next != null)
{
edge = edge.next;
}
// Add edge at last position
edge?.next = newEdge;
}
}
else
{
print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
}
}
// This is handles the request of connecting Edges between given node a to b
fun addEdge(a: Int, b: Int): Unit
{
if (this.size > 0 && a < this.size && b < this.size)
{
// connect edge
// a---->b
this.connectEdge(a, b);
//self loop
if (a == b)
{
return;
}
// connect edge
// a <---- b
this.connectEdge(b, a);
}
else
{
//not valid Vertices
print("Invalid Node Vertices " + a + " " + b);
}
}
fun printGraph(): Unit
{
if (this.size > 0)
{
var temp: AjlistNode ? ;
// Loop controlling variable
var i: Int = 0;
while (i < this.size)
{
print("\n Adjacency list of vertex " + i + " :");
// Get first edge of [i] node
temp = this.node[i]?.edge;
while (temp != null)
{
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
print("  " + this.node[temp.id]?.data);
temp = temp.next;
}
i += 1;
}
}
else
{
print("Empty Graph Node");
}
}
// Print all steps process in dfs
fun printDFS(visit: Array < Boolean > , i: Int): Unit
{
if (i >= this.size || visit[i] == true)
{
return;
}
var temp: AjlistNode ? = this.node[i]?.edge;
visit[i] = true;
while (temp != null)
{
if (visit[temp.id] == false)
{
print("  " + i);
this.printDFS(visit, temp.id);
}
temp = temp.next;
}
print("  " + i);
}
// handles the request of find all steps in DFS process
fun dfs(): Unit
{
if (this.size > 0)
{
var visit: Array < Boolean > = Array(this.size)
{
false
};
print("\n DFS \n");
this.printDFS(visit, 0);
}
}
}
fun main(args: Array < String > ): Unit
{
// 11 is number of nodes
var graph: MyGraph = MyGraph(11);
//Connected two node with Edges
graph.printGraph();
graph.dfs();
}``````

#### Output

`````` Adjacency list of vertex 0 :  1  2  3
Adjacency list of vertex 1 :  0  5
Adjacency list of vertex 2 :  0  9
Adjacency list of vertex 3 :  0  8
Adjacency list of vertex 4 :  9
Adjacency list of vertex 5 :  1  6
Adjacency list of vertex 6 :  5  7  10
Adjacency list of vertex 7 :  6  10
Adjacency list of vertex 8 :  3
Adjacency list of vertex 9 :  2  4
Adjacency list of vertex 10 :  6  7
DFS
0  1  5  6  7  10  7  6  5  1  0  2  9  4  9  2  0  3  8  3  0``````

## Output Explanation

The adjacency list shows the connections between vertices, and the DFS traversal output demonstrates the sequence of visited vertices. The DFS traversal starts at vertex `0`, explores its adjacent vertices in a depth-first manner, and backtracks when necessary. The traversal path is shown as `0 1 5 6 7 10 7 6 5 1 0 2 9 4 9 2 0 3 8 3 0`.

## Time Complexity

The time complexity of the DFS traversal algorithm depends on the size of the graph and the number of edges. In the worst case, where every vertex is connected to every other vertex, the time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

## Comment

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.

Categories
Relative Post