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
for each adjacent_vertex in graph[vertex]:
DFS(graph, adjacent_vertex, visited)
Algorithm Explanation
- Initialize an array
visited
of sizen
(number of vertices) with all elements set tofalse
. - Start DFS traversal from vertex
0
and call the DFS function. - 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;
}
// Create Adjacency node
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);
}
}
//Display Adjacency list of vertex
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
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 0, 3);
add_edge(graph, 1, 5);
add_edge(graph, 2, 9);
add_edge(graph, 3, 8);
add_edge(graph, 4, 9);
add_edge(graph, 5, 6);
add_edge(graph, 6, 7);
add_edge(graph, 6, 10);
add_edge(graph, 7, 10);
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;
}
// Create Adjacency node
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);
}
}
//Display Adjacency list of vertex
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.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 5);
graph.addEdge(2, 9);
graph.addEdge(3, 8);
graph.addEdge(4, 9);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(6, 10);
graph.addEdge(7, 10);
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;
}
// Create Adjacency node
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
void addEdge(int a, int 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;
}
}
//Display Adjacency list of vertex
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.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 5);
graph.addEdge(2, 9);
graph.addEdge(3, 8);
graph.addEdge(4, 9);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(6, 10);
graph.addEdge(7, 10);
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;
}
// Create Adjacency node
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);
}
}
//Display Adjacency list of vertex
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.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 5);
graph.addEdge(2, 9);
graph.addEdge(3, 8);
graph.addEdge(4, 9);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(6, 10);
graph.addEdge(7, 10);
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;
}
// Create Adjacency node
$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
public function addEdge($a, $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;
}
}
//Display Adjacency list of vertex
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->addEdge(0, 1);
$graph->addEdge(0, 2);
$graph->addEdge(0, 3);
$graph->addEdge(1, 5);
$graph->addEdge(2, 9);
$graph->addEdge(3, 8);
$graph->addEdge(4, 9);
$graph->addEdge(5, 6);
$graph->addEdge(6, 7);
$graph->addEdge(6, 10);
$graph->addEdge(7, 10);
$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;
}
// Create Adjacency node
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
addEdge(a, 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);
}
}
//Display Adjacency list of vertex
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.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 5);
graph.addEdge(2, 9);
graph.addEdge(3, 8);
graph.addEdge(4, 9);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(6, 10);
graph.addEdge(7, 10);
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
# Create Adjacency node
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
def addEdge(self, a, 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.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(0, 3)
graph.addEdge(1, 5)
graph.addEdge(2, 9)
graph.addEdge(3, 8)
graph.addEdge(4, 9)
graph.addEdge(5, 6)
graph.addEdge(6, 7)
graph.addEdge(6, 10)
graph.addEdge(7, 10)
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_reader :id, :next
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_reader :data, :edge
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_reader :size, :node
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
# Create Adjacency node
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
def addEdge(a, 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.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(0, 3)
graph.addEdge(1, 5)
graph.addEdge(2, 9)
graph.addEdge(3, 8)
graph.addEdge(4, 9)
graph.addEdge(5, 6)
graph.addEdge(6, 7)
graph.addEdge(6, 10)
graph.addEdge(7, 10)
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;
}
// Create Adjacency node
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);
}
}
//Display Adjacency list of vertex
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.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 5);
graph.addEdge(2, 9);
graph.addEdge(3, 8);
graph.addEdge(4, 9);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(6, 10);
graph.addEdge(7, 10);
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;
}
// Create Adjacency node
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: "");
}
}
//Display Adjacency list of vertex
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.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 5);
graph.addEdge(2, 9);
graph.addEdge(3, 8);
graph.addEdge(4, 9);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(6, 10);
graph.addEdge(7, 10);
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;
}
// Create Adjacency node
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);
}
}
//Display Adjacency list of vertex
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.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 5);
graph.addEdge(2, 9);
graph.addEdge(3, 8);
graph.addEdge(4, 9);
graph.addEdge(5, 6);
graph.addEdge(6, 7);
graph.addEdge(6, 10);
graph.addEdge(7, 10);
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.
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