[Algorithm] 깊이 우선 탐색 (DFS) & 너비 우선 탐색 (BFS)

 

 

 

 

깊이 우선 탐색 (Depth-First Search, DFS)

루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 방법 (스택 or 재귀함수를 통해 구현)

 

• 가능한 한 깊이 내려가면서 탐색을 진행한다.
• 특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다.

 

def dfs(graph, v, visited):
	visited[v] = True
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)
visited = [False] * n
dfs(graph, 1, visited)

 

 

 

---

 

 

 

너비 우선 탐색 (Breadth-First Search, BFS)

루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법 (큐를 통해 구현)

 

• 인접한 노드를 먼저 탐색한다.
• 최단 경로를 찾는 데 유용하다.

 

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
		v = queue.popleft()
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

 

 

 

---

 

 

 

DFS vs. BFS

	DFS	BFS
	깊이 우선 탐색	너비 우선 탐색
데이터 구조	스택 사용	최단 경로를 찾기 위해 큐 사용
정의	순회가 루트 노드에서 시작하여 근처에 방문하지 않은 노드가 없는 노드에 도달할 때까지 가능한 한 노드를 통해 진행하는 순회 접근 방식	다음 레벨로 이동하기 전에 먼저 동일한 레벨의 모든 노드를 살펴보는 순회 접근 방식
	builds the tree sub-tree by sub-tree	builds the tree level by level
접근 방식	LIFO	FIFO
	더 먼 정점에 답이 있을 때 더 적합	더 가까운 정점을 검색하는 데 적합
활용	미로 찾기, 퍼즐 해결, 그래프의 모든 노드를 방문하는 문제 등	최단 경로 찾기, 네트워크 탐색, 그래프의 레벨 순회 등