[강의노트] 방향그래프 - 1

방향 그래프 - 1

지금까지 무방향 그래프의 구현과 수정, 그리고 순회알고리즘 DFS와 BFS에 대해서 다루어보았다.

이번에 배울 것은 간선에 방향성이 존재하는 방향그래프이다.

 

방향그래프

방향그래프란 모든 간선이 방향간선인 그래프이다. 무방향 그래프에서 방향성만 추가된것이므로 개념은 어렵지않다..

방향그래프에서 단순하다는 개념은 간선의 수를 m , 정점의 수를 n이라 할 때

m <= n(n-1) 을 만족하면 그래프 G는 단순한 그래프라고 한다.

 

이 말의 의미는 싸이클이 없고, 한 정점에서 다른 정점으로 가는 경로가 유일하다는 의미이다. 수식의 의미를 생각해보면

간선을 만들어내려면 양 끝점이 필요하다. 한 정점을 선택하는 경우의 수는 n가지이고 다른 한 점을 고를 수 있는 경우의 수는 n-1 가지이다.

따라서 간선을 만들어낼 수 있는 최대 경우의 수는 n(n-1)인데 이것은 싸이클이 없고, 정점과 정점을 잇는 방향 간선이 유일하다는 가정하에 만족한다.

 

진입간선과 진출간선을 각각 별도의 인접리스트로 보관하면 각각 집합의 크기에 비례한 시간에 조사가 가능하다

즉 이전에 무방향그래프에서는 간선의 방향성이 없으므로 정점에 대한 간선의 인접리스트를 하나로 보관했는데,

이제 방향성을 가지기때문에 각 정점은 진입,진출 두 간선에 대한 인접리스트를 가져야한다

 

방향그래프에서의 DFS

이전에 무방향그래프를 순회하는 DFS를 배웠었다.

방향그래프에서의 DFS 및 BFS 를 적용하려면, 주어진 방향만을 따라 순회하도록 설정해주면 된다.

무방향그래프와 다르게 방향 DFS에서는 전향간선과 교차간선이라는 새로운 개념이 생겼다.

왼쪽의 그래프에서 A노드를 기준으로 해서 순회 과정을 트리로 나타내면 오른쪽 그림으로 나타낼 수 있다.

이때 D노드에서 A노드로 거슬러 올라가는 간선을 후향간선이라고 하고, 반대로 A노드에서 E노드로 향하는 간선을 전향간선이라고 한다.

또한 E노드에서 D노드로 향하는 간선은 같은 level의 이웃노드로 향하는 간선인데 이것은 BFS에서 배웠듯이 교차간선이라고 한다.

도달 가능성

한 정점을 기준으로해서 도달할 수 있는 정점을 표시하는 트리를 생성할 수 있다. 이때 DFS와 BFS 알고리즘이 활용된다.

 

 

강연결성 

그래프의 강연결성은 그래프의 모든 정점들이 강하게 연결되어 있다는 뜻이다.

즉 그래프의 어느 두 정점 u와 v를 선택하더라도, 두 정점은 서로 도달할 수 있는 경로가 존재할 때 강연결성을 가진 그래프라고 한다.

그래프의 강연결성을 판단하는 방법은 각 정점을 시작 정점으로 해서 DFS 를 돌리면 되지만 시간복잡도는 O(n*(n+m))

따라서 더 간단한 방법이 필요하다

그것은 바로 강연결성 검사 알고리즘을 이용하는 것.

강연결성 검사 알고리즘

핵심적인 부분은 3번이다. G의 간선들을 모두 역행시킨 그래프 G`을 통해 DFS를 수행하는 것이 핵심 아이디어가 된다

 

4-2 을 살펴보면 G`의 v로부터 DFS를 수행했을때, 모든 정점을 방문한다면 그래프 G는 강연결성을 가진다고 한다.

하지만 임의의 정점 v에 대해서만 검사한 것인데 어떻게 O(n+m)의 시행만으로 강연결성을 보장하는 것일까?

밑에 그림을 보자

그림을 잘 살펴보면 임의의 노드 v를 기준으로 진출하는 방향으로 모든 정점을 갈 수 있고 진입방향으로 모든 정점이 v에 도달 할 수 있다.

이 경우에 어떤 두 정점을 골라도 서로 갈 수 있는 경로가 존재하는 것이기때문에 강연결성을 가지게 되는 것이다.

 

강연결 요소 찾기

강연결성을 가지는 최대의 부그래프를 강연결 요소라고 말한다

이 또한 DFS를 사용해서 O(n+m) 시간에 계산 가능하다

 

 

이행적 폐쇄

이행적 폐쇄는 도달 가능성에 대한 정보를 제공한다. 정의를 읽으면 조금 복잡하게 생각될 수 있는데

쉽게 말하면 그래프G에서 두 정점 v,u 를 잇는 경로가 존재한다면, 그래프 G*에선 경로를 스킵하고 출발점과

도착점을 끝점으로 하는 간선을 그리는 것이다. 이렇게 생성된 간선은 도달가능성에 대한 정보를 보여준다

 

여기서 동적프로그래밍으로 Floyd-Warshall 알고리즘이 나오는데 실행시간이 O(n*(n+m)) 이다.

원리는 삼단논법과 유사하다. A 에서 B로 가는 길이 있고, B에서 C로 가는 길이 있다면 A에서 C로 가는길이 있다를 이용

 

이행적폐쇄는 그래프의 도달가능성을 표시하는 알고리즘이다. 즉 그래프의 모든 두 정점에 대해 도달가능한 정점들은 간선을 삽입한다.

이행적폐쇄를 그래프에 표시하는 알고리즘은 두가지 단계를 거친다.  

 

1. 먼저 정점들에 번호를 매겨준다.

2. 1,2,..., k로 번호가 매겨진 정점들만 이동할 수 있는 경로를 고려한다. 이때 k는 1부터 n까지 늘리면서 반복

 

그림에서 보여주는거처럼 임의의 정점 i 에서 정점 j 까지 가는 경로를 생각해보자.

 

1부터 k-1 까지 번호 매겨진 정점들만 사용해서 i부터 k까지 가는 경로와 k부터 j까지 가는 경로가 있다면

아까 말한 3단논법 원리처럼 k를 거쳐서 (즉 1부터 k까지 번호 매겨진 정점들을 사용해서) i -> k -> j 의 경로를 구할 수 있게 되는 것이다.

 

방금 설명한 알고리즘에 대한 수도코드이다.

왼쪽의 설명을 참조하면 어렵지않게 이해할 수 있다.

G_k-1 그래프의 정점 i,k 에 대한 경로와 k,j에 대한 경로를 확인하고, 만약 G_k에 vi,vj 경로가 없으면 삽입한다.

 

아까 설명한 

 

1부터 k-1 까지 번호 매겨진 정점들만 사용해서 i부터 k까지 가는 경로와 k부터 j까지 가는 경로가 있다면

아까 말한 3단논법 원리처럼 k를 거쳐서 (즉 1부터 k까지 번호 매겨진 정점들을 사용해서)

i -> k -> j 의 경로를 구할 수 있게 되는 것이다.

 

이 부분이다.

 

수행예시는 start vertex가 A -> B -> C -> D -> E로 이동하면서

각각의 수행에서는 start vertex를 통해서 갈 수 있는 간선을 삽입한다.

어려운내용은 없으므로 좀 더 알고리즘을 구체적으로 이해하기 위해 참고하면 좋을 것 같다.

 

 

다음 포스트에서는 방향 그래프의 구현에 대해서 다루어보겠다.