Graph Algoltim

그래프 알고리즘들

1. 최소 신장 트리 (MST)

---

최소 신장 트리(Minimum Spanning Tree)는 가중치 그래프에서 모든 정점을 연결하면서, 간선의 가중치 합이 최소가 되는 트리를 의미합니다. 최소 신장 트리는 다음 두 가지 알고리즘으로 구할 수 있습니다.

(1) 크루스칼 알고리즘 (Kruskal's Algorithm)

• 작동 방식:

  1. 모든 간선을 가중치 기준으로 오름차순 정렬.
  2. 간선을 하나씩 선택하면서 사이클이 생기지 않도록 연결.
  3. 정점이 모두 연결될 때까지 반복.

• 필요 자료구조: 유니온-파인드(Union-Find) 자료구조를 사용하여 사이클을 검사.

• 시간 복잡도: $O(E \log E)$ (간선 정렬 비용이 주요 작업).

• 예시

  1. 간선 정렬: (A, B, 1), (B, C, 2), (A, C, 3).
  2. 첫 번째 간선 (A, B, 1) 추가.
  3. 두 번째 간선 (B, C, 2) 추가.
  4. 세 번째 간선 (A, C, 3)은 사이클이 생기므로 제외.

• C 언어 구현:

#include <stdio.h>
#include <stdlib.h>

// 간선을 나타내는 구조체
typedef struct {
    int u, v, weight; // u: 시작 정점, v: 끝 정점, weight: 가중치
} Edge;

// 특정 정점의 루트 부모를 찾는 함수 (경로 압축 사용)
int find(int parent[], int i) {
    if (parent[i] != i)
        parent[i] = find(parent, parent[i]); // 부모를 재귀적으로 갱신하며 루트 찾기
    return parent[i];
}

// 두 집합을 합치는 함수 (랭크를 사용한 합집합 연산)
void unionSet(int parent[], int rank[], int x, int y) {
    int rootX = find(parent, x); // x의 루트 찾기
    int rootY = find(parent, y); // y의 루트 찾기

    // 랭크를 비교하여 랭크가 낮은 쪽을 높은 쪽에 연결
    if (rank[rootX] < rank[rootY])
        parent[rootX] = rootY;
    else if (rank[rootX] > rank[rootY])
        parent[rootY] = rootX;
    else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

// 크루스칼 알고리즘 구현
void kruskal(Edge edges[], int V, int E) {
    int parent[V], rank[V]; // 부모 배열과 랭크 배열 초기화

    // 초기화: 각 정점은 자기 자신이 부모, 랭크는 0
    for (int i = 0; i < V; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    // 간선을 가중치 기준으로 오름차순 정렬
    qsort(edges, E, sizeof(Edge), [](const void* a, const void* b) {
        return ((Edge*)a)->weight - ((Edge*)b)->weight;
    });

    printf("MST에 포함된 간선:\n");
    int mstWeight = 0; // 최소 신장 트리의 총 가중치

    // 모든 간선을 순회하며 MST 구성
    for (int i = 0; i < E; i++) {
        int u = edges[i].u; // 간선의 시작 정점
        int v = edges[i].v; // 간선의 끝 정점

        // 두 정점이 같은 집합에 속하지 않을 경우 간선을 추가
        if (find(parent, u) != find(parent, v)) {
            printf("간선 (%d, %d) = %d\n", u, v, edges[i].weight);
            unionSet(parent, rank, u, v); // 두 정점의 집합 합치기
            mstWeight += edges[i].weight; // 가중치 누적
        }
    }
    printf("MST의 총 가중치: %d\n", mstWeight);
}

(2) 프림 알고리즘 (Prim's Algorithm)

• 작동 방식:

  1. 임의의 시작 정점에서 시작.
  2. 해당 정점과 연결된 간선 중 최소 가중치의 간선을 선택하여 연결.
  3. 방문하지 않은 정점이 없을 때까지 반복.

• 필요 자료구조: 최소 힙(Min Heap)을 사용하여 최소 가중치 간선 선택.

• 시간 복잡도: $O(E \log V)$ (힙에 간선 삽입/삭제 비용).

• 예시

  1. 시작 정점 $A$에서 최소 가중치 간선 (A, B, 1) 선택.
  2. 다음으로 방문 가능한 간선 중 최소 가중치 간선 (B, C, 2) 선택.
  3. 반복하여 모든 정점을 연결.

• C 언어 구현:

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 5 // 정점의 개수

// MST 집합에 포함되지 않은 정점 중 최소 키 값을 가지는 정점을 반환
int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        // 최소 키 값을 찾으며, MST 집합에 포함되지 않은 정점만 고려
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// 프림 알고리즘 구현
void primMST(int graph[V][V]) {
    int parent[V]; // MST에 포함된 간선 정보를 저장
    int key[V]; // 각 정점에 대한 최소 가중치 값 저장
    bool mstSet[V]; // MST에 포함 여부를 저장

    // 초기화: 모든 키 값을 무한대로 설정, MST 집합은 비어 있음
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0; // 시작 정점의 키 값은 0
    parent[0] = -1; // 시작 정점은 부모가 없음

    // MST에 모든 정점이 포함될 때까지 반복
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet); // 최소 키 값을 가지는 정점 선택
        mstSet[u] = true; // 선택된 정점을 MST 집합에 추가

        // 선택된 정점과 인접한 정점들의 키 값 업데이트
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u; // v의 부모를 u로 설정
                key[v] = graph[u][v]; // v의 키 값 갱신
            }
        }
    }

    // MST 출력
    printf("간선 \t가중치\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
    }
}

