[자료구조]CH8. 그래프(신장 트리와 최소 비용 신장 트리)

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부 날짜 : 21.03.13

 

<Section4> 신장 트리와 최소 비용 신장 트리

 

1. 신장 트리

 

 모든 정점이 n개인 무방향 그래프에서 정점이 n개이고 간선이 n-1개인 사이클이 없는, 트리 형태의 부분 그래프를 신장 트리(Spanning Tree)라고 한다. 즉, 간선을 최소로 이용하여 모든 정점을 연결한 그래프이다. 

깊이 우선 탐색을 이용하여 생성된 신장 트리를 깊이 우선 신장 트리, 너비 우선 탐색을 이용하여 생성된 신장 트리는 너비 우선 신장 트리라고 한다. 

 

2. 최소 비용 신장 트리

 

 가중치 그래프에서는 간선에 가중치가 주어진다. 무방향 가중치 그래프에서 신장 트리 비용은 신장 트리를 구성하는 간선 n-1개의 가중치를 합한 값이 된다. 이때 가중치 합이 최소인 신장 트리를 최소 비용 신장 트리라고 한다. 

 

 1) 크루스칼 알고리즘Ⅰ

 가중치가 높은 간선을 제거하면서 최소비용 신장 트리를 만든다.

 

 ①그래프의 모든 간선을 가중치에 따라 내림차순으로 정렬한다.

 ②그래프에서 가중치가 가장 높은 간선을 제거한다. 단, 이때 정점을 그래프에서 분리시키는 간선은 제거할 수 없으므로 이런 경우에는 그 다음으로 가중치가 높은 간선을 제거한다.  

 ③간선이 n-1개가 남을 때까지 반복한다. 

 ④그래프에 간선이 n-1개만 남으면 최소 비용 신장 트리가 완성된다. 

 

 2) 크루스칼 알고리즘Ⅱ

 가중치가 낮은 간선을 삽입하면서 최소비용 신장 트리를 만든다. 

 

 ①그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

 ②그래프에서 가중치가 가장 낮은 간선을 삽입한다. 단, 이때 사이클을 형성하는 간선은 삽입할 수 없으므로

 그 다음으로 가중치가 낮은 간선을 삽입한다.

 ③간선이 n-1개가 삽입될 때까지 반복한다.

 ④그래프에 간선이 n-1개가 되면 최소 비용 신장 트리가 완성된다. 

 

 3) 프림 알고리즘

 미리 간선을 정렬하지 않고, 하나의 정점에서 시작하여 트리를 확장해 나가는 방법이다. 

 

 ①그래프에서 시작 정점을 선택한다.

 ②선택한 정점에 부속된 간선 중에서 가중치가 가장 낮은 간선을 연결하여 트리를 확장한다. 

 ③이전에 선택한 정점과 새로 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 삽입한다. 

 단, 사이클을 형성하는 간선은 삽입할 수 없으므로 이런 경우에는 그 다음으로 가중치가 낮은 간선을 선택한다. 

 ④그래프에 간선이 n-1개 삽입될 떄까지 반복한다.

 ⑤그래프의 간선이 n-1개가 되면 최소 비용 신장 트리가 완성된다.

 

3. 최단 경로

 

 신장 트리가 아닌 가중치 그래프에서 정점과 정점을 연결하는 경로 중에서 가중치의 값이 최소인 경로이다.

최단 경로를 구하려는 가중치 그래프의 가중치는 가중치 인접 행렬에 저장한다.

가중치 인접 행렬은 2차원 배열이고, 두 정점 사이에 간선이 없으면 ∞ 값이 저장되어 있다고 가정한다. 

그리고 각 정점은 자기 자신과 이어진 간선이 없으므로 가중치 인접 행렬에서의 대각선 값은 0이다. 

 

 1) 다익스트라 최단 경로 방법

 

  시작 정점 v에서 가장 가까운 정점을 선택하여 추가하면서 추가된 정점에 의해 단축되는 경로가 있으면, 

 경로 거리를 수정하는 과정을 반복하면서 시작 정점에서 모든 정점에 대한 최단 경로를 구하는 것이다.

 

 시작정점 : v

 목표정점 : w

 추가된 정점 : u

 추가된 정점을 관리하는 집합 : S

 가중치 : weight

 

 ①경로 길이를 저장할 배열 distance 준비 :

 시작 정점으로부터 각 정점에 이르는 경로의 길이를 저장하기 위한 배열 distance를 시작정점에서의 인접 정점에 대한  가중치값을 인접행렬weight에서 구해 초기화한다.

 

 ②시작 정점 초기화 :

 시작 정점의 distance를 0으로 초기화라고 집합 S에 추가한다.

 

 ③최단 거리 수정 :

 집합 S에 속하지 않은 정점 중에서 distance가 최소인 정점 u를 찾아 집합 S에 추가한다. 

 새로운 정점 u가 추가되면, u에 인접하고 집합 S에 포함되지 않은 정점 w의 distance값을 다음 식에 따라 수정한다. 

 distance[w] ← min(distance[w] , distance[u]+weight[u][w])

 모든 정점이 S에 추가될 때까지 반복한다. 

 

 Dijkstra_shortestPath(G,v)

 

     S ←{v};

     for (i ← 0 ; i < 정점의 개수 ; i ← i+1) do

         distance[i] ← weight[v][i];

 

     for (i ← 0 ; S != V(G) ; i ← i+1 ) do { //집합 S와 정점의 집합 V(G)가 같지 않은 동안 

         u ← S에 속하지 않은 정점 중에서 distance[]가 최소인 정점;

         S ← {u}; //집합 S에 정점 u 삽입

 

         for (w ← 0 ; w < 정점의 개수 ; w ← w+1) do

               if (정점이 S에 속하지 않으면) then 

                   distance[w] ← min(distance[w] , distance[u] + weight[u][w]); //경로값을 최소인 것으로 수정

     }

 end Dijkstra_shortestPath()

     

 2) 플로이드 최단 경로 알고리즘

  모든 정점 사이의 최단 경로를 구하는 방법이다.

 정점 0부터 정점 k-1까지의 정점을 고려한 최단 거리 A^(k-1)을 구한 상태에서 다음 정점 k를 고려할 때,

 A^(k-1)[v][w]와 A^(k-1)[v][k]+A^(k-1)[k][w] 중에서 작은 값에 따라 최단 경로가 수정된다.

 

 Floyd_shortestPath(G,v)

   

    // 인접 행렬 weight를 배열 A에 복사하여 초기화를 먼저 해준다.

 

    for (k ←0;k<=n-1;k←k+1) do //n-1은 거쳐가는 정점의 인덱스를 나타낸다

        for (v ← 0; v<=n;v←v+1) do

            for (w←0;w<=n-1;w←w+1) do

                A[v][w]←min(A[v][w],A[v][k]+A[k][w]);

 end Floyd_shortestPath()