알고리즘 - 19 그래프 알고리즘 (신장 트리, 위상 정렬)

최소 신장 트리

1. 최소 신장 트리 개요

2. 프림 알고리즘

3. 크루스칼 알고리즘

 

 

최소 신장트리 minimum spanning tree

조건

- 무향 연결 그래프 -> 연결 그래프 : 모든 정점간에 경로가 존재하는 그래프

 

트리

- 싸이클이 없는 연결 그래프

- n개의 정점을 가진 트리는 항상 n-1개의 간선을 가짐

 

그래프 G(V, E)의 신장 트리

- 정점 집합 V를 그대로 두고, 간선을 |V| - 1개만 남겨 트리로 구성한것

 -> 아래의 좌측 그림에서 정점 개수는 9개로 사이클을 제거 -> 우측 그림은 9-1 = 8개의 간선을 가진 신장 트리

 

G의 최소 신장 트리

- G의 신장트리들 중 간선의 합이 최소인 신장 트리

-> 좌측 그래프의 간선을 지우는것에 따라 여러 개의 신장 트리가 만들어 질 수 있음. 

 

최소 비용 신장 트리를 만드는 알고리즘

1. 프림 알고리즘

2. 크루스칼 알고리즘

 

 

프림 알고리즘

- 집합 S를 공집합에서 시작하여 모든 정점을 포함할 떄 까지( 즉, S = V가 될 떄 까지) 키워나감

 -> 맨 처음 정점을 제외하고 정점을 하나 더할 떄 마다 간선이 하나씩 확정 됨

 

프림 알고리즘 동작 방법

1. 그래프에서 하나의 정점을 선택하여 트리를 만듬

2. 그래프의 모든 간선이 들어있는 집합을 만듬

3. 모든 정점이 트리에 포함되어 있지 않는 동안 트리와 연결된 간선 가운데 트리 속의 두 정점을 연결하지 않는 가장 가중치가 작은 간선을 트리에 추가함

 

 

프림 알고리즘 유사 코드

- 프림 알고리즘은 그리디 알고리즘의 일종 -> 그리디 알고리즘으로 최적해를 보장하는 드문 예

Prime (G, r)
{
    S <- 공집합;     // 정점 r을 방문되었다고 표시하고, 집합 S에 포함시킴
    while (S != V){
       S에서 V-S를 연결하는 간선들 중에 최소 길이의 간선 (x, y)을 찾는다. x \in S,  y \in V-S
       정점 y를 방문되었다고 표시하고, 집합 S에 포함시킨다.
    }

}

 

프림 알고리즘 동작과정

 

 

 

 

 

크루스칼 알고리즘

- 싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소 신장 트리를 만듦

 -> n개의 정점으로 트리를 만드는데 n-1개의 간선이 필요함

 -> 최소에는 간선이 하나도 없는 상태에서 시작하여 n-1개의 산언을 더하면 더함

 * 프림 알고리즘은 정점을 기준으로 동작한다면, 크루수칼 알고리즘은 간선을 중심으로 동작

 

크루스칼 알고리즘 작동 예

 

 

 

 

 

 

위상 정렬 개요

- 완수해야할 여러가지 일이 있고 이들 간에 상호 선후 관계가 있는 경우

 -> 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것

ex 1. 특정 수강 과목에 선수 과목이 있는 예

 - 선수 과목 부터 수강해야 함

 - 수강 시 위상 정렬을 통해 올바른 수강 순서를 찾아 낼 수 있음

ex 2. 라면 끓이는 순서 예

 

위상 정렬의 조건

- 싸이클이 없는 유향 그래프

 

위상 정렬 topological sorting

1. 모든 정점을 일렬로 나열함

2. 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치해야함

3. 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재함

 

진입 간선

- u에 연결된 간선들 중 u로 향하는 간선

진출 간선

- u에 연결된 간선들 중 u로부터 나가는 가선

 

위상 정렬의 예시

- 아래의 좌측 그래프에 대한 위상 정렬의 예 2개

위상 정렬 유사 코드

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

 

위상 정렬 알고리즘 작동 예