그래프 순회 (DFS & BFS)

종류

탐색방법	구현 방법	활용	시간복잡도
DFS	재귀, Stack	백트래킹	O(V^2)
BFS	Queue	최단경로	인접 리스트: O(V+E) 인접행렬: O(V^2)

 

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

개념

한 루트에서 최대한 깊숙이 들어가면서 탐색한 후, 다시 돌아와 다른 루트로 탐색하는 방법

 

장단점

장점	단점
현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 적다	해가 없는 경로에 깊이 빠질 가능성이 있음
목표 노드가 깊은 레벨에 있을 경우 해를 빨리 구할 수 있다.	얻어진 경로가 최단 경로라는 보장이 없다. 따라서, 최단경로를 구하기 위해서는 전체 경로를 다 돌아본 후 비교해야 한다.

구현 방법

재귀: 스택보다 속도는 빠르나 깊이가 너무 깊어지면 재귀 한도를 초과할 수 있으므로 주의해서 사용

스택: 깊이가 깊어도 한도가 없으므로 유용

 

 

시간 복잡도

하나의 경로에서 v만큼 돌기 때문에, O(V) 시간 필요

V개의 정점을 방문할 때마다 v만큼 돌아야 한다

V * O(V) = O(V^2)

 

 

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

개념

시작 정점에서부터 인접한 정점들을 차례로 방문하고, 다시 방문했던 정점을 시작으로 인접한 정점들을 방문하여 탐색하는 방법

 

장단점

장점	단점
출발 노드에서부터의 목표 노드까지 최단 경로를 구할 수 있음	경로가 길 경우엔 탐색 가지가 급격히 많아져 많은 메모리 필요
	해가 존재하지 않는 경우, 모든 노드를 탐색 완료 후 종료
	무한 그래프의 경우, 해를 찾지 못하고 끝도 없음

 

시간 복잡도

모든 정점을 한 번씩 방문하고, 정점을 방문할 때마다 모든 인접 간선을 검사해야 하기 때문에 dfs와 비슷하다

인접 리스트로 구현된 경우: O(V+E)

인접 행렬로 구현된 경우: O(V^2)

 

※인접 리스트 vs 인접 행렬

	인접 리스트	인접 행렬
특징	가 정점에서 인접한 정점들만 리스트에 넣음	|V| x |V| 크기의 정방 행렬
장점	진출 차수를 구할때는 리스트에 있는 것만 찾으면 되므로 유리	진입 차수와 진출 차수를 모두 구할 때 유리
단점	진입 차수를 찾기 위해서는 모든 노드를 탐색해야함	인접 정점을 찾을때, 인접 정점의 수가 적더라도 V크기만큼 탐색해야함 간선이 적은 희소 그래프에서도 |V| x |V| 크기의 메모리 공간을 할당해야하므로 낭비가 심함

 

BFS

 

출처: 위키백과
https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89