BFS?
BFS는 너비 우선 탐색이다.
이 자료구조는 웹 크롤링, 퍼즐이나 게임 풀기, 소셜 네트워크(친구 찾기) 등에서 쓰인다.
그래프를 탐색하는 방법 중 하나이다.
그래프는 vertex(정점), edge(간선)으로 이루어져 있으며 시간복잡도는 O(V+E)로 알려져 있다.
탐색 과정
BFS 방식으로 그래프를 탐색하는 과정은 아래와 같다.
레벨 0이 시작 정점이자 레벨 1의 부모 정점이라고 하자.
그럼 BFS는 레벨 1에 있는 모든 정점 즉, 정점 s의 자식 정점들인 레벨 1에 있는 정점들을 모두 탐색한다.
이 과정의 반복이다.
또 레벨 1의 정점들은 레벨 1의 자식 정점인 레벨 2의 정점들을 모두 탐색한다.
한 정점을 파고들어 그 정점의 끝 정점까지 파고드는 것이 아닌, 한 정점의 모든 자식 정점을 탐색한 후 또 그 자식들을 모두 탐색하는 것이다.
탐색 순서는 따라서 s -> a -> x -> z -> c -> d -> f -> v
구현
보통 BFS 구현에서는 deque을 사용한다.
하지만, deque을 사용하지 않은 의사코드도 있어서 구현해보았다.
adj = [
["s"],
["a", "x"],
["z", "d", "c"],
["f", "v"]]
def bfs(adj, s):
level = {s : 0}
parent = {s : None}
i = 1
frontier = [1]
while frontier:
next = []
for u in frontier:
for v in adj[u]:
print(v)
if v not in level:
level[v] = i
parent[v] = u
if u + 1 < len(adj):
next.append(u + 1)
frontier = next
i += 1
bfs(adj, adj[0][0])
아래는 deque을 사용한 BFS이다.
from collections import deque
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
def bfs(graph, start, visited):
q = deque([start])
# q.append(start)
visited[start] = True
while q:
v = q.popleft()
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
visited[i] = True
q.append(i)
bfs(graph, 1, visited)