그래프(2) - 크루스칼, 프림, 데이크스트라 알고리즘

최소 신장 트리(Minimum Spanning Tree) 

 

• 신장 트리
  • 가중 무방향 그래프에서 모든 정점을 포함하는 트리
• 최소 신장 트리
  • 신장 트리 중 간선 가중치의 합이 가장 작은 트리
  • 그래프 G=(V,E) 에 대해, 트리 G′=(V′,E′)는 V′=V, E′⊆E 

 

크루스칼 알고리즘

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

과정 

 

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬
2. 제일 작은 간선부터 하나씩 선택
3. 선택할 때마다
   • 사이클이 생기는지 확인
   • 사이클이 생기지 않으면 간선 추가
   • 사이클이 생기면 버림
4. 간선이 정점수 − 1개 가 되면 끝낸다

Kruskal(G):
    T = ∅
    for each vertex v in G:
        정점 v로 구성된 연결 성분 초기화

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

    for each edge (u, v) in G.E (가중치가 가장 작은 것부터):
        if u와 v가 서로 다른 연결 성분에 속하면:
            T = T ∪ {(u, v)}
            u가 속한 연결 성분과 v가 속한 연결 성분을 합침
        else:
            간선 (u, v)를 버림

    return T

성능

• 연결 성분 초기화: MAKE-SET(v) 를 V번 호출 → O(V)
• 간선 정렬: O(E log E)
• for (모든 간선 (u,v) 에 대해)
  → E번 반복
  → 각 iteration 마다 FIND/UNION 비용 O(log E) → 전체 O(E log E)
• 전체 시간 복잡도: O(E log E) ≈ O(E log V)

 

프림 알고리즘 

• 임의의 한 정점에서 시작해서 연결된 정점을 하나씩 선택해나가는 방법
• 이미 선택된 정점들에 부수된 가중치가 가장 작은 간선을 선택해서 추가

과정 

 

1. 시작 정점 선택
   • 임의의 정점 r 선택
   • 선택된 정점 집합 S = {r}, MST 간선 집합 T = ∅
2. 반복 (|S| < |V| 동안)
   • S 와 V–S 를 잇는 모든 간선 중 최소 가중치 간선 (u,v) 선택
   • T ← T ∪ {(u,v)}
   • S ← S ∪ {v}
3. 종료 조건
   1. |S| = |V| 이 되면 MST 완성 → T 반환

Prim(G):
    T = ∅
    S = {1}        // 임의의 시작 정점(예: 1)으로 초기화
    while S ≠ V:
        // S 안의 정점 u와 S 밖의 정점 v를 잇는 최소 가중치 간선 (u, v) 선택
        (u, v) = argmin { w(u,v) | u ∈ S, v ∈ V–S }
        T = T ∪ {(u, v)}
        S = S ∪ {v}
    return T

성능

 

• 인접 행렬 사용 시: O(|V|²)
• 인접 리스트 + 힙(우선순위 큐) 사용 시: O((|V| + |E|) · log |V|)

최단경로 문제

• 가중 그래프에서 두 정점 u→v를 잇는 경로 중 간선 합이 최소인 경로
• 단일 출발점 최단경로: 데이크스트라, 벨만-포드 알고리즘
• 모든 상 최단 경로: 플로이드 알고리즘 

데이크스트라(Dijkstra) 알고리즘 

 

• 단일 출발점 최단 경로 알고리즘 → 하나의 출발 정점에서 다른 모든 정점으로 최단 경로를 찾는 알고리즘
• Greedy 방법이 적용: 매 단계 “가장 가까운” 미선택 정점부터 고정
• 음의 가중치 간선이 없는 그래프에만 적용 가능
• 거리 배열 d[v]: 출발점에서 S(선택된 정점 집합)를 거쳐 v까지의 현재까지 알려진 최단 거리

과정

 

1. 초기화
   • 출발 정점 s의 거리는 0 → d[s] = 0
   • 나머지 모든 정점의 거리는 무한대 → d[v] = ∞
   • 방문한 정점 집합 S = {} (아직 아무것도 확정 안 됨)
2. 반복 (방문 안한 정점 중 제일 가까운 애부터)
   • 아직 확정되지 않은 정점들 중, d[v] 값이 가장 작은 정점 u를 선택
   • 정점 u는 이제 최단 경로가 확정되므로 S에 추가
   • u와 인접한 모든 정점 v에 대해
     • d[u] + W(u,v) < d[v]라면
     • d[v]를 갱신하고,
     • prev[v] = u로 경로 추적 정보를 저장
3. 종료
   • 모든 정점이 S에 포함되면 d[]에 최단 거리 확정
   • d[v]: 출발 정점 s에서 v까지의 최단 거리
   • prev[v]: v로 가는 최단 경로에서 직전 정점

// 입력: 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) {
        // S에 포함되지 않은 정점 중 d[u]가 최소인 정점 u 선택
        u ∈ V–S 중 d[u] 최소인 정점 선택;
        S = S ∪ {u};

        // u에 인접한 모든 정점 v에 대해 이완 처리
        for (u에 인접한 모든 정점 v) {
            if (d[v] > d[u] + W(u, v)) {
                d[v] = d[u] + W(u, v);
                prev[v] = u;
            }
        }
    }

    return (d[], prev[]);
}

성능 

 

• 인접 행렬 사용: O(|V|²)
• 인접 리스트 + 우선순위 큐(힙) 사용: O((|V| + |E|) log |V|)