Graph Traversals - BFS and DFS#

Welcome to Day 20 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive into two fundamental graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). These algorithms form the basis for many more complex graph algorithms and are essential for solving a wide range of problems.

Introduction to Graph Traversals#

Graph traversal refers to the process of visiting (checking and/or updating) each vertex in a graph. The order in which the vertices are visited defines the traversal algorithm. The two most common traversal algorithms are:

1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)

Breadth-First Search (BFS)#

BFS explores a graph level by level. It visits all the neighbors of a vertex before moving to the next level neighbors.

Algorithm:#

1. Start from a chosen source vertex and add it to a queue.
2. Visit the vertex at the front of the queue and remove it.
3. Add all unvisited neighbors of this vertex to the queue.
4. Repeat steps 2-3 until the queue is empty.

Implementation:#

 1from collections import deque
 2
 3def bfs(graph, start):
 4    visited = set()
 5    queue = deque([start])
 6    visited.add(start)
 7
 8    while queue:
 9        vertex = queue.popleft()
10        print(vertex, end=" ")
11
12        for neighbor in graph[vertex]:
13            if neighbor not in visited:
14                visited.add(neighbor)
15                queue.append(neighbor)
16
17# Example usage
18graph = {
19    0: [1, 2],
20    1: [0, 2, 3],
21    2: [0, 1, 4],
22    3: [1, 4],
23    4: [2, 3]
24}
25
26print("BFS starting from vertex 0:")
27bfs(graph, 0)

Time Complexity:#

• O(V + E), where V is the number of vertices and E is the number of edges.

Space Complexity:#

• O(V) for the queue and visited set.

Applications of BFS:#

1. Finding the shortest path in an unweighted graph
2. Web crawlers
3. Social networking features (e.g., finding friends within a certain degree of connection)
4. GPS Navigation systems
5. Puzzle solving (e.g., solving a Rubik’s cube in the least number of moves)

Depth-First Search (DFS)#

DFS explores a graph by going as deep as possible along each branch before backtracking.

Algorithm:#

1. Start from a chosen source vertex.
2. Explore one of its unvisited neighbors.
3. Repeat step 2 for the newly visited vertex.
4. If all neighbors are visited, backtrack to the previous vertex.
5. Repeat steps 2-4 until all vertices are visited.

Implementation:#

 1def dfs(graph, start, visited=None):
 2    if visited is None:
 3        visited = set()
 4
 5    visited.add(start)
 6    print(start, end=" ")
 7
 8    for neighbor in graph[start]:
 9        if neighbor not in visited:
10            dfs(graph, neighbor, visited)
11
12# Iterative DFS
13def dfs_iterative(graph, start):
14    visited = set()
15    stack = [start]
16
17    while stack:
18        vertex = stack.pop()
19        if vertex not in visited:
20            visited.add(vertex)
21            print(vertex, end=" ")
22            stack.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)
23
24# Example usage
25graph = {
26    0: [1, 2],
27    1: [0, 2, 3],
28    2: [0, 1, 4],
29    3: [1, 4],
30    4: [2, 3]
31}
32
33print("Recursive DFS starting from vertex 0:")
34dfs(graph, 0)
35
36print("\nIterative DFS starting from vertex 0:")
37dfs_iterative(graph, 0)

Time Complexity:#

• O(V + E), where V is the number of vertices and E is the number of edges.

Space Complexity:#

• O(V) for the recursive call stack or the stack in iterative implementation.

Applications of DFS:#

1. Topological Sorting
2. Detecting cycles in a graph
3. Path finding (e.g., maze solving)
4. Finding strongly connected components
5. Generating mazes

Comparison of BFS and DFS#

Exercise#

1. Implement a function to find the shortest path between two vertices in an unweighted graph using BFS.
2. Create a method to detect a cycle in a directed graph using DFS.
3. Implement a function to find all connected components in an undirected graph using either BFS or DFS.

Summary#

Today, we explored two fundamental graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). We implemented both algorithms and discussed their characteristics, time and space complexities, and applications.

Understanding these traversal techniques is crucial for solving a wide range of graph problems and forms the foundation for more advanced graph algorithms. As we progress through this challenge, you’ll find BFS and DFS being used as building blocks for solving complex graph-related problems.

Tomorrow, we’ll dive into shortest path algorithms, starting with Dijkstra’s algorithm. Stay tuned!

Solution#

 1from collections import deque
 2
 3def shortest_path(graph, start, goal):
 4    if start == goal:
 5        return [start]
 6    visited = {start}
 7    parent = {start: None}
 8    queue = deque([start])
 9    while queue:
10        vertex = queue.popleft()
11        for neighbor in graph[vertex]:
12            if neighbor not in visited:
13                visited.add(neighbor)
14                parent[neighbor] = vertex
15                if neighbor == goal:
16                    path = [goal]
17                    while parent[path[-1]] is not None:
18                        path.append(parent[path[-1]])
19                    return list(reversed(path))
20                queue.append(neighbor)
21    return None  # no path exists
22
23# Example usage
24graph = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1, 4], 4: [2, 3]}
25print(shortest_path(graph, 0, 4))  # [0, 2, 4]