Depth First Traversal for a Graph
The problem at hand involves performing Depth First Traversal (DFS) on a directed graph. DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. The goal is to visit all the vertices of the graph starting from a given vertex and to print the sequence of visited vertices.
Given a directed graph, we need to implement a Depth First Traversal algorithm to traverse all its vertices starting from a specified vertex. We want to output the sequence of visited vertices in the DFS traversal.
Let's consider a simple directed graph with 6 vertices numbered from 0 to 5 and the following edges:
- Vertex 0 is connected to vertices 1 and 5.
- Vertex 1 is connected to itself.
- Vertex 2 is connected to vertex 1.
- Vertex 3 is connected to itself and vertex 0.
- Vertex 4 is connected to vertices 2 and 3.
- Vertex 5 is connected to vertex 1.
Solving the Problem
To solve this problem, we need to implement the Depth First Traversal algorithm. Here's a step-by-step explanation:Step 1: Define Graph Representation
We represent the graph using an adjacency list. The graph is structured as a collection of vertices, each having a data value and a linked list of adjacent nodes.Step 2: Implement Graph Creation
We create a new graph with a specified number of vertices using the
newGraph function. This
function initializes the graph and allocates memory for vertices.
We connect the vertices by adding edges between them using the
addEdge function. This
function takes two vertices as input and creates an edge between them by updating their adjacency lists.
The DFS algorithm starts from a given vertex and explores as deeply as possible along each branch
before backtracking. We implement the
dfs function that recursively traverses the graph
using DFS. It maintains an array
visit to track visited vertices to avoid revisiting
printDFS function initiates the DFS traversal from a specific vertex. It prints
the sequence of visited vertices during the traversal.
DFS(graph, vertex, visited): if vertex is visited: return mark vertex as visited print vertex for each adjacentNode in vertex's adjacency list: DFS(graph, adjacentNode, visited) PrintDFS(graph, startVertex): initialize an array visited with all vertices unvisited DFS(graph, startVertex, visited)
- Initialize a graph
newGraphfunction with 6 vertices.
- Add the specified edges using the
- Print the adjacency list of the graph using the
- Call the
printDFSfunction with a starting vertex (e.g., vertex 4).
- The DFS traversal is initiated, and the visited vertices sequence is printed.
1) DFS traversal of directed graph in c
2) DFS traversal of directed graph in c++
3) DFS traversal of directed graph in java
4) DFS traversal of directed graph in c#
5) DFS traversal of directed graph in go
6) DFS traversal of directed graph in kotlin
7) DFS traversal of directed graph in swift
8) DFS traversal of directed graph in scala
9) DFS traversal of directed graph in ruby
10) DFS traversal of directed graph in python
11) DFS traversal of directed graph in TypeScript
12) DFS traversal of directed graph in node js
13) DFS traversal of directed graph in php
14) DFS traversal of directed graph in vb.net
Resultant Output Explanation
The adjacency lists of the graph are printed first, showing which vertices are connected to each vertex. Then, the DFS traversal is performed starting from vertex 4. The visited vertices sequence is printed as 4 -> 2 -> 1 -> 3 -> 0 -> 5.
The time complexity of DFS traversal in a graph depends on the number of vertices and edges. In the worst case, where all vertices and edges are explored, the time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph.