[알고리즘] ep5-3) 방향그래프

ㅁ방향그래프(directed graph): 모든 간선이 방향간선인 그래프

 

응용: 일방통행 도로, 항공노선, 작업 스케줄링

 

방향 DFS 알고리즘에서, 네 종류의 간선이 발생한다

1. 트리간선(tree edges): 새로운 정점 방문 시 사용되는 간선

2. 후향간선(back edges): 현재 정점에서 이미 방문한 정점으로 돌아가는 간선

3. 전향간선(forward edges): 조상의 정점에서 자손의 정점으로 향하는 간선

4. 교차간선(cross edges): 같은 레벨 또는 다른 서브트리의 정점으로 향하는 간선

 

방향그래프 G의 두 정점 u와 v에 대해 만약 u에서 v로의 방향경로가 존재한다면, "u는 v에 도달한다(reach)" 또는 "v는 u로부터 도달 가능(reachable)하다"라고 말한다

s를 루트로 하는 DFS 트리: s로부터 방향경로를 통해 도달 가능한 정점들을 표시

 

 

방향그래프 G의 어느 두 정점 u와 v에 대해서나 u는 v에 도달하며 v는 u에 도달하면, G를 강연결(Strong Connected)이라고 말한다 - 즉, 어느 정점에서든지 다른 모든 정점에 도달 가능 (그래프의 모든 정점이 서로 도달 가능)

G는 강연결성이 있다

 

 

<강연결 검사 알고리즘> O(n + m)

1. 타잔 알고리즘

• DFS로 그래프를 탐색하며 각 정점의 발견 순서를 기록
• 탐색 중 스택을 사용하여 방문한 정점을 저장
• 각 정점에 대해 DFS를 수행하며, 탐색 도중에 발견한 강연결 부분 그래프를 분리

 

2. 코사라주의 알고리즘

• 그래프 G에 대해 모든 정점을 대상으로 DFS를 수행하고, 각 정점의 완료 시간을 기록
• 그래프 G의 모든 간선 방향을 뒤집어 역그래프 G^T를 생성
• 완료 시간이 가장 늦은 정점부터 G^T에서 DFS를 수행하며, 이 과정에서 강연결 부분 그래프를 탐색

 

 

 

1. G의 임의의 정점 v를 선택

2. G의 v로부터 DFS를 수행

- 방문되지 않은 정점 w가 있다면, false를 반환

3. G의 간선들을 모두 역행시킨 그래프 G'를 얻음

4. G의 v로부터 DFS를 수행

- 방문되지 않은 정점 w가 있다면, false를 반환

- 그렇지 않으면, true를 반환

 

 

ㅇ강연결요소(SCC, Strongly Connected Component): 방향그래프에서 각 정점으로부터 다른 모든 정점으로 도달할 수 있는 최대의 부그래프

DFS를 사용하여 O(n + m) 시간에 계산가능(이중연결성, biconnectivity)와 유사

 

 

 

ㅇ이행적 폐쇄(transitive closure): 특정한 정점 쌍 사이에 직접적인 경로가 없어도 여러 간선을 거쳐 도달 가능한 모든 경로를 포함하는 그래프

 

정확히는 다음을 만족하는 방향그래프 G*가 이행적 폐쇄 그래프이다

- G*는 G와 동일한 정점들로 구성

- G에 u로부터 v != u 로의 방향경로가 존재한다면 G*에 u로부터 v로의 방향간선이 존재

삼단논법 느낌이다

 

이행적 폐쇄는 방향그래프에 관한 도달 가능성 정보를 제공한다

e.g. 컴퓨터 네트워크에서, "노드 a에서 노드 b로 메시지를 보낼 수 있을까?"

 

이행적 폐쇄의 계산은 각 정점에서 출발하여 DFS를 수행할 수 있다 - O(n(n + m))

대안으로, DP를 사용할 수 있다 (플로이드-와샬 알고리즘)

원리: "A에서 B로 가는 길과 B에서 C로 가는 길이 있다면, A에서 C로 가는 길이 있다"

ㅇ플로이드-와샬(Floyd-Warshall) 이행적 폐쇄: 가중치 방향 그래프의 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘

동적 프로그래밍(DP)을 사용하여 그래프의 인접 행렬을 반복적으로 갱신하면서 최단 경로를 계산

(각 노드마다 가장 짧은 거리를 구한다고 생각하면 된다)

