해당 포스팅부터는 그래프 알고리즘을 배운다. 그 첫 번째로 그래프를 순회하는 방법을 알아보자.
트리 구조에서 전위, 중위 순회 역시 트리 내의 모든 노드를 어떠한 순서로 방문한다. 그래프 순회 마찬가지로 그래프의 정점과 간선들을 방문하는 절차를 말한다.
그래프 순회에서는 대표적으로 깊이우선탐색(DFS)와 너비우선탐색(BFS)가 있다.
깊이우선탐색(Depth-First Search)
dfs는 트리의 전위 순회와 비슷하게 출발정점으로부터 멀어지는 방향으로 정점과 간선의 방문을 진행한다.
n개의 정점과 m개의 간선이 있는 경우에 O(n+m) 시간에 dfs를 수행한다.
dfs는 재귀적으로 함수를 호출해 그래프의 정점, 간선의 방문뿐만 아니라 그래프가 연결그래프인지 결정하는 문제, 그래프의 연결 요소들을 계산하는 문제, 그래프의 신장숲을 결정하는 문제 등을 해결할 수 있다.
dfs 문제는 정점의 방문에 대해 fresh와 visit으로 라벨을 달고 간선에 대해서 fresh, tree, back 3개의 라벨을 사용한다.
dfs 의사코드
for each v from G.vertex()
if(l(v) = fresh){
dfs(v)
}
}먼저 dfs를 호출하기 전에 모든 정점과 모든 간선에 대한 label을 fresh로 초기화 하고 출발한다.
초기화 후 그래프의 정점을 돌며 dfs를 호출해 그래프 순회를 수행한다.
Alg dfs(v)
input graph G, start vertex v
output labeling of edges of G in connected component of v
as tree edges & back edges
l(v) <- visit //출발 정점 방문 표시
for each e G.incidentEdges(v){
if(l(e) = fresh){ //간선 첫 방문이라면
w <- G.opposite(v, e) //e의 endpoit 중 v가 아닌 정점 w
if(l(w) = fresh){ //w 방문 안 했으면 label에 tree
l(e) <- tree
dfs(w)
} else{ //w 방문 했으면 label에 back
l(e) <- back
}
}
}
return가장 먼저 인자로 들어온 v에 방문 표시 후 v의 부착간선 리스트를 돈다.
v의 부착간선 e가 fresh 상태라면 v와 함께 e를 이루는 정점 w를 추출한다.
w가 fresh 상태라면, 해당 간선에는 tree 표시 후 dfs를 재귀 호출한다. w가 visit 상태라면, 간선 e에 back 표시 후 다음 부착간선을 검사한다.
정점에 대한 fresh와 visit은 이해가 되는데 간선의 tree와 back에 대한 이해가 쉽지 않다. dfs 수행 예시를 보면서 알아보자.
dfs 수행 그림 예시
먼저 A에서 시작한다고 하자. A에 방문 표시를 하고 A의 부착간선 리스트를 돌 것이다. 부착간선은 B, C, D, E로 향하는 4가지의 간선이 있다. 먼저 B를 향하는 간선을 본다.
해당 간선 e에서 e.opposite(A)를 통해 B 정점을 뽑아내고 B가 fresh 상태이므로 e에 tree 표시 후 dfs(B)를 호출한다.
dfs(B)에서는 B를 visit 상태로 바꾸고 시작한다. 다음 B의 부착간선 리스트를 볼 것인데 A로 향하는, C로 향하는 간선 2개가 있다. A로 향하는 간선 e부터 보면 fresh가 아닌 상태이기 때문에 다음 부착간선을 검사한다. C는 fresh이기 때문에 B-C에 tree 표시 후 dfs(C)를 호출한다.
dfs(C)에서는 C를 visit 상태로 바꾸고 시작한다. 다음 C의 부착간선 리스트를 검사하는데 A로 향하는 간선부터 검사한다 하자. 간선(C, A)는 fresh이기 때문에 A의 라벨까지 체크할 수 있다. A를 보아하니 visit이므로 이 때, tree가 아닌 back을 표시하고 다음 부착간선 검사로 넘어간다.
이렇게 쭉쭉 진행이 되고 최종적으로 완성된 그래프를 보자. 여기서 back으로 표시된, 후향 간선을 싹 지워보면 트리가 된다.
그림의 예시는 연결그래프이기 때문에 신장트리가 된다. v와 연결되지 않은 정점과 간선이 그래프의 연결요소로 존재했다면 신장숲이었을 것이다.
이 신장트리를 dfs(v)에 의해 라벨된 v 연결요소의 DFS tree라고 한다. 간선에 tree와 back으로 네이밍한 것도 이러한 이유이고 back은 이미 방문한 정점을 향한다는 후향 간선의 의미를 갖는다.
dfs 성능
정점과 간선의 라벨을 수정하는 데 각 O(1) 시간이 소요된다. 각 정점은 fresh로 1번, visit으로 1번하여 총 2번 수정을 거치고 각 간선은 fresh로 1번 이외의 것으로 1번하여 총 2번 수정한다.
그래프가 인접리스트로 표현된 경우에 dfs는 O(n+m)에 수행한다.
dfs 작업은 경로 찾기, 연결성 검사, 싸이클 찾기 등으로 응용, 확장이 가능하다.
참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.
