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보다 수행시간이 좋다.
- 사용하는 경우 : 두 노드 사이의 최단 경로를 구하거나 임의의 경로를 찾고 싶을 때 선택
- 어떤 노드를 방문했는지 여부를 반드시 검사해야 한다. 검사하지 않을 경우 무한루프에 빠진다.
- 탐색 순서
- 0번을 시작으로 좌/우측 자식 노드의 존재 여부를 확인
- 좌측부터 1번 노드와 2번 노드를 순차적으로 방문
- 1번 노드를 방문, 자식 노드인 3번, 4번 노드를 순차적으로 방문할 것을 기록
- 2번 노드를 방문, 자식 노드인 5번, 6번 노드를 순차적으로 방문할 것을 기록
- 3번, 4번, 5번, 6번 노드를 순차적으로 방문
BFS 구현에는 선입선출 방식인 큐(queue)를 이용한다. 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보를 큐에 넣어 먼저 큐에 들어있던 노드부터 방문한다.
예제
# BFS 구현
from collections import deque
def bfs(graph, start, visited):
queue = deque([start]) # 큐 구현을 위해 deque 라이브러리 이용
visited[start] = True
while queue:
v = queue.popleft()
print(v, end='')
for i in graph[v]: # 해당 노드와 연결되었지만 아직 방문하지 않은 노드를 큐에 삽입
if not visited[v]:
visited[i] = True
queue.append(i)
# 노드 연결 정보를 2차원 리스트로 표현
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) # 1 2 3 8 7 4 5 6
Greedy 알고리즘
그리디(Greedy) 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 그리디 알고리즘을 이용하면, 매 순간 가장 좋아보이는 것만 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. (순간마다 하는 선택은 그 순간에 지역적으로는 최적이지만, 그 선택들을 계속 모아 연속적인 답을 만들었다고해서 그 답이 최적이라는 보장은 없다.)
- 다른 최적해 계산 알고리즘에 비해 빠른 속도를 갖는다.
- 현재의 최적 값을 찾아 선택하기에 항상 최적 해를 찾는 것은 불가능하다.
최소 신장 트리(MTS-Minimum Spanning Tree)
Spanning Tree란
Spanning Tree는 그래프 내의 모든 정점을 포함하는 트리이다. 그래프의 최소 연결 부분 그래프이며, 그래프에서 일부 간선을 선택해서 만든 트리이다. (Spanning Tree = 신장 트리)
n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 Spanning Tree가 된다. (하나의 그래프에 여러 개의 신장 트리가 존재할 수 있다. ) Spanning Tree는 트리의 특수한 형태이므로, 모든 정점들이 연결되어 있어야 하고, 사이클이 포함되어서는 안된다.
MST(Minimum Spanning Tree)란
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다.
MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다.
MST의 특징
- 간선의 가중치의 합이 최소이다.
- n개의 정점을 가지는 그래프는 반드시 (n-1)개의 간선만 사용해야 한다.
- 사이클이 포함되지 않는다.
MST 구현 방법
1. Kruskal MST 알고리즘
탐욕적인 방법(Greedy)을 이용하여 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 것이다.
- 순서
- 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
- 정렬된 간선들에서 순서대로 사이클을 만들지 않는 간선을 선택한다. (그리디 방법을 사용하기에 사이클을 형성하는 간선을 제외하고 가장 낮은 가중치를 먼저 선택한다.)
- 해당 간선을 최소 비용 신장 트리의 집합에 추가한다.
2. Prim MST 알고리즘
시작 정점부터 출발하여 신장트리를 단계적으로 확장해가는 방법이다. 이전 단계에서 만들어진 신장트리를 확장하는 방법이며, 정점 선택을 기반으로 하는 알고리즘이다.
- 순서
- 시작 정점을 최소 비용 신장 트리 집합에 포함시킨다.
- 앞 단계에서 만들어진 집합에 인접한 정점들 중 최소 간선으로 연결된 정점을 선택해 트리를 확장해나간다.
- 위의 과정을 트리가 (n-1)개의 간선을 가질 때까지 반복한다.
질문
- DFS, BFS를 사용하기 적합한 상황은 언제일까?
- DFS는 주로 모든 노드를 방문하고자 하는 경우에 사용하고, BFS는 두 노드 사이의 최단 경로를 찾고 싶을 때 선택한다.
- 최소 신장 트리는 무엇인가?
- 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 신장트리라고 하는데, 이 신장 트리들 중에서 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장트리를 최소 신장 트리라고 한다