1. DFS(Depth First Search)
그래프에서 깊이를 우선적으로 탐색하는 알고리즘을 DFS 즉, 깊이우선탐색이라고 부른다. 그래프는 노드(node 또는 vertex)와 간선(edge)으로 이루어진 자료구조이며, DFS는 그래프에서 한 노드를 시작점으로 모든 노드를 탐색하는 알고리즘 중 하나이다.
- 깊이 우선 탐색?
- DFS, BFS 탐색 순서에는 한 가지의 정답만이 있는 것이 아니다.
트리 자료구조(그래프의 한 종류)를 예로 들면 이해하기 쉽다. 깊이 우선 탐색은 쉽게 생각하면 자식 노드가 없는 노드를 찾을 때까지 탐색하는 방식을 의미하는데, 이는 곧 탐색 순서가 반드시 하나로 정해지지 않는다는 것을 의미하기도 한다.
위 그림에서 시작 노드는 A이고, 연결된 노드가 둘 이상이라면, 알파벳 순서로 탐색한다고 가정하자. 위의 그림과 아래 순서를 같이 보면 보다 이해하기 쉽다.
1) A노드를 방문한다.
2) A노드와 연결된 B, C 노드 중 B를 방문한다.
3) B노드와 연결된 D, E 노드 중 D를 방문한다.
4) D노드에 연결된 노드 중, 이미 방문한 노드를 제외한 다른 노드가 없으므로, 이전에 방문한 B에서 갈 수 있는 다른 노드인 E를 방문한다.
5) E노드에서 더 이상 방문할 노드가 없고, E의 부모 노드인 B에서도 더이상 방문할 노드가 없으니, B의 부모 노드인 A노드에서 아직 방문하지 않은 C노드를 방문한다.
6) 마지막으로 C에서 방문할 수 있는 F를 방문하고, 더 이상 방문할 노드가 없으므로 탐색을 종료한다.
# 파이썬 코드
N = int(input()) # 노드 개수
visited = [False]*(N+1) # N+1를 곱해주는 이유는 편의상 인덱스를 1부터 사용하기 위함
graph = [[],] # 마찬가지로 인덱스를 1부터 사용하기 위함
for _ in range(n):
graph.append(list(map(int, input().split())))
def dfs(graph, v, visited):
visited[v] = True
for n in graph(v):
if not visited[n]:
dfs(graph, n, visited)2. BFS(Breadth First Search)
DFS는 깊이를 우선 즉, 자식 노드를 우선적으로 탐색했다면, BFS 즉, 너비우선탐색은 가까운 노드부터 방문하는 알고리즘이다. 다른 말로는 level first search라고도 불리는데, 즉, 트리 구조를 예를 들면, 같은 레벨의 노드부터 탐색함을 의미한다.
- 너비 우선 탐색?
위의 그림과 탐색 순서가 조금 다른 것을 볼 수 있는데, 바로 시작 노드에서 연결된 노드를 먼저 탐색하고, 다시 자식 노드에 연결된 노드들을 탐색하고 있다. BFS는 탐색 순서를 찾기 위해 큐를 이용하는데, 큐에 들어가는 노드들의 순서는 다음과 같다.
1) A노드를 방문하고, 연결된 노드인 B, C를 큐에 넣는다.
2) 큐에서 B를 꺼내고, B에 연결되있는 D, E를 큐에 넣는다.
3) 큐에서 C를 꺼내고, C에 연결되있느 F를 넣는다.
4) 큐에서 D를 꺼낸다. 연결된 아직 방문되지 않은 노드가 없으므로 큐에 넣을 건 없다.
5) 큐에서 E를 꺼낸다. 마찬가지로 큐에 넣을 노드는 없다.
6) 큐에서 F를 꺼내고 모든 노드를 탐색했으므로, 탐색을 종료한다.
# 파이썬 코드
N = int(input()) # 노드 개수
visited = [False]*(N+1) # N+1를 곱해주는 이유는 편의상 인덱스를 1부터 사용하기 위함
graph = [[],] # 마찬가지로 인덱스를 1부터 사용하기 위함
for _ in range(n):
graph.append(list(map(int, input().split())))
def bfs(graph, v, visited):
queue = deque([v])
visited[v] = True
while queue:
new = queue.popleft()
print(new, end=' ')
for adj in graph[new]:
if not visited[adj]:
queue.append(adj)
visited[adj] = True
