Breadth-First Search (BFS) is a method for exploring graphs or trees, starting from a vertex and visiting all its adjacent vertices first, followed by the unvisited adjacent vertices. It can also be used as a shortest path search algorithm in certain cases. Today, we will proceed with a deep problem-solving approach along with the basic concept of BFS.
Problem: Numbering Complexes
Problem Description
In a given n x n array consisting of 0s and 1s, 1 represents the location of a house and 0 represents the absence of a house. Write a program that assigns each complex a unique number to distinguish all the houses. The size of a complex is defined as the number of houses belonging to it.
Input
n (1 ≤ n ≤ 25) An n x n array composed of 0s and 1s
Output
Print the size of each complex in ascending order
Example Input
7 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
Example Output
1 7
Problem Approach
To solve this problem, we will use the BFS algorithm to explore the graph. By traversing the provided 2D array, whenever we encounter a house (1), we will count all the connected houses using BFS to calculate the size of the complex. In the next step, we will explain the concept of BFS in detail.
Breadth-First Search (BFS) Concept
BFS is implemented using a queue. It follows the following process:
- Add the starting node to the queue and mark it as visited.
- Remove a node from the queue and add all its adjacent nodes (that have not yet been visited) to the queue, marking them as visited.
- If the queue is not empty, return to step 2.
Coding Implementation
I will write code to solve the problem using the BFS algorithm.
from collections import deque
def bfs(x, y, n, graph, visited):
queue = deque()
queue.append((x, y))
visited[x][y] = True
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
size = 1 # store the size of the complex
while queue:
cx, cy = queue.popleft() # current position
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
size += 1 # increase the count of connected houses
return size # return the size of the complex
def find_complexes(n, graph):
visited = [[False] * n for _ in range(n)]
complexes = []
for i in range(n):
for j in range(n):
if graph[i][j] == 1 and not visited[i][j]:
size = bfs(i, j, n, graph, visited)
complexes.append(size)
return sorted(complexes) # return the sizes in ascending order
# Example input
n = 7
graph = [
[0, 0, 1, 0, 0, 1, 1],
[0, 0, 1, 0, 1, 1, 1],
[0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[1, 1, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0]
]
complex_sizes = find_complexes(n, graph)
print(len(complex_sizes)) # print the number of complexes
for size in complex_sizes:
print(size) # print the size of each complex
Code Explanation
The above code demonstrates how to calculate the size of complexes using BFS. The main functions are find_complexes and bfs.
bfs(x, y, n, graph, visited): Executes BFS starting from the point (x, y) to calculate the size of the corresponding complex. It records each visited house using a queue and aggregates all connected houses.find_complexes(n, graph): Iterates through the given graph, finds houses (1), invokes BFS, and stores the calculated complex sizes in a list.
Conclusion
Breadth-First Search (BFS) is a useful search method that can be utilized in various fields. I hope you learned how to solve problems using BFS through this lecture. Understanding and applying the code during the problem-solving process will greatly assist you in your coding tests.
Additional Practice Problems
Try solving the following problems:
- Finding the shortest path between specific nodes in the given graph
- Solving a maze problem using BFS