그래프 깊이 우선 탐색
20 Nov 2017 | Depth First Search DFS Graph
이번 글에서는 그래프(Graph)라는 자료구조를 순회하는 알고리즘 가운데 깊이우선탐색(Depth First Search) 기법을 살펴보도록 하겠습니다. 파이썬 코드는 이곳을 참고하였습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
깊이우선탐색이란 더 이상 나아갈 엣지가 없을 때까지 깊이 탐색하는 그래프 순회(traverse) 기법입니다. 깊이우선탐색을 도식화한 그림은 다음과 같습니다.
파이썬 구현
깊이우선탐색을 파이썬으로 구현한 코드는 다음과 같습니다. 알고리즘에서 쓰이는 변수는 다음과 같습니다.
- 그래프 : Graph (각 노드에는 값과 엣지뿐 아니라 방문시간 time, 색상 Color 정보도 들어 있음)
- 시작노드 : startVertex
- 시작노드와 이웃한 노드 : nextVertex
- 색상 : 아직 방문하지 않았다면 white(defalut), 이미 방문했다면 black, 방문 여부를 검토(processing)하고 있다면 gray
- 방문시간 : 최초 방문(discovery)한 시간, 방문을 마친(finish) 시간 두 가지로 나뉨
from pythonds.graphs import Graph
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
# 모든 노드의 색상을 white,
# 부모노드 정보를 -1로 초기화
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
# 임의의 노드가 아직 방문하지 않은(white)
# 노드라면 해당 노드에 대해 dfsvisit 호출
# dfsvisit은 더 이상 나아갈 엣지가 없을 때까지
# 재귀적으로 수행, 수행 후에도 white인 노드가 있으면
# 해당 노드를 시작노드로 해서 dfsvisit 반복 수행
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def dfsvisit(self,startVertex):
# processing이라는 의미로
# 시작노드의 색상을 gray로 변경
startVertex.setColor('gray')
# 방문시간에 1을 더함
self.time += 1
# 시작노드를 발견한 시점을 기록
startVertex.setDiscovery(self.time)
# 시작노드에 인접한 모든 이웃노드들에 대해
for nextVertex in startVertex.getConnections():
# 해당 노드가 아직 방문하지 않은(white) 노드라면
if nextVertex.getColor() == 'white':
# 해당 노드의 부모를 시작노드라고 기록
nextVertex.setPred(startVertex)
# 해당 노드를 시작노드로 해서 dfsvisit 호출
self.dfsvisit(nextVertex)
# 이렇게 모든 이웃노드들에 대해 탐색이 끝나면
# 시작노드 방문을 마쳤다는 의미로 black으로 변경
startVertex.setColor('black')
# 방문시간에 1을 더함
self.time += 1
# 시작노드 processing을 끝낸 시점을 기록
startVertex.setFinish(self.time)
순회 예시
(a)와 같은 그래프를 깊이우선탐색 방식으로 순회해보겠습니다. 시작노드 startVertex를 $u$로 두겠습니다. 그러면 우선 시작노드 발견시점을 1로 적어두고, processing하고 있다는 의미로 색상을 gray로 바꿉니다. 이후 dfsvisit 함수가 재귀적으로 세 번 호출되면서 $v$, $y$, $x$ 노드에 대해 같은 작업이 진행돼 전체적으로는 (b), (c), (d) 같은 모습을 띄게 됩니다.
이번엔 (f)를 봅시다. (f)에서는 $x$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $x$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이우선탐색이 불가능합니다. $x$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(5)을 기록하고 재귀함수 호출을 종료합니다.
(g)를 봅시다. (g)에서는 $y$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $y$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $y$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(6)을 기록하고 재귀함수 호출을 종료합니다.
(h)를 봅시다. (h)에서는 $v$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $v$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $v$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(7)을 기록하고 재귀함수 호출을 종료합니다.
(m)을 봅시다. (m)에서는 $u$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $u$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $u$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(8)을 기록하고 재귀함수 호출을 종료합니다.
이로써 dfs에서의 dfsvisit 재귀함수 호출이 종료됐습니다. 그런데 아직 아래의 반복문은 계속 돌고 있으므로, 나머지 노드 가운데 아직 방문하지 않은(white) 노드가 있다면 해당 노드들에 대해서도 dfsvistit을 수행해 줍니다.
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
(m)을 다시 봅시다. $w$를 시작노드로 dfvisit을 수행합니다. $w$ 발견시점을 9로 하고 processing하고 있다는 의미로 색상을 gray로 바꿉니다. 이후 $w$의 이웃노드인 $z$를 시작노드로 dfvisit을 재귀적으로 수행합니다. $z$ 발견시점을 10으로 하고 processing하고 있다는 의미로 색상을 gray로 바꿉니다.
(o)를 봅시다. (o)에서는 $z$를 시작노드로 하는 재귀함수 dfvisit이 수행되고 있습니다. $z$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $z$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(11)을 기록하고 재귀함수 호출을 종료합니다.
(p)를 봅시다. (p)에서는 $w$를 시작노드로 하는 재귀함수 dfvisit이 수행되고 있습니다. $w$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $w$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(12)을 기록하고 재귀함수 호출을 종료합니다.
(p)까지 수행이 끝나면 그래프 전체에서 white인 노드가 없게 됩니다. 이로써 dfs의 반복문도 종료됩니다.
깊이우선탐색 그래프의 특성
위 예시에서 깊이우선탐색이 종료된 그래프의 모습은 다음과 같습니다.
깊이우선탐색으로 그래프를 순회한 결과로 부모-자식노드가 도출됩니다. 예컨대 위 그림에서는 $u$와 $v$, $w$와 $b$가 그러한 관계를 갖습니다. 부모에서 자식노드로 향하는 엣지를 Tree edge/Discover edge라고 합니다. 반대로 자식에서 부모노드로 향하는 엣지를 Back edge라고 합니다. 위 그림 기준으로는 음영표시된 엣지가 tree edge, B라고 표시된 엣지가 back edge입니다. 무방향그래프(undirected graph)에서는 Tree edge와 Back edge만 존재합니다.
Tree edge가 아닌 엣지 가운데 자손노드로 향하는 노드를 Forward edge라고 합니다. Cross edge는 이 세 가지 경우를 제외한 모든 종류의 엣지를 나타냅니다. 위 그림 기준으로는 F가 forward edge, B가 back edge입니다. back edge가 존재한다는 말은 사이클(cycle)이 존재한다는 말과 같습니다.
위 여섯개 노드를 발견시점과 탐색종료시점 순으로 나열하면 다음과 같습니다. 자식노드의 발견시점과 탐색종료시점은 부모노드의 부분집합이 됩니다. 이같은 구조를 parenthesis structure라고 합니다.
뿐만 아니라 어떤 임의의 노드가 있고, 이 경로상에 존재하는 white 노드들은 깊이우선탐색 기준 해당 노드의 자식노드가 됩니다. 이를 white path theorem이라고 합니다.
깊이우선탐색의 계산복잡성
깊이우선탐색은 모든 노드와 엣지에 대해 한번씩은 탐색하게 되므로 전체적인 계산복잡성은 $O($|$V$|$+$|$E$|$)$가 됩니다.
이번 글에서는 그래프(Graph)라는 자료구조를 순회하는 알고리즘 가운데 깊이우선탐색(Depth First Search) 기법을 살펴보도록 하겠습니다. 파이썬 코드는 이곳을 참고하였습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
깊이우선탐색이란 더 이상 나아갈 엣지가 없을 때까지 깊이 탐색하는 그래프 순회(traverse) 기법입니다. 깊이우선탐색을 도식화한 그림은 다음과 같습니다.
파이썬 구현
깊이우선탐색을 파이썬으로 구현한 코드는 다음과 같습니다. 알고리즘에서 쓰이는 변수는 다음과 같습니다.
- 그래프 : Graph (각 노드에는 값과 엣지뿐 아니라 방문시간 time, 색상 Color 정보도 들어 있음)
- 시작노드 : startVertex
- 시작노드와 이웃한 노드 : nextVertex
- 색상 : 아직 방문하지 않았다면 white(defalut), 이미 방문했다면 black, 방문 여부를 검토(processing)하고 있다면 gray
- 방문시간 : 최초 방문(discovery)한 시간, 방문을 마친(finish) 시간 두 가지로 나뉨
from pythonds.graphs import Graph
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
# 모든 노드의 색상을 white,
# 부모노드 정보를 -1로 초기화
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self:
# 임의의 노드가 아직 방문하지 않은(white)
# 노드라면 해당 노드에 대해 dfsvisit 호출
# dfsvisit은 더 이상 나아갈 엣지가 없을 때까지
# 재귀적으로 수행, 수행 후에도 white인 노드가 있으면
# 해당 노드를 시작노드로 해서 dfsvisit 반복 수행
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def dfsvisit(self,startVertex):
# processing이라는 의미로
# 시작노드의 색상을 gray로 변경
startVertex.setColor('gray')
# 방문시간에 1을 더함
self.time += 1
# 시작노드를 발견한 시점을 기록
startVertex.setDiscovery(self.time)
# 시작노드에 인접한 모든 이웃노드들에 대해
for nextVertex in startVertex.getConnections():
# 해당 노드가 아직 방문하지 않은(white) 노드라면
if nextVertex.getColor() == 'white':
# 해당 노드의 부모를 시작노드라고 기록
nextVertex.setPred(startVertex)
# 해당 노드를 시작노드로 해서 dfsvisit 호출
self.dfsvisit(nextVertex)
# 이렇게 모든 이웃노드들에 대해 탐색이 끝나면
# 시작노드 방문을 마쳤다는 의미로 black으로 변경
startVertex.setColor('black')
# 방문시간에 1을 더함
self.time += 1
# 시작노드 processing을 끝낸 시점을 기록
startVertex.setFinish(self.time)
순회 예시
(a)와 같은 그래프를 깊이우선탐색 방식으로 순회해보겠습니다. 시작노드 startVertex를 $u$로 두겠습니다. 그러면 우선 시작노드 발견시점을 1로 적어두고, processing하고 있다는 의미로 색상을 gray로 바꿉니다. 이후 dfsvisit 함수가 재귀적으로 세 번 호출되면서 $v$, $y$, $x$ 노드에 대해 같은 작업이 진행돼 전체적으로는 (b), (c), (d) 같은 모습을 띄게 됩니다.
이번엔 (f)를 봅시다. (f)에서는 $x$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $x$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이우선탐색이 불가능합니다. $x$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(5)을 기록하고 재귀함수 호출을 종료합니다.
(g)를 봅시다. (g)에서는 $y$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $y$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $y$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(6)을 기록하고 재귀함수 호출을 종료합니다.
(h)를 봅시다. (h)에서는 $v$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $v$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $v$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(7)을 기록하고 재귀함수 호출을 종료합니다.
(m)을 봅시다. (m)에서는 $u$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $u$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $u$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(8)을 기록하고 재귀함수 호출을 종료합니다.
이로써 dfs에서의 dfsvisit 재귀함수 호출이 종료됐습니다. 그런데 아직 아래의 반복문은 계속 돌고 있으므로, 나머지 노드 가운데 아직 방문하지 않은(white) 노드가 있다면 해당 노드들에 대해서도 dfsvistit을 수행해 줍니다.
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
(m)을 다시 봅시다. $w$를 시작노드로 dfvisit을 수행합니다. $w$ 발견시점을 9로 하고 processing하고 있다는 의미로 색상을 gray로 바꿉니다. 이후 $w$의 이웃노드인 $z$를 시작노드로 dfvisit을 재귀적으로 수행합니다. $z$ 발견시점을 10으로 하고 processing하고 있다는 의미로 색상을 gray로 바꿉니다.
(o)를 봅시다. (o)에서는 $z$를 시작노드로 하는 재귀함수 dfvisit이 수행되고 있습니다. $z$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $z$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(11)을 기록하고 재귀함수 호출을 종료합니다.
(p)를 봅시다. (p)에서는 $w$를 시작노드로 하는 재귀함수 dfvisit이 수행되고 있습니다. $w$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $w$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(12)을 기록하고 재귀함수 호출을 종료합니다.
(p)까지 수행이 끝나면 그래프 전체에서 white인 노드가 없게 됩니다. 이로써 dfs의 반복문도 종료됩니다.
깊이우선탐색 그래프의 특성
위 예시에서 깊이우선탐색이 종료된 그래프의 모습은 다음과 같습니다.
깊이우선탐색으로 그래프를 순회한 결과로 부모-자식노드가 도출됩니다. 예컨대 위 그림에서는 $u$와 $v$, $w$와 $b$가 그러한 관계를 갖습니다. 부모에서 자식노드로 향하는 엣지를 Tree edge/Discover edge라고 합니다. 반대로 자식에서 부모노드로 향하는 엣지를 Back edge라고 합니다. 위 그림 기준으로는 음영표시된 엣지가 tree edge, B라고 표시된 엣지가 back edge입니다. 무방향그래프(undirected graph)에서는 Tree edge와 Back edge만 존재합니다.
Tree edge가 아닌 엣지 가운데 자손노드로 향하는 노드를 Forward edge라고 합니다. Cross edge는 이 세 가지 경우를 제외한 모든 종류의 엣지를 나타냅니다. 위 그림 기준으로는 F가 forward edge, B가 back edge입니다. back edge가 존재한다는 말은 사이클(cycle)이 존재한다는 말과 같습니다.
위 여섯개 노드를 발견시점과 탐색종료시점 순으로 나열하면 다음과 같습니다. 자식노드의 발견시점과 탐색종료시점은 부모노드의 부분집합이 됩니다. 이같은 구조를 parenthesis structure라고 합니다.
뿐만 아니라 어떤 임의의 노드가 있고, 이 경로상에 존재하는 white 노드들은 깊이우선탐색 기준 해당 노드의 자식노드가 됩니다. 이를 white path theorem이라고 합니다.
깊이우선탐색의 계산복잡성
깊이우선탐색은 모든 노드와 엣지에 대해 한번씩은 탐색하게 되므로 전체적인 계산복잡성은 $O($|$V$|$+$|$E$|$)$가 됩니다.
Comments