알고리즘 9강 (그래프)

학습개요

1. 이번 시간에는 그래프를 활용한 대표적인 응용문제로서, 최소 신장 트리를 구하는 크루스칼 알고리즘과 프림 알고리즘, 그리고 단일 출발점 최단 경로를 구하는 데이크스트라 알고리즘에 대해서 학습한다.

 학습목표

1. 최소 신장 트리를 구하는 크루스칼 알고리즘의 개념과 동작을 이해하고 적용할 수 있다.
2. 최소 신장 트리를 구하는 프림 알고리즘의 개념과 동작을 이해하고 적용할 수 있다.
3. 단일 출발점 최단 경로를 구하는 데이크스트라 알고리즘의 개념, 동작 및 특성을 이해하고 적용할 수 있다.

 주요용어

1. 최소 신장 트리(minimum spanning tree)
   - 신장 트리 중에서 간선의 가중치의 합이 가장 작은 것
   - 신장 트리 → 가중 무방향 그래프에서 모든 정점을 포함하는 연결된 부분 그래프 중에서 트리인 것
2. 크루스칼 알고리즘(Kruskal algorithm)
   - 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 골라서 사이클을 형성하지 않는 간선을 추가하는 방식으로 최소 신장 트리를 만들어가는 알고리즘
3. 프림 알고리즘(Prim algorithm)
   - 임의의 한 정점에서 시작해서, 이미 선택된 정점의 집합과 선택되지 않는 정점의 집합을 잇는 간선 중에서 가중치가 가장 작은 간선을 선택해서 추가하는 방식으로 최소 신장 트리를 구하는 알고리즘
4. 최단 경로(shortest path)
   - 가중 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
5. 데이크스트라 알고리즘(Dijkstra algorithm)
   - 하나의 출발점에서 시작해서 거리값이 최소인 정점을 차례대로 선택하여 최단 경로를 구하는 알고리즘
   - 미선택 정점 집합에서 거리값이 가장 작은 정점 u를 선택하고, u의 인접 정점에 대해서 u를 경유하는 거리와 기존 거리를 비교해서 작은 값을 새로운 거리값으로 조정하는 과정을 반복적으로 거침

정리하기

1. 크루스칼 알고리즘
    ⦁ 최소 신장 트리 → 신장 트리 중에서 간선의 가중치 합이 가장 작은 것
   - 신장 트리 → 가중 무방향 그래프에서 모든 정점을 포함하는 트리
   - 크루스칼 알고리즘과 프림 알고리즘 → 욕심쟁이 방법이 적용됨
    ⦁ 크루스칼 알고리즘
   - 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 골라서 사이클을 형성하지 않으면 추가하는 방식
   - 간선 (u,v)의 두 정점 u,v가 서로 다른 연결 성분에 속하면 해당 간선은 사이클을 형성하지 않음
   - |V|=n개의 정점이 각각의 서로 다른 연결 성분으로 구성된 상태에서 시작해서 간선을 추가할 때마다 연결 성분들이 하나씩 합쳐져서 최종적으로 하나의 연결 성분을 형성함
   - 성능 → O(|E|log|E|)
2. 프림 알고리즘
    ⦁ 임의의 한 점에서 시작해서 연결된 정점을 하나씩 선택해서 추가시키는 방법
   - 이미 선택된 정점 집합 S와 미선택 정점 집합 V-S를 잇는 간선 중에서 가중치가 가장 작은 간선을 선택해서 추가하는 방식
    ⦁ 성능
   - 인접 행렬 → O(|V|2)
   - 인접 리스트와 힙 사용 → O((|V|+|E|)log|V|)
3. 데이크스트라 알고리즘
    ⦁ 최단 경로 → 가중 그래프에서 두 정점 u에서 v를 연결하는 경로 중 간선의 가중치의 합이 가장 작은 경로
    ⦁ 데이크스트라 알고리즘
   - 단일 출발점 최단 경로를 구하는 알고리즘 → 하나의 출발점에서 시작하여 거리 d[]가 최소인 정점을 선택해 나감으로써 최단 경로를 구하는 방법 → 욕심쟁이 방법 적용 → 음의 가중치를 갖는 간선이 없는 경우에만 적용 가능
   - 거리 d[v] → 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이
   - 적용 방법 → ⓐ 미선택 정점 집합 V-S에서 거리 d[]가 최소인 정점 u를 선택하고, ⓑ u의 인접 정점들에 대하여 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새 거리값으로 조정
   - 성능 → 인접 행렬 O(|V|2), 인접 리스트 O((|E|+|V|)log|V|)