[Algorithm] BFS / DFS

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)

---

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

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

 

 

 

 

---

참고

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

https://f-lab.kr/insight/understanding-dfs-and-bfs-algorithms-20240517