BFS
- Problem I noticed: my BFS fundamentals were weak.
- → I decided I should go back and re-do some basic BFS problems.
from collections import deque
node = [[0] * 100 for _ in range(100)]
edge = [0 for i in range(100)]
visited = [0 for i in range(100)]
def bfs(graph, queue):
global n
global visited
while queue:
v = queue.popleft()
# number of edges connected to vertex v
print(v, end=' ')
n = edge[v]
for i in range(n, -1, -1):
next = node[v][n]
# if this vertex was already visited, skip
if visited[next] == 1:
continue
# push unvisited vertices into the queue
queue.append(next)
visited[next] = 1
return
def solution(n, wires):
global m
global visited
graph = []
answer = []
# build the graph
for i in range(len(wires)):
for w in wires:
if wires[i] != w:
node[w[0]][edge[w[1]]] = w[1]
node[w[1]][edge[w[0]]] = w[0]
edge[w[0]] += 1
edge[w[1]] += 1
result = 0
# use BFS to count the number of connected components
for i in range(1, n + 1):
queue = deque()
queue.append(i)
if visited[i] == 0:
visited[i] = 1
bfs(edge, queue)
result += 1
print('result:', result)
n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
solution(n, wires)
# 1 0 2 3 4 5 6 7 8 9 result: 8
Why the heck is it suddenly visiting vertex 0? 😂 That’s so random… What’s going on here?
And where is this result: 8 even coming from?..
from collections import deque
def bfs(graph, queue, node, edge):
global n
global visited
while queue:
v = queue.popleft()
# number of edges connected to vertex v
# print(v, end=' ')
n = edge[v]
for i in range(n, -1, -1):
next = node[v][i]
# if this cell was already visited, skip
if visited[next] == 1:
continue
# push unvisited vertices into the queue
queue.append(next)
visited[next] = 1
return
def solution(n, wires):
global m
global visited
graph = []
answer = []
# build the graph
for i in range(len(wires)):
node = [[0] * 100 for _ in range(100)]
edge = [0 for i in range(100)]
visited = [0 for i in range(100)]
# pick one wire to cut
for w in wires:
# draw the graph with one wire removed
if wires[i] != w:
node[w[0] - 1][edge[w[1]]] = w[1] - 1
node[w[1] - 1][edge[w[0]]] = w[0] - 1
edge[w[0] - 1] += 1
edge[w[1] - 1] += 1
result = 0
# use BFS to count the number of connected components
for j in range(0, n):
queue = deque()
queue.append(j)
if visited[j] == 0:
visited[j] = 1
bfs(edge, queue, node, edge)
result += 1
print(result)
# answer.append(result)
print(answer)
n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
solution(n, wires)
Now it does traverse, but I still don’t know how many connected chunks I actually have yet…
My “strong suspicion” is that the bug is hidden here:
node[w[0] - 1][edge[w[1]]] = w[1] - 1
node[w[1] - 1][edge[w[0]]] = w[0] - 1
edge[w[0] - 1] += 1
edge[w[1] - 1] += 1
This setup looks more like something you’d do for DFS than for clean adjacency storage in general, so it becomes a problem.
From the figure, vertex 3 is connected to 3 neighbors, but node[v] shows only vertex 4 connected. That’s where the fundamental bug was.
Root cause found
edge[w[0]] += 1
edge[w[1]] += 1
node[w[0]][edge[w[0]]] = w[1]
node[w[1]][edge[w[1]]] = w[0]
The bug came from how I was storing information into the node array. After fixing that, BFS works cleanly.
Perfect BFS code (without cutting wires)
from collections import deque
def bfs(queue, node, edge, visited, n):
connected = 0
while queue:
v = queue.popleft()
# count how many vertices are in this connected component
# print(v, end=' ')
connected += 1
k = edge[v]
for i in range(1, k + 1):
next = node[v][i]
# if already visited, skip
if visited[next] == 1:
continue
# enqueue unvisited vertices
queue.append(next)
visited[next] = 1
return (connected, n - connected)
def solution(n, wires):
node = [[0] * 100 for _ in range(100)]
edge = [0 for i in range(100)]
visited = [0 for i in range(100)]
# build the graph
for w in wires:
edge[w[0]] += 1
edge[w[1]] += 1
node[w[0]][edge[w[0]]] = w[1]
node[w[1]][edge[w[1]]] = w[0]
result = 0
answer = []
# use BFS to find how many connected components there are
for j in range(1, n):
queue = deque()
queue.append(j)
if visited[j] == 0:
visited[j] = 1
c, u = bfs(queue, node, edge, visited, n)
result += 1
answer.append([c, u])
print(answer)
n = 9
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
solution(n, wires)
Final version with wires cut (working solution)
from collections import deque
def bfs(queue, node, edge, visited, n):
connected = 0
while queue:
v = queue.popleft()
# number of edges connected to v
# print(v, end=' ')
connected += 1
k = edge[v]
for i in range(1, k + 1):
next = node[v][i]
# if already visited, skip
if visited[next] == 1:
continue
# enqueue unvisited vertices
queue.append(next)
visited[next] = 1
return (connected, n - connected)
def solution(n, wires):
answer = []
for i in range(len(wires)):
node = [[0] * 100 for _ in range(100)]
edge = [0 for i in range(100)]
visited = [0 for i in range(100)]
# build the graph
for w in wires:
# skip exactly one wire (the one we are “cutting”)
if wires[i] != w:
edge[w[0]] += 1
edge[w[1]] += 1
node[w[0]][edge[w[0]]] = w[1]
node[w[1]][edge[w[1]]] = w[0]
result = 0
# use BFS to find the two connected components after cutting one wire
for j in range(1, n):
queue = deque()
queue.append(j)
if visited[j] == 0:
visited[j] = 1
c, u = bfs(queue, node, edge, visited, n)
result += 1
val = abs(c - u)
print(f'val = {val}')
answer.append(val)
return min(answer)
But: with this approach, I got 84.6% accuracy, and there were runtime errors on 2 test cases. Probably because I’m doing BFS way more often than necessary.
How to make it better
Instead of building edge and node arrays manually, just use an adjacency list and append neighbors directly.
Here all edge weights are 1, so BFS is naturally suitable.
import sys
from collections import defaultdict, deque
# Breadth-first search
def bfs(a, b, wire_node, n):
que = deque()
que.append(a)
visited = [0] * (n + 1)
visited[a] = 1
cnt = 0
while que:
tmp = que.popleft()
for next_wire in wire_node[tmp]:
# skip the one specific edge we are “cutting”
if tmp == a and next_wire == b:
continue
if visited[next_wire] == 0:
visited[next_wire] = 1
que.append(next_wire)
cnt += 1
return cnt
def solution(n, wires):
# build graph (power grid nodes)
wire_node = defaultdict(list)
for a, b in wires:
wire_node[a].append(b)
wire_node[b].append(a)
# try cutting each wire
min_val = sys.maxsize # initialize with a huge value
for wire in wires:
cut1, cut2 = wire
val = abs(bfs(cut1, cut2, wire_node, n) - bfs(cut2, cut1, wire_node, n))
if val < min_val:
min_val = val
return min_val
Basic Problems (BFS/DFS warm-up) Ice Cream (counting components in a grid)
from collections import deque
def bfs(i, j, table, visited):
queue = deque()
if table[i][j - 1] == 1:
queue.push([i, j])
def solution():
n, m = map(int, input().split())
# The two lines below actually aren’t necessary.
table = [[0] * (m + 2) for _ in range(n + 2)]
visited = [[0] * m for _ in range(n)]
# Table setting – and honestly, this is way more complicated than needed.
for i in range(0, n + 2):
for j in range(0, n + 2):
if i == 0 or i == n + 1 or j == 0 or j == n + 1:
table[i][j] = 2
else:
num = int(input())
table[i][j] = num
# The simpler way:
for i in range(n):
graph.append(list(map(int, input())))
# The full table is already given as input, so there’s no need
# to construct it via (i, j) indices manually.
# Just iterate over it:
for i in range(n):
for j in range(m):
if visited[i][j] == 0:
bfs(i, j, table, visited)
In this problem, the inputs are not “edge lists” but the grid itself, so it’s better to change the mindset and treat it as a grid traversal problem.
from collections import deque
def dfs(i, j, n, m, graph):
# NOTE: This is actually a DFS using recursion, but I originally named it dfs.
if i <= -1 or i >= n or j <= -1 or j >= m:
return False
if graph[i][j] == 0:
graph[i][j] = 1
dfs(i + 1, j, n, m, graph)
dfs(i - 1, j, n, m, graph)
dfs(i, j + 1, n, m, graph)
dfs(i, j - 1, n, m, graph)
return True
def solution():
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# Since we already have the full grid, there’s no need to reconstruct it by (i, j).
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j, n, m, graph) == True:
result += 1
print(result)
return result
solution()
Difference between the two codes:
In the first version, I added “padding” around the grid to generalize the logic, but that’s not necessarily a good idea.
The second version uses boundary checks directly (i <= -1 or i >= n etc.), which is simpler and more standard.
I actually wanted to solve this with BFS, but I ended up using DFS first. So I tried BFS too:
from collections import deque
from re import L
visited = [[0] * 100 for _ in range(100)]
def bfs(graph, x, y, queue):
global n
global m
global visited
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
depth = 0
while queue:
v = queue.popleft()
print(v, end=' ')
for i in range(4):
nx = v[0] + dx[i]
ny = v[1] + dy[i]
# If out of bounds, ignore
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# Skip already visited cells
if visited[nx][ny] == 1:
continue
if graph[nx][ny] == 0:
queue.append([nx, ny])
visited[nx][ny] = 1
depth = depth + 1
return
def solution():
global n
global m
global visited
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# Again, the grid is already given.
result = 0
# Iterate through all cells
for i in range(n):
for j in range(m):
queue = deque()
queue.append([i, j])
# This condition was crucial for solving it
if visited[i][j] == 0 and graph[i][j] == 0:
visited[i][j] = 1
bfs(graph, i, j, queue)
result += 1
print(result)
return
solution()
This time I solved it with BFS. In practice, the difference between DFS and BFS isn’t huge here; it depends more on how the problem is framed.
Maze (Shortest Path)
For shortest path problems with uniform edge weights, BFS is usually the best choice.
If all edges have the same cost, BFS increments the distance level by level.
DFS instead goes all the way down one path before checking others, which is inefficient for shortest path.
from collections import deque
def bfs(graph, x, y, queue):
global n
global m
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
depth = 0
while queue:
v = queue.popleft()
print(v, end=' ')
for i in range(4):
nx = v[0] + dx[i]
ny = v[1] + dy[i]
if nx == n - 1 and ny == m - 1:
print(depth)
return depth
# out of bounds
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# already visited
if visited[nx][ny] == 1:
continue
if graph[nx][ny] == 1:
queue.append([nx, ny])
visited[nx][ny] = 1
depth += 1
pass
def solution():
global n
global m
global visited
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# The grid is given directly as input.
visited = [[0] * m for _ in range(n)]
queue = deque()
queue.append([1, 1])
visited[1][1] = 1
bfs(graph, 1, 1, queue)
return
solution()
Again, BFS is naturally suited for shortest paths in grids with uniform move cost.
PREVIOUSSpace center
NEXTBFS