digraph는 directed graph의 준말로 방향간선 그래프를 뜻한다.
앞 포스팅의 dfs, bfs는 무방향간선 그래프를 가정하고 설명했다. digraph는 무방향간선 그래프의 성격과 조금 차이가 있다.
방향간선 그래프의 정점 개수 n, 간선 개수 m에 대해 그래프가 루프와 병행 간선이 없는 단순 그래프라면 m <= n P 2를 만족한다. 또한, 정점에 대한 진입 간선과 진출 간선을 리스트로 보관한다면 그래프 순회를 조금 더 최적화 할 수 있다.
이번 포스팅은 무방향 그래프와 다른 방향 그래프 개념들과 DAG의 위상 정렬을 학습한다.
방향 그래프
dfs
digraph에서 dfs를 하게 되면, 전향 간선과 교차 간선이 추가된 4가지의 간선 성격이 발생한다. 전향은 출발 진영에서 멀어지기는 하지만 이미 방문을 한 간선이 된다.
도달 가능성
무방향 그래프의 경우는 출발 정점이 도달하지 못하는 것에 대해 서로 다른 연결요소로 말을 하지만 digraph에서는 도달 가능성을 체크하게 된다.
강연결성
만약, digraph에서 어느 정점을 선택하더라도 도달 가능하다면 그래프를 강연결(strongly connected)이라고 한다.
그래프의 강연결성은 어떻게 확인할까?
첫 번째로 단순하게 모든 정점에 대해 dfs를 돌리고 visit이 있으면 false를 리턴하는 방식이다. 각 dfs를 정점 개수 n번 소화하므로 O(n(n+m)) 시간에 수행한다.
두 번째로 간선을 역행시키는 방법이다.
임의 정점을 선택하고 dfs를 진행한다. 모두 방문이 되었다면 모든 간선 방향을 역행시킨 그래프 G'을 구한다. G'에 대해 똑같은 정점으로 dfs를 진행한다. G'에서도 모든 정점을 방문했다면 원래의 G는 강연결이 증명된다. dfs를 총 2번하여 O(n+m)으로 시간복잡도가 줄어든다.
이행적 폐쇄
이행적 폐쇄는 데이터베이스 정규화의 함수적 종속성을 공부하면서 처음 접했던 용어인 것 같다. 데이터베이스에서는 이행적 폐쇄가 부정적 성격의 느낌이 강했는데 그래프의 이행적 폐쇄도 부정적인 건 아니지만 얼추 비스무리하다.
이행적 폐쇄는 한 정점에서 다른 정점으로 경로가 있다면, 도달 가능하다면, 간선이 있다고 보는 것이다.
이 역시 모든 정점에 대해 dfs를 해서 O(n(n+m)) 시간에 그래프의 이행적 폐쇄를 구할 수 있겠지만, 우리는 여기서 동적프로그래밍(Dynamic Programming)을 사용한다. 어떻게 dp를 사용해 이행적 페쇄를 구하는지는 다음 포스팅에서 다루겠다.
📌 DAG
비순환 방향 그래프(directed acyclic graph, DAG)는 싸이클이 존재하지 않는 방향 그래프를 말한다. java의 인터페이스, 상속 클래스 개념이 DAG이다.
📙 위상 정렬
위상 정렬(topological sort)은 DAG의 정점들을 위상 순서대로 선형으로 정렬하는 작업이다. 어떠한 방향 그래프가 위상 순서를 가진다면 DAG이고, DAG이라면 그래프는 위상 순서를 가진다.
위상 정렬 구현에는 진입 차수를 이용하는 방법과 dfs 방법으로 나뉜다.
1. 진입 차수를 이용한 위상 정렬
Alg topologicalSort()
input graph G
output topological order Q
Q <- empty list
for each v from G.vertex() { //각 정점 진입간선 차수 계산, 0인 정점 Q에 삽입
in_degree(v) <- inDegree(v)
if(in_degree(v) = 0) {
Q.enqueue(v)
}
}
i <- 1 //topological number
while(!Q.isEmpty()) {
v <- Q.dequeue()
l(v) <- i
i++
for each e from G.outIncidentEdge(v) {
dest <- G.opposite(v, e)
in_degree(dest)--
if(in_degree(dest) = 0) {
Q.enqueue(dest)
}
}
}
if(i <= n) { //i가 정점 개수보다 크지 않다면 그래프에 싸이클이 존재
DirectedCycleException()
}먼저 위상 순서를 나타낼 Q를 초기화 하고 그래프 모든 정점의 진입 차수를 계산한다. DAG이기 때문에 진입 차수가 0(진출 간선만 있는)인 정점이 반드시 존재할 것이고 그 정점들을 Q에 집어 넣는다.
다음 반복문을 돌며 Q에 있던 정점들을 하나씩 빼서 정점들의 진출 간선을 검사한다. 방금 빼낸 정점(v)가 진출하는 간선을 통해 구한 도착 정점(dest)에 대해 차수 하나씩을 빼준다. Q에 들어갔다 빠져 나오면서 위상 순서가 기입된 녀석의 진입 간선들은 배제하는 것이고 이렇게 배제해가면 어느 순간 진입 차수가 0인 새로운 정점이 생긴다. 그 녀석을 또 Q에 넣어가며 위상 정렬을 한다.
진입 차수를 이용한 위상 정렬은 bfs 성격이 강하다.
마지막으로 Q가 비어 있어 루프를 탈출하게 되면 모든 정점에 대해 위상 순서가 적혔는지 검사한다. 만약 i가 그래프 정점 개수보다 크지 않다면 그래프는 DAG이 아니었던 것.
2. dfs 위상 정렬
for each v from G.vertex() {
if(l(v) = fresh){
topologicalSortDFS(v)
}
}Alg topologicalSortDFS(v)
input start vertex v, global variable vertex number n
l(v) <- visit
for each e from G.outIncidentEdge(v) {
dest <- opposite(v, e)
if(l(dest) = Fresh) {
topologicalSortDFS(dest)
} else if(!topologicalNum(w)) {
DirectedCycleException()
}
}
topologicalNum(v) <- n
n--진입 차수를 이용한 위상 정렬은 맨 앞 순서부터 쌓아가는 걸 타겟으로 한다. dfs 위상 정렬은 가장 뒷 순서를 타겟한다.
먼저 정점 v에 visit 표시를 한다.
그 후 v의 진출 간선을 본다.
- 간선 e의 도착 정점 dest를 도출하고 dest를 방문하지 않았다면, dest를 인자로 dfs 위상 정렬을 재귀 호출한다. 이 부분에서 dfs 위상 정렬이 뒷 순서를 타겟한다는 것을 알 수 있다. 만약 가장 뒷 순서가 start vetex로 함수를 수행하면 진출 간선이 없기 때문에 정점에 방문 표시 후 위상 순서를 적고 함수는 종료된다.
- dest가 visit인데 위상 순서가 없는 상태면 싸이클이다.
- dest가 visit이고 위상 순서도 있으면 다음 진출 간선을 본다.
맨 처음 아무런 정점에서 dfs를 수행한다. A라 가정하자. 위상 정렬 알고리즘 재귀 호출로 C에 도착할 것이며 C에는 진출 간선이 없기 때문에 제일 큰 번호 6이 붙는다. 다음 리턴되어 B로 돌아오고 B 역시 이제는 검사할 진출 간선이 남아 있지 않아 번호 5를 붙인다.
함수는 A로 리턴된 상태인데 A에는 아직 E로 가는 진출 간선이 남아있다. 해당 경로로 재귀 호출을 다시 진행하면 F에 도달할 것이고, F는 C로 가는 간선이 있지만, visit이고 위상 순서도 있기 때문에 넘어간다. F에 더 이상 검사할 간선이 없기 때문에 F에 4번을 붙인다. 다음 C, A에 번호를 붙인다.
for each v from G.vertex() {
if(l(v) = fresh){
topologicalSortDFS(v)
}
}이제 D만 남은 상황이지만, fresh 상태인 모든 정점에 대해 dfs 위상 정렬을 호출하고 있기 때문에 D에 마지막으로 위상 순서 1번을 마킹할 수 있다.
위상 정렬 알고리즘 성능
진입 차수 위상 정렬과 dfs 위상 정렬 모두 O(n+m) 시간 소요된다.
참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.