---

2. 최단 경로 알고리즘

---

(1) 다익스트라 알고리즘 (Dijkstra's Algorithm)

• 목적: 단일 시작 정점에서 다른 모든 정점까지의 최단 경로를 구함.

• 작동 방식:

  1. 시작 정점의 거리를 0으로 설정하고, 다른 모든 정점의 거리를 무한대로 초기화.
  2. 현재 방문한 정점의 인접 정점에 대해, 더 짧은 경로가 발견되면 거리 갱신.
  3. 모든 정점을 방문할 때까지 반복.

• 필요 자료구조: 우선순위 큐(Priority Queue).

• 시간 복잡도: $O(V \log V + E)$.

• 제한 사항: 음의 가중치 간선이 존재하면 사용 불가능.

• C 언어 구현:

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define V 9 // 그래프의 정점 수

// 최단 거리 값을 가지는 정점의 인덱스를 반환하는 함수
int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < V; v++) {
        // sptSet에 포함되지 않은 정점 중에서 최소 거리 값을 가진 정점 찾기
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// 최종 계산된 거리 배열을 출력하는 함수
void printSolution(int dist[]) {
    printf("정점 \t 시작점으로부터의 거리\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t %d\n", i, dist[i]);
    }
}

// 다익스트라 알고리즘을 구현하는 함수
void dijkstra(int graph[V][V], int src) {
    int dist[V]; // 출발점에서 각 정점까지의 최단 거리 값을 저장하는 배열
    bool sptSet[V]; // sptSet[i]는 정점 i가 최단 경로 트리에 포함되었는지 여부를 나타냄

    // 모든 정점의 거리 값을 무한대로 초기화하고 sptSet을 false로 초기화
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    // 시작 정점의 거리는 항상 0
    dist[src] = 0;

    // 모든 정점을 처리할 때까지 반복
    for (int count = 0; count < V - 1; count++) {
        // 아직 처리되지 않은 정점 중에서 최단 거리 값을 가지는 정점을 선택
        int u = minDistance(dist, sptSet);

        // 선택된 정점을 sptSet에 포함
        sptSet[u] = true;

        // 선택된 정점과 인접한 정점의 거리 값을 업데이트
        for (int v = 0; v < V; v++) {
            // sptSet에 포함되지 않은 정점 중에서:
            // 1. 그래프에 간선이 존재하고
            // 2. 선택된 정점의 거리 값이 무한이 아니며
            // 3. 선택된 정점을 통해 더 짧은 경로가 발견되면 거리 값 갱신
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 계산된 최단 거리 값 출력
    printSolution(dist);
}

int main() {
    // 그래프의 인접 행렬 표현
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };

    // 0번 정점을 시작점으로 다익스트라 알고리즘 수행
    dijkstra(graph, 0);

    return 0;
}

(2) 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

• 목적: 단일 시작 정점에서 다른 모든 정점까지의 최단 경로를 구함.

• 작동 방식:

  1. 모든 간선을 최대 $V - 1$번 반복하여 업데이트.
  2. 음의 가중치 간선이 존재할 경우, 이를 탐지하기 위해 추가 반복 수행.

• 필요 조건: 음의 가중치 간선이 있을 때도 작동 가능.

• 시간 복잡도: $O(VE)$.

(3) 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

• 목적: 모든 정점 쌍 간의 최단 경로를 구함.

• 작동 방식:

  1. 정점 $k$를 중간 경로로 고려하여 모든 정점 $i$에서 $j$로의 최단 경로를 갱신.
  2. $D[i][j] = \min(D[i][j], D[i][k] + D[k][j])$.

• 시간 복잡도: $O(V^3)$.

---

3. 위상 정렬 (Topological Sorting)

---

• 목적: 유향 비순환 그래프(DAG)에서 정점의 순서를 결정.

• 작동 방식:

  1. 모든 정점의 진입 차수(In-degree)를 계산.
  2. 진입 차수가 0인 정점을 큐에 삽입.
  3. 큐에서 정점을 꺼내 연결된 간선 제거.
  4. 진입 차수가 0이 된 정점을 큐에 추가.
  5. 큐가 빌 때까지 반복.

• 시간 복잡도: $O(V + E)$.

• 활용 사례: 작업 스케줄링, 컴파일러에서 의존성 분석.

---

4. 그래프 탐색 알고리즘

---

(1) 너비 우선 탐색 (BFS)

• 작동 방식: 큐(Queue)를 사용하여 정점을 레벨 순으로 탐색.
• 시간 복잡도: $O(V + E)$.
• 활용 사례: 최단 경로 탐색(비가중치 그래프).

(2) 깊이 우선 탐색 (DFS)

• 작동 방식: 스택(Stack) 또는 재귀를 사용하여 정점을 깊게 탐색.
• 시간 복잡도: $O(V + E)$.
• 활용 사례: 사이클 탐지, 연결 요소 개수 찾기.