Posted on by Kalkicode
Code Graph

# Depth First Traversal for a Graph

The problem at hand involves performing Depth First Traversal (DFS) on a directed graph. DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. The goal is to visit all the vertices of the graph starting from a given vertex and to print the sequence of visited vertices.

## Problem Statement

Given a directed graph, we need to implement a Depth First Traversal algorithm to traverse all its vertices starting from a specified vertex. We want to output the sequence of visited vertices in the DFS traversal.

## Example Scenario

Let's consider a simple directed graph with 6 vertices numbered from 0 to 5 and the following edges: • Vertex 0 is connected to vertices 1 and 5.
• Vertex 1 is connected to itself.
• Vertex 2 is connected to vertex 1.
• Vertex 3 is connected to itself and vertex 0.
• Vertex 4 is connected to vertices 2 and 3.
• Vertex 5 is connected to vertex 1.

## Solving the Problem

To solve this problem, we need to implement the Depth First Traversal algorithm. Here's a step-by-step explanation:

Step 1: Define Graph 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.

Step 4: Depth First Traversal (DFS)

The DFS algorithm starts from a given vertex and explores as deeply as possible along each branch before backtracking. We implement the `dfs` function that recursively traverses the graph using DFS. It maintains an array `visit` to track visited vertices to avoid revisiting them.

Step 5: Print DFS Sequence

The `printDFS` function initiates the DFS traversal from a specific vertex. It prints the sequence of visited vertices during the traversal.

## Pseudocode

``````DFS(graph, vertex, visited):
if vertex is visited:
return
mark vertex as visited
print vertex

PrintDFS(graph, startVertex):
initialize an array visited[] with all vertices unvisited
DFS(graph, startVertex, visited)``````

## Algorithm Explanation

1. Initialize a graph `g` using the `newGraph` function with 6 vertices.
2. Add the specified edges using the `addEdge` function.
3. Print the adjacency list of the graph using the `printGraph` function.
4. Call the `printDFS` function with a starting vertex (e.g., vertex 4).
5. The DFS traversal is initiated, and the visited vertices sequence is printed.

## Resultant Output Explanation

The adjacency lists of the graph are printed first, showing which vertices are connected to each vertex. Then, the DFS traversal is performed starting from vertex 4. The visited vertices sequence is printed as 4 -> 2 -> 1 -> 3 -> 0 -> 5.

## Time Complexity

The time complexity of DFS traversal in a graph depends on the number of vertices and edges. In the worst case, where all vertices and edges are explored, the time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post