DFS는 Depth-First-Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)라고 말한다.
그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면, 두 노드는 인접하다(Adjacent) 라고 표현한다.
프로그래밍에서는 그래프를 두가지 방법으로 표현이 가능하다.
2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.
연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다. 실제 코드에서는 논리적으로 정답이 될수 없는 큰 값중에서 999999999,987654321 등 으로 초기화 하는 경우가 많다.
이렇게 그래프를 인접 행렬 방식으로 처리할 때는 다음과 같이 데이터를 초기화 한다.
INF = 999999999
graph = [
[0,7,5],
[7,0,INF],
[5,INF,0]
]
print(graph)
==>
[[0,7,5],[7,0,999999999],[5,999999999,0]]
인접 리스트 방식에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.
인접 리스트는 '연결 리스트' 라는 자료구조를 이용해 구현하는데 파이썬에서는 기본 자료형인 리스트 자료형에 append()를 사용한다.
g = [[] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장 (노드,거리)
g[0].append((1,7))
g[0].append((2,5))
# 노드 1에 연결된 노드 정보 저장 (노드,거리)
g[1].append((0,7))
# 노드 2에 연결된 노드 정보 저장 (노드,거리)
g[2].append((0,5))
print(g)
===>
[[(1,7),(2,5)],[(0,7)],[(0,5)]]
# g = graph
# v = visit
# visited = visited
def DFS(g,v,visited):
visited[v] = True
print(v,end =' ')
for i in g[v]:
if not visited[i]:
dfs(g,i,visited)
g =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited = [False] * 9
dfs(g,1,visited)
===>
1 2 7 6 8 3 4 5
BFS 알고리즘은 '너비 우선 탐색'이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘 이다.
DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다. BFS는 그 반대이다.
BFS에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.
from collections import deque
def bfs(g,start,visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v,end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visitied[i] = True
g =[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7],
]
visited = [False] * 9
bfs(g,1,visited)
==>
1 2 3 8 7 4 5 6