BFS, DFS

DFS(Depth First Search)

DFS는 깊이 우선 탐색 알고리즘이다.

 

DFS는 스택, 재귀함수를 사용하여 구현한다.

모든 그래프에 대해서 적용 가능한 탐색 알고리즘이다.

그래프 노드 탐색에서는 전위순회와 탐색하는 순서가 같다.

 

순서는 0, 1, 3, 4, 2, 5, 6 노드를 순차적으로 탐색한다.

 

인접 행렬을 사용할 경우 시간복잡도: O(V²)

노드 n의 인접 노드를 찾는 과정에서 O(V)의 시간복잡도가 필요하고, 모든 정점을 탐색해야하므로 V번 반복해야 하기 때문에 총 시간 복잡도는 O(V²) 가 된다.

 

인접 리스트를 사용할 경우 시간복잡도: O(V+E)

노드 n의 리스트에는 노드 n과 인접한 노드 개수만큼만(차수만큼) 들어있다. 다른 노드의 경우도 이러할 것이다. 이 개수를 모두 합하면 결국에는 간선의 개수인 E가 된다. 그리고 모든 정점을 탐색할 때 V번 반복하므로 총 시간 복잡도는 O(V+E)이다.

장점

1. BFS에 비해 저장공간의 필요성이 적다. 백트래킹 해야하는 노드들만 저장하면 된다.
2. 찾아야하는 노드의 level이 높을수록 유리하다.

단점

1. 그래프의 깊이가 깊은 경우 오래 걸릴 수 있다.
2. 찾은 답이 최단 경로임을 보장할 수 없다.

BFS(Breadth First Search)

BFS는 너비 우선 탐색 알고리즘이다.

BFS는 주로 큐를 사용하여 구현한다.

모든 그래프에 대해서 적용 가능한 탐색 알고리즘이다.

순서는 0, 1, 2, 3, 4, 5, 6 노드를 순차적으로 탐색한다.

인접 행렬을 사용할 경우 시간복잡도: O(V²)

노드 n의 인접 노드를 찾는 과정에서 O(V)의 시간복잡도가 필요하고, 모든 정점을 탐색해야하므로 V번 반복해야 하기 때문에 총 시간 복잡도는 O(V²) 가 된다.

 

인접 리스트를 사용할 경우 시간복잡도: O(V+E)

노드 n의 리스트에는 노드 n과 인접한 노드 개수만큼만(차수만큼) 들어있다. 다른 노드의 경우도 이러할 것이다. 이 개수를 모두 합하면 결국에는 간선의 개수인 E가 된다. 그리고 모든 정점을 탐색할 때 V번 반복하므로 총 시간 복잡도는 O(V+E)이다.

장점

1. 답이 되는 경로가 여러개임에도 최단경로임을 보장한다.
2. 최단 경로가 존재한다면 반드시 그 최단경로를 찾을 수 있다.
3. 그래프의 레벨이 낮을수록 유리하다.

단점

1. 인접한 노드들을 모두 저장하고 있기에 공간을 보다 많이 사용한다.

참고자료

https://lotuslee.tistory.com/48

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

 

 

https://lotuslee.tistory.com/49

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