너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
목차
BFS (Breadth-First Search, 너비 우선 탐색)
시작 정점에서 가까운 정점부터 차례로 탐색. 특정 깊이의 모든 정점을 탐색 후 다음 깊이로 이동.
- Queue(FIFO) 자료구조 사용
- 최단 경로 탐색에 유용 (가중치 없는 그래프)
def bfs(graph, start_node):
visited = list()
queue = list()
queue.append(start_node)
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
queue.extend(graph[node])
return visitedDFS (Depth-First Search, 깊이 우선 탐색)
한 경로를 따라 가능한 멀리까지 이동한 후 뒤로 돌아가 다른 경로를 탐색.
- Stack(LIFO) 자료구조 사용
- 모든 경로를 탐색해야 하는 문제, 백트래킹 문제에 유용
def dfs(graph, start_node):
visited = list()
stack = list()
stack.append(start_node)
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
# 역순으로 추가하여 올바른 순서 유지
stack.extend(reversed(graph[node]))
return visited시간 복잡도
Vertex 수 + Edge 수: O(V + E)