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
	for each adjacent_vertex in graph[vertex]:
		DFS(graph, adjacent_vertex, visited)

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;
	}
	// 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.

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.

New Comment