DFS vs BFS

그래프를 탐색하는 방법에는 DFS, BFS가 있다. 
DFS는 Depth-First Search 즉 깊이 우선 탐색을 말하고, BFS는 Breadth-First Search 너비 우선 탐색을 말한다.

 

(그래프란 node와 node를 잇는 edge로 이루어진 자료구조를 말한다.)

 

그럼 DFS와 DFS의 차이점을 알아보자.

✅ DFS의 개념 

루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 먼저 다 탐색하는 방식을 말한다. 
모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.

 

BFS보다 간단하지만 느리다.

 

 

✅ BFS의 개념
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다.
루트 노드에서 시작해서 인접한 노드를 먼저 탐색을 하는 방식이다. 
시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져있는 정점은 나중에 방문한다.

그러므로 최단 경로를 찾고싶을 때 이 방법을 선택한다.

결론) 깊이 우선 탐색은 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색하고, 너비 우선 탐색을 현재 정점에 연결된 가까운 점들부터 탐색한다.

코드 비교

#dfs

- 스택 또는 재귀함수로 구현 

 

#그래프 표현
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]

#dfs는 재귀적으로 깊게 탐색
#방문된 정보 표현
visited = [False] * 9
dfs(graph, 1, visited)

#dfs 함수 
#해당 노드의 상태를 True로
def dfs(graph, v, visited):
	visited[v]=True
    print(v,end='')
    
    #인접한 노드 중 방문하지 않은 것이 있다면 
    for i in graph[v]:
    	if not visited[i]:
        	# 그 i를 기준으로 다시 탐색 시작
        	dfs(graph, i, visitied)

 

#bfs

- 큐를 이용해서 구현

 

#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
bfs(graph,1,visited)

def bfs(graph, start, visited):
	queue=deque([start])
    visited[start]=True
    while queue:
    	#가장 먼저 들어온 v를 pop하고 그 v에 인접한 i중에 방문하지 않았다면 큐에 넣고, 방문 처리
    	v=queue.popleft()
        print(v,end='')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i]=True

 

Q. 그럼 알고리즘 문제를 풀 때 어떤 개념을 사용하는 것이 더 적합할까?
1. 모든 정점을 방문하는 문제: 둘 다 무관

2. 경로의 특징을 저장해야하는 문제: DFS
     ex. 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안되는 문제 등 
     (BFS는 경로의 특징을 가지지 못한다.)

3. 최단 거리를 구해야하는 문제: BFS
     ex. 미로 찾기 등 최단거리를 구해야 할 경우 -> BFS는 경로 탐색 시 먼저 찾아지는 해답이 곧 최단거리이다.

참고) https://devuna.tistory.com/32