9강. 그래프 (2)

1. 신장 트리 ( Spanning Tree )

• 가중 무방향 그래프에서 모든 정점을 포함하는 트리 ( 사이클 존재X )
• 특징
  • 모든 정점이 연결됨
  • 간선 수 = 정점 수 - 1
    • |V| = n 이면 간선은 n-1개

2. 최소 신장 트리 ( MST, Minimum Spanning Tree )

• 최소 신장 트리란?
  • 신장 트리 중에서 가중치의 합이 가장 작은 것
  • 간선 (u, v)마다 가중치 w(u, v)를 가진 연결된 무방향 그래프 G = (V, E)에 대해서 다음을 만족하는 트리 G' = (V, E')
• 조건
  • 간선 일부만을 선택했을 때, 선택된 간선들의 가중치 합이 최소
    • E' ⊆ E, w(E') = min { ∑(u,v)∈E' w(u,v) }

3. 최소 신장 트리를 구하는 알고리즘

• 모든 간선 중에서 정점을 모두 연결하면서 가중치의 합을 가장 작게 만드는 (n-1)개의 간선을 고르는 과정
• 욕심쟁이 방법 적용
• 종류 : 크루스칼( Kruskal ) 알고리즘, 프림( Prim ) 알고리즘

Greedy_MST(G){
  T ← ∅ ;  // 최소 신장 트리의 간선 집합
  
  while (T가 신장 트리를 만들지 않았음) { // 신장 트리를 만들때까지 반복
    // 사이클을 형성하지 않으며 최소의 가중치를 갖는 간선
    최선의 간선 (u, v) 선택;
    T ← T ∪ {(u, v)};
  }
  
  return (T);
}

4. 크루스칼 알고리즘

• 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 골라서 사이클을 형성하지 않으면 해당 간선을 추가하는 방식
• 사이클 형성 여부의 판단
  • 간선 (u, v)의 두 정점 u, v가 서로 다른 연결 성분에 속하면 사이클을 형성하지 않음
• |V|=n개의 정점이 각각의 서로 다른 연결 성분으로 구성된 상태에서 시작해서 간선을 추가할 때마다 연결 성분들이 하나씩 합쳐지고 최종적으로 하나의 연결 성분을 형성함

Kruskal(G){
  T = ∅;

  for (G의 각 정점 v에 대해) {
		정점 v로 구성된 연결 성분 초기화;
	}

  가중치가 증가하는 순으로 모든 간선을 정렬;

  for (가중치가 가장 작은 간선부터 모든 간선 (u, v)∈E에 대해서) {
    if (u와 v가 서로 다른 연결 성분에 속하면) { // 사이클을 형성하지 않으면
      T = T ∪ {(u, v)};
      u가 속한 연결 성분과 v가 속한 연결 성분을 합침;
    } else {
				간선 (u, v)를 버림;
		}
	  return (T);
	}
	
}

5. 크루스칼 알고리즘의 성능

• O(|E|log|E|)

Kruskal(G){
  T = ∅; // O(1)

  for (G의 각 정점 v에 대해) { // O(|V|)
		정점 v로 구성된 연결 성분 초기화;
	}

  가중치가 증가하는 순으로 모든 간선을 정렬; // O(|E|log|E|)

  for (가중치가 가장 작은 간선부터 모든 간선 (u, v)∈E에 대해서) { // O(|E|log|E|)
    if (u와 v가 서로 다른 연결 성분에 속하면) { // 사이클을 형성하지 않으면
      T = T ∪ {(u, v)};
      u가 속한 연결 성분과 v가 속한 연결 성분을 합침;
    } else {
				간선 (u, v)를 버림;
		}
	  return (T);
	}
	
}

6. 프림 알고리즘

• 임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해 나가는 방법
  • 이미 선택된 정점들에 부수된 가중치가 가장 작은 간선을 선택해서 추가
  • 어떤 순간에 이미 선택된 정점의 집합 S와 선택되지 않은 정점의 집합 V-S를 잇는 간선 중에서 가중치가 가장 작은 간선을 선택해서 추가하는 방법
• 임의의 정점 하나를 S로 지정한 후 시작해서 S=V가 될 때까지 S를 점점 키워 나가는 방법

Prim(G) {
    T = ∅;
    S = {1}; // 임의의 정점(여기서는 1)으로 초기화
    while (S != V) { // S가 V 전체가 될 때까지 반복
        (u, v) = S에 속한 정점 u와 V-S에 속한 정점 v 중 가중치가 최소인 간선 선택;
        T = T ∪ {(u, v)};
        S = S ∪ {v};
    }
    return T;
}

7. 프림 알고리즘의 성능

• 인접 행렬의 경우 → O(|V|²)
• 인접 리스트와 힙을 사용하는 경우 → O((|V|+|E|)log|V|)

8. 최단 경로

• 두 정점 u와 v간의 최단 경로 ( shortest path )
  • 가중 그래프에서 두 정점 u에서 v를 연결하는 경로 중 간선의 가중치의 합이 가장 작은 경
• 최단 경로 문제의 유형
  • 단일 출발점 최단 경로 ( single-source shortest path ) 문제
    • 한 지점에서 모든 다른 지점으로 가는데 가장 짧은 경로를 찾는 문제
    • 데이크스트라( Dijkstra ) 알고리즘, 벨만-포드( Bellman-Ford ) 알고리즘
  • 단일 도착점 최단 경로 문제
  • 단일 쌍 최단 경로 문제
  • 모든 쌍 최단 경로 ( all-pairs shortest path ) 문제
    • 두 지점간의 최단 경로를 찾는 문제
    • 플로이드( Floyd ) 알고리즘

9. 데이크스트라 알고리즘

• Dijkstra, 다익스트라
• 단일 출발점 최단 경로 알고리즘
  • 하나의 출발 정점에서 다른 모든 정점으로 최단 경로를 찾는 알고리즘
  • 욕심쟁이 방법이 적용된 알고리즘
  • 가정
    • 음의 가중치를 갖는 간선 없음
• 거리 d[v]
  • 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이
• 출발점에서 시작하여 거리 d[ ]가 최소인 정점을 차례대로 선택하여 최단 경로를 구하는 방법
• 초기화
  • 출발점 s의 거리 d[s]=0, 나머지 모든 정점 v의 거리 d[v]=∞, 선택된 정점의 집합 S={ }
• S=V가 될 때까지 반복
  • 미선택 정점 집합 V-S에서 거리 d[ ]가 가장 작은 정점 u를 선택
  • u의 인접 정점에 대해서
  • u를 경유하는 거리와 기존 거리를 비교해서 작은 값을 새로운 거리값으로 조정

// 입력: G=(V,E), s : 시작 정점
// 출력: d[] : s로부터 다른 모든 정점으로의 최단 경로의 길이
//       prev[] : 최단 경로를 만드는 선행 정점

Dijkstra(G, s)
{
    S = { };
    d[s] = 0;
    for (모든 정점 v ∈ V) {
        d[v] = ∞;
        prev[v] = NULL;
    }

    while (S != V) {
        d[u]가 최소인 정점 u ∈ V-S를 선택;
        S = S ∪ { u };
        for (u에 인접한 모든 정점 v) {
            if (d[v] > d[u] + W(u,v)) {
                d[v] = d[u] + W(u,v);
                prev[v] = u;
            }
        }
    }
    return (d[], prev[]);
}

10. 데이크스트라 알고리즘 성능과 특징

• 인접 행렬: O(|V|²), 인접 리스트 + 힙: O((|V|+|E|)log|V|)
• 한계
  • 음의 가중치를 갖는 간선이 없어야 함