Lecture 18 - Graph(2)

---

위상 정렬 (Topological Sorting)

우선 싸이클이 없는 유향 그래프에서 정의되는 문제이다.  간단하게 살펴보면 모든 정점을 정렬하되 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치해야 하는 정렬이다. 이때 복수의 위상 순서가 존재할 수 있다.

라면 끓이기에서 위상순서를 나타낸 그래프를 보면 위와 같다.

---

Kahn 기반 알고리즘

다음은 Kahn 알고리즘 기반 위상 정렬의 psuedo code이다.

topologicalSort1(G, v)
{
	for ← 1 to n {
	진입간선이 없는 정점 u를 선택한다;
	A[i] ← u;
	정점 u와, u의 진출간선을 모두 제거한다;
   }
   ▷ 이 시점에 배열 A[1…n]에는 정점들이 위상정렬되어 있다
}

수행 시간은 Θ(|V|+|E|)이고 진입간선과 진출간선을 보면 다음과 같이 정점에 연결이 되어있다.

알고리즘 진행과정을 그래프 예시로 확인하자.

---

DFS 기반 알고리즘

다음은 DFS 알고리즘 기반의 위상정렬 알고리즘 psuedo code이다.

topologicalSort2(G)
{
	for each v∈V
		visited[v] ← NO;
	for each v∈V ▷ 정점의 순서는 무관
		if (visited[v] = NO) then DFS-TS(v) ;
}
DFS-TS(v)
{
	visited[v] ← YES;
	for each x∈L(v) ▷ L(v): v의 인접 리스트
		if (visited[x] = NO) then DFS-TS(x) ;
	연결 리스트 R의 맨 앞에 정점 v를 삽입한다;
}

---

시간복잡도

위상 정렬 알고리즘의 대표적인 방법으로는 Kahn 알고리즘과 DFS (깊이 우선 탐색) 기반 알고리즘이 있다.

1. Kahn 알고리즘
Kahn 알고리즘은 진입 차수가 0인 정점을 큐에 삽입하고, 그래프에서 해당 정점과 연결된 간선을 제거한 후, 다시 진입 차수가 0인 정점을 찾아 큐에 삽입하는 과정을 반복한다.

수행 시간 분석:
- 모든 정점의 진입 차수를 계산하는 데에 O(V) 시간이 소요된다 (V는 정점의 개수).
- 정점들을 큐에 삽입하고 큐에서 꺼내는 데에 O(V) 시간이 소요된다.
- 모든 간선에 대해 진입 차수를 감소시키는 데에 O(E) 시간이 소요된다 (E는 간선의 개수).

따라서, Kahn 알고리즘의 전체 시간 복잡도는 O(V + E)이다.

2. DFS 기반 알고리즘
DFS 기반 알고리즘은 깊이 우선 탐색을 사용하여 그래프를 탐색하고, 역순으로 정점들을 저장해 위상 정렬을 완성한다.

수행 시간 분석:
- 그래프의 모든 정점에 대해 DFS를 수행하므로 O(V) 시간이 소요된다.
- 각 정점에서 인접한 정점을 방문하는 데에 O(E) 시간이 소요된다.

따라서, DFS 기반 위상 정렬 알고리즘의 전체 시간 복잡도는 O(V + E)이다.

결론적으로, 위상 정렬 알고리즘의 시간 복잡도는 O(V + E)로, 정점과 간선의 개수에 선형적으로 비례한다.

---

최단 경로

가중치가 있는 유향 그래프에 대해 두 정점 사이의 경로 중 가중치 합이 최소가 되는 경로를 구하는 문제로 무향 그래프는 양쪽 방향으로 간선이 다 있다고 볼 수도 있다.

 

1. 단일 시작점 최단 경로 문제

   ① 음의 가중치를 허용하지 않는 경우 -> 다익스트라 알고리즘

   ② 음의 가중치를 허용하는 경우 -> 벨만-포드 알고리즘

        -그러나 벨만-포드 알고리즘도 싸이클에서의 가중치 합이 음이 되면 적용할 수가 없다. 해당 사이클을 반복하여 특정 경로의 가중치             합을 음의 무한대로 보낼 수 있기 때문이다.

   ③ 싸이클이 없는 그래프의 경우

 

2. 모든 정점 쌍에 대한 최단 경로 문제 -> 플로이드-워샬 알고리즘

---

Dijkstra

Dijkstra(G, r)
▷ G=(V, E): 주어진 그래프
▷ r: 시작으로 삼을 정점
{
	S ← Ф ; ▷ S : 정점 집합
	for each u∈V
		d[u] ← ∞ ;
	d[r] ← 0 ;
	while (S≠V){ ▷ n회 순환된다
		u ← extractMin(V-S, d) ;
		S ← S ∪{u};
		for each v∈L(u) ▷ L(u) : u로부터 연결된 정점들의 집합
			if (v∈V-S and d[u] +w[u, v] < d[v] ) then {
				d[v] ← d[u] + w[u, v];	#relaxation(이완)
				prev[v] ← u;
               }
	}
}
extractMin(Q, d[])
{
	집합 Q에서 d값이 가장 작은 정점 u를 리턴한다 ;
}

진행과정을 그래프에서 확인하면 다음과 같다.

---