그래프 : 여러 개체들이 연결되어 있는 자료구조
그래프 순회 (탐색)
•
그래프 내의 모든 노드를 한 번씩 살펴보는 것
•
비선형 자료구조인 그래프에서의 순회를 할 때는 시작 노드를 설정해주어야 한다.
•
시작 노드를 기준으로 연결된 노드들을 살펴보며 그래프 순회를 수행할 수 있다.
•
시작 노드를 기준으로 연결된 노드들을 살펴 볼 때 방식에 따라 다음과 같이 두 가지로 분류할 수 있다.
◦
깊이 우선 탐색(DFS, Depth-First Search)
▪
현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식
◦
너비 우선 탐색(BFS, Breadth-First Search)
▪
시작 노드를 기준으로 거리가 가까운 노드를 먼저 방문하는 방식
▪
거리가 가깝다는 의미는 시작 노드에서 해당 노드까지 갈 때 거친 간선의 갯수가 적다는 것을 의미
깊이 우선 탐색 (DFS)
•
현재 탐색 중인 노드를 기준으로 연결된 노드를 즉시 방문하는 방식
•
시간복잡도
◦
Node의 갯수 N , Edge의 갯수 M →
•
연결된 노드 중 무엇을 먼저 방문하냐에 다라서 방문 순서가 달라지므로 결과가 여러개가 존재할 수 있다.
•
stack 자료구조를 쓰거나, 재귀 함수를 통해서 구현
DFS 예제
•
구현
# 노드의 갯수
N = 5
# DFS function
def dfs(node):
global adj_list, visted
if visted[node]:
return
visited[node] = True
print(node, end=' ')
#recursive
for adj_node in adj_list[node]:
dfs(adj_node)
adj_list = [[] for _ in range(N)]
visited = [False] * N
adj_list[0].append(1); adj_list[0].append(2)
adj_list[1].append(4); adj_list[1].append(3)
adj_list[2].append(3)
adj_list[3].append(0)
dfs(0)
Python
복사
너비 우선 탐색 (BFS)
•
시작 노드를 기준으로 거리가 가까운 노드를 먼저 방문하는 방식
•
거리가 가까운 노드를 넣어주고 가까운 노드 부터 나와야 하기 때문에 queue를 사용하여 구현
•
시간 복잡도 : , : 노드의 갯수, : 간선의 갯수
•
BFS 예제
그림설명
from collections import deque
adj_list = [[] for _ in range(N)]
visited = [False] * N
adj_list[0].append(1); adj_list[0].append(2)
adj_list[1].append(4); adj_list[1].append(3)
adj_list[2].append(3)
adj_list[3].append(0)
q = deque()
q.append(0)
visited[0] = True
while q:
node = q.popleft()
print(node, end=' ')
for adj_node in adj_list[node]:
if visited[adj_node]:
continue
q.append(adj_node)
visited[adj_node] = True
Python
복사
from collections import deque
adj_list = [[] for _ in range(N)]
visited = [False] * N
adj_list[0].append(1); adj_list[0].append(2)
adj_list[1].append(4); adj_list[1].append(3)
adj_list[2].append(3)
adj_list[3].append(0)
q = deque()
q.append(0)
visited[0] = True
print(0, end=' ')
while q:
node = q.popleft()
for adj_node in adj_list[node]:
if not visited[adj_node]:
q.append(adj_node)
visited[adj_node] = True
print(adj_node, end=' ')
Python
복사
내용정리
•
그래프 순회 알고리즘으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다
•
두 알고리즘 모두 노드와 간선을 한번씩 처리하기 때문에 시간 복잡도는 이다.
•
깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)
◦
일반적인 그래프 순회(탐색)을 구현할 때
▪
DFS 와 BFS 모두 사용 가능
▪
따라서 편한 대로 하면됨
◦
시작 노드로부터 가까운 노드 순으로 방문해야 할 때
▪
DFS 불가능 / BFS 가능
•
그러나 깊이 우선 탐색(DFS)를 알아야 하는 이유
◦
그래프 탐색 응용 문제에서 DFS를 기반으로 코드를 작성해야 하는 경우가 종종 있음