Python: DFS (Depth-First Search) in Graphs

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

✅ Some premium posts are free to read — no account needed. Follow me on Medium to stay updated and support my writing.

🎓 Top 10 Udemy Courses (Huge Discount): Explore My Udemy Courses — Learn through real-time, project-based development.

▶️ Subscribe to My YouTube Channel (172K+ subscribers): Java Guides on YouTube

1. Introduction

The Depth-First Search (DFS) is a fundamental algorithm used to traverse or search through graphs and trees. It explores as far as possible along each branch before backtracking. The main idea behind DFS is to go deeper into the graph whenever possible.

2. Program Overview

In this program, we will:

1. Create a representation for a graph using an adjacency list.

2. Implement the DFS algorithm to traverse through the graph and print each vertex.

3. Code Program

class Graph:
    def __init__(self):
        # Dictionary to store the adjacency list of the graph
        self.graph = dict()

    def add_edge(self, u, v):
        # Add an edge to the adjacency list
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def dfs(self, v, visited=None):
        # Mark the current node as visited
        if visited is None:
            visited = set()
        visited.add(v)
        print(v, end=' ')

        # Recur for all adjacent vertices
        for neighbour in self.graph.get(v, []):
            if neighbour not in visited:
                self.dfs(neighbour, visited)

        return visited

# Create a sample graph and add edges
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

# Perform DFS from vertex 2
print("DFS starting from vertex 2:")
g.dfs(2)

Output:

DFS starting from vertex 2:
2 0 1 3

4. Step By Step Explanation

1. We initialize an empty graph with the Graph class, which uses a dictionary to represent the adjacency list.

2. The add_edge method allows adding edges to the graph.

3. The dfs method is used to perform a depth-first traversal of the graph. It uses a set visited to keep track of visited vertices.

4. In the sample provided, we created a graph with 4 vertices and then executed DFS starting from vertex 2. The output represents the order in which nodes are visited.