# How to implement Depth First Search in Graph?

Depth-First Search is a fundamental algorithm used for traversing and exploring graphs. Below, I’ll outline the steps and provide a Python code implementation for DFS:
Step 1: Introduction to DFS and Graph Representation:
 Briefly explain what DFS is and its purpose in graph traversal.
 Introduce the concept of a graph and different ways to represent it (e.g., adjacency list, adjacency matrix).
Step 2: Implementing the Graph:
 Code the graph representation using an adjacency list.
 Show how to add vertices and edges to the graph.

``````class Graph:
def __init__(self):
self.graph = {}
self.graph[vertex] = []
self.graph[u].append(v)
self.graph[v].append(u) # For an undirected graph``````

Step 3: Implementing Depth-First Search (DFS)
 Code the DFS algorithm using a recursive approach.
 Explain the importance of visited nodes to avoid infinite loops in graphs containing cycles.

``````def dfs_recursive(graph, start, visited):
if start not in visited:
print(start, end=&#39; &#39;)
for neighbor in graph[start]:
dfs_recursive(graph, neighbor, visited)``````

Step 4: Traversing the Graph with DFS
 Create a graph instance and add vertices and edges to it.
 Perform DFS on the graph and display the traversal order.

``````if __name__ == &quot;__main__&quot;:
g = Graph()
# Add vertices and edges to the graph