Python: DFS (Depth-First Search) in Graphs

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.