BFS, DFS

BFS와 DFS는 그래프를 탐색하는 알고리즘 기법이다.

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

DFS는 하나의 방향을 결정하면 그 방향을 따라 끝까지 도달한다. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색한다. 즉, 그래프에서 깊은 부분을 우선적으로 탐색한다.

• 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 이 방법을 선택
• 스택(stack)을 사용해서 구현하며, 자기 자신을 호출하는 순환 알고리즘의 형태를 갖고 있다.
• 어떤 노드를 방문했는지 여부를 반드시 검사해야 한다. 검사하지 않을 경우 무한루프에 빠진다.
• 탐색 순서
  • 0번을 시작으로 왼쪽에 위치한 1번 노드를 우선적으로 탐색
  • 3번 노드가 끝이기에 이전 단계로 돌아간다.(1번 노드로 돌아간다)
  • 1번 노드에서 오른쪽에 위치한 4번 노드를 탐색
  • 왼쪽을 다 탐색했기에 오른쪽 노드인 2를 탐색

예제

def dfs(graph, v, visited):
		visited[v] = True
		print(v, end='')
		for i in graph[v]:  # 현재 노드와 연결된 노드를 재귀적으로 방문
				if not visited[i]:
						dfs(graph, i visited)

graph = [
		[],
		[2, 3, 8],
		[1, 7],
		[1, 4, 5],
		[3, 5],
		[3, 4] ,
		[7],
		[2, 6, 8] ,
		[1, 7]
]

# 노드 방문 여부를 리스트로 표현
visited = [False] * 9

dfs(graph, 1, visited)

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

BFS는 현재 위치를 기준으로 가장 가까운(인접한) 노드를 순차적으로 방문한다. DFS와는 다르게 끝까지 파고드는 방향이 아니라, 주변을 순차적으로 탐색하는 방법(시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문)이며 일반적으로 DFS보다 수행시간이 좋다.

• 사용하는 경우 : 두 노드 사이의 최단 경로를 구하거나 임의의 경로를 찾고 싶을 때 선택