Summary
BFS와 DFS는 그래프의 모든 정점을 탐색하는(그래프의 순회) 완전 탐색 알고리즘이다.
BFS는 Breadth-First Search로 너비 우선 탐색을 의미하고 자료구조는 Queue를 사용한다.
DFS는 Depth-First Search로 깊이 우선 탐색을 의미하고 자료구조는 Stack을 사용한다.
설명
쉽게 설명하기 위해서 아래와 같은 그래프가 있다고 가정해보자.
(만약, Queue와 Stack에 대해 잘 모른다면 먼저 아래 참고를 통해 공부하고 돌아오자!)
그래프의 모든 노드를 BFS와 DFS 방법으로 탐색하여 탐색 순서가 어떻게 되는지 살펴보며 공부해보자.
- BFS (Breadth-First Search, 너비 우선 탐색)
BFS는 방문 노드와 가장 가깝게 인접한 노드들을 먼저 탐색해 나가는 방법이다. 즉, 너비를 넓혀나가면서 탐색한다고 생각하면 된다.
BFS로 모든 노드를 한 번씩만 탐색하기 위해 사용되는 자료구조는 배열과 Queue를 사용한다.
| 배열(visit) | 노드의 방문 여부를 체크 |
| Queue | 노드의 방문 차례를 기록 |
- 탐색 순서
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
- 자료 구조 = Queue
Queue는 먼저 들어온 요소가 먼저 나가는 FIFO 형식이므로, Queue에 담긴 순서대로 빠져나오기 때문에 BFS 알고리즘에서 사용된다. Queue에서 pop()하여 빠져나오는 노드가 방문 노드가 되며, 해당 노드와 인접한 노드들을 다시 Queue에 넣어주면서 탐색해나가면 된다.
1. 시작 노드인 1을 Queue에 push한다.
2. 방문 노드 = Queue.pop() = 1을 탐색해 1과 인접한 2, 3, 4 노드를 차례대로 Queue에 push한다.
3. 방문한 노드 1을 체크(visit[1] = 1)하고, 방문 순서를 기록한다.
4. 방문 노드 = Queue.pop() = 2를 탐색해 2와 인접하면서 방문하지 않은(visit[n] = 0) 5, 6 노드를 Queue에 push한다.
이 과정을 Queue.empty()가 True가 될 때까지 반복하면, 모든 노드를 BFS 방법으로 탐색할 수 있다.
만약, Queue.pop()한 노드에 인접하면서 방문하지 않은 노드가 없다면 push는 이뤄지지 않으므로, 다음 Queue.pop()을 진행하면 된다.
Queue의 변화 과정
- Python3 코드
def bfs(node, visit, graph):
queue = []
queue.append(node)
while len(queue) > 0:
now_node = queue.pop(0)
visit[now_node] = True
print("Visit node ", now_node+1)
for i in range(0, len(graph)):
if i!=now_node and visit[i]==False and graph[now_node][i]:
queue.append(i)
def solution(graph):
visit = [False]*len(graph)
for i in range(0, len(graph)):
if visit[i] == False:
bfs(i, visit, graph)
graph = [[1,1,1,1,0,0,0,0,0,0],
[1,1,0,0,1,1,0,0,0,0],
[1,0,1,0,0,0,1,0,0,0],
[1,0,0,1,0,0,0,1,1,0],
[0,1,0,0,1,0,0,0,0,1],
[0,1,0,0,0,1,0,0,0,0],
[0,0,1,0,0,0,1,0,0,0],
[0,0,0,1,0,0,0,1,0,0],
[0,0,0,1,0,0,0,0,1,0],
[0,0,0,0,1,0,0,0,0,1]]
solution(graph)
- 출력
- DFS (Depth-First Search, 깊이 우선 탐색)
DFS는 현재 노드에서 갈 수 있는 노드까지 들어가면서 탐색해 나가는 방식으로 그래프를 순회한다. 즉, 연결 되어 있는 노드들을 따라 깊숙히 탐색해 나가면서 모든 노드를 탐색한다고 생각하면 된다. DFS에서 사용되는 자료구조는 배열과 Stack이다.
| 배열(visit) | 노드의 방문 여부를 체크 |
| Stack | 노드의 방문 차례를 기록 |
- 탐색 순서
1 -> 2 -> 5 -> 10 -> 6-> 3 -> 7 -> 4 -> 8 -> 9
- 자료 구조 = Stack
Stack은 나중 들어온 요소가 먼저 나가는 LIFO 형식이다. 따라서 top에 있는 노드가 방문 노드가 되며, 인접한 노드를 먼저 탐색해 나가기 때문에 DFS에 Stack이 사용된다.
1. 먼저, 시작 노드인 1이 Stack에 들어온다.
2. 방문 노드 = Stack.pop() = 1을 탐색해 1과 인접한 4, 3, 2 노드를 차례대로 Stack에 push한다.
3. 방문한 노드 1을 체크(visit[1] = 1)하고, 방문 순서를 기록한다.
4. 방문 노드 = Stack.pop() = 2를 탐색해 2와 인접하면서 방문하지 않은 6, 5 노드를 Stack에 push한다.
이 과정을 Stack.empty()가 true가 될 때까지 반복하면, 모든 노드를 DFS 방법으로 탐색할 수 있다.
만약, Stack.pop()한 노드에 인접하면서 방문하지 않은 노드가 없다면 push는 이뤄지지 않으므로 다음 Stack.pop()을 진행하면 된다.
- Python3 코드
def dfs(node, visit, graph):
print("Visit node ", node+1)
visit[node] = True
for i in range(0, len(graph)):
if i!=node and visit[i] == False and graph[node][i] == 1:
dfs(i, visit, graph)
def solution(graph):
visit = [False]*len(graph)
dfs(0, visit, graph)
graph = [[1,1,1,1,0,0,0,0,0,0],
[1,1,0,0,1,1,0,0,0,0],
[1,0,1,0,0,0,1,0,0,0],
[1,0,0,1,0,0,0,1,1,0],
[0,1,0,0,1,0,0,0,0,1],
[0,1,0,0,0,1,0,0,0,0],
[0,0,1,0,0,0,1,0,0,0],
[0,0,0,1,0,0,0,1,0,0],
[0,0,0,1,0,0,0,0,1,0],
[0,0,0,0,1,0,0,0,0,1]]
solution(graph)
- 출력
사용 예제
참고
[STL] Stack
Stack은 LIFO(Last In First Out, 후입선출)의 자료구조이다. C++의 표준 템플릿 라이브러리로 정의되어 있다. #include 기본 함수 top() Stack의 가장 위의 원소를 반환 push(element) top에 원소 추가 pop() to..
hwayomingdlog.tistory.com
[STL] Queue
Queue는 FIFO(First In First Out, 선입선출)의 자료구조이다. C++의 표준 템플릿 라이브러리로 정의되어 있다. #include 기본 함수 front() Queue의 제일 앞에 있는 원소를 반환 back() Queue의 제일 뒤에..
hwayomingdlog.tistory.com
'Computer Science > Algorithms' 카테고리의 다른 글
| [DP] 동적 프로그래밍 | 동적 계획법 Dynamic Programming (0) | 2021.03.19 |
|---|