정점들을 1, 2, ..., n으로 번호를 매기고 1, 2, ..., k로 매겨진 정점들만 경유 정점으로 사용하는 경로들을 고려한다

시간복잡도: O(n^3) - 여기서 n은 정점의 수

 

 

과정1

과정2

 

 

ㅇ동적 프로그래밍(DP, Dynamilc Programming): 복잡한 문제를 더 간단한 하위 문제로 나누고, 그 하위 문제들의 결과를 저장하여 중복 계산을 피함으로써 효율적으로 문제를 해결하는 방법

언뜻 보기에 많은 시간(심지어 지수 시간)이 소요될 것 같은 문제에 주로 적용한다

[적용의 조건 3가지]

1. 부문제 단순성(simple subproblems): 부문제들이 j, k, l, m 등과 같은 몇 개의 변수로 정의될 수 있는 경우

2. 부문제 최적성(subproblem optimality): 전체 최적치가 최적의 부문제들에 의해 정의될 수 있는 경우

3, 부문제 중복성(subproblem overlap): 부문제들이 독립적이 아니라 상호 겹쳐질 경우 (따라서 해가 "상향식"으로 구축되어야 함)

e.g. 피보나치 수열에서 n번째 수 찾기, 그래프의 이행적 폐쇄 계산

 

[DP의 두 가지 주요 구현 방법]

- 메모이제이션(memoization): 재귀호출

하향식 접근 방식(Top-Down Approach)이다

 

- 타뷸레이션(tabulation): 반복문

상향식 접근 방식(Bottom-Up Approach)이다

 

 

 

ㅇ방향 비싸이클 그래프(DAG, directed acyclic graph): 방향싸이클이 존재하지 않는 방향그래프

응용 예시

- C++ 클래스 간의 상속 or 자바 인터페이스,

- 교과목 간의 선수 관계

- 프로젝트의 부분 작업들 간의 스케줄링 제약

- 사전의 용어 간의 상호의존성

- 액셀과 같은 스프레드시트에서 수식 간의 상호의존성

 

 

ㅇ위상순서(topological order): DAG의 모든 정점들을 순서대로 나열한 것

모든 i < j 인 간선 (vi, vj)에 대해 정점들을 번호로 나열한 것

다시 말하자면 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 앞에 나와야 한다 (그래프 내의 모든 간선이 위상순서를 유지하도록 정점들이 순서대로 배열된 것)

위상순서는 작업의 의존 관계를 나타내는 그래프에서 작업을 어떤 순서로 수행해야 하는지를 결정해야 할 때 사용된다 만약 어떤 작업이 다른 작업에 의존하고 있다면, 그 의존 작업을 먼저 수행해야 하기 때문이다

e.g. 작업스케줄링 방향그래프에서 위상순서는 작업들의 우선 순서 제약을 만족하는 작업 순서이다

 

"그래프가 DAG면 위상순서를 가지며, 그 역도 참이다"

 

 

ㅇ위상정렬(topological sort): DAG로부터 위상순서를 얻는 절차

2가지 알고리즘이 있다

 

1. 칸 알고리즘 - 정점의 진입차수(in-degree)를 이용

• 각 정점의 진입 차수를 계산한다
• 진입 차수가 0인 정점들을 큐에 넣는다
• 큐에서 정점을 하나씩 꺼내면서 해당 정점과 연결된 모든 간선을 제거하고, 연결된 정점들의 진입 차수를 감소시킨다
• 진입 차수가 0이 된 정점들을 다시 큐에 넣는다
• 큐가 빌 때까지 이 과정을 반복하면 위상순서를 얻을 수 있다
• 만약 위상순서가 다 처리되지 않았는데도 큐가 비었다면, 그래프에는 싸이클이 존재하는 것이다

 

과정1

과정2

 

 

 

2. DFS 확장

• 모든 정점에 대해 DFS를 수행하여 종료 시점을 기록한다
• DFS가 종료되는 시점에 정점을 스택에 쌓는다
• 모든 DFS가 끝난 후, 스택에서 정점을 꺼내면 위상순서가 된다

 

과정1

과정2

과정3

 

 

"2가지 알고리즘 모두 O(n + m) 시간과 O(n)의 공간 소요"

+ G가 DAG인 경우, G의 위상순서를 계산

+ G에 방향싸이클이 존재할 경우, 일부 정점의  순위를 매기지 않은 채로 정지

 

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan)