그래프 응용(최소신장트리), Prim 알고리즘 C언어 구현

지난 시간에 그래프의 기초 개념을 다루었으니 그래프 응용 시간을 가져보겠다.

이번 시간에 할 건 그래프의 최소비용 신장트리의 구성이다.

그전에 우리는 무방향 그래프만 다룰 것이고, 시작에 앞서 용어를 몇 개 짚고 가자

가중치 그래프

좌 : 가중치 그래프, 우 : 인접행렬 표현

: 정점을 잇는 간선에 값이 부여된 그래프이다.

인접행렬을 보면 0과 0이상의 값, 무한대로 3가지의 값의 표현이 있다.

 

0 : 자기 자신을 가리키는 간선이 없으니 0

0 이상의 값 : 가중치, weight라고 부른다.

무한대 : this 정점에서 해당 정점까지 한 번에 가지 못한다는 걸 의미한다.

 

지난 시간에는 정점이 간선으로 연결되어 있다는 사실로, 인접행렬을 0과 1로 표현했지만

이제는 간선에 값이 주어지기에 1이 아닌, 그 값을 인접행렬에 넣는다.

 

신장트리(Spanning Tree)

: 한 그래프에서 모든 정점을 포함하는 트리를 의미한다.

수업시간에 허겁지겁 적느라 글씨가 개판이다.

여기서 트리란, 그래프의 한 종류로 사이클(Cycle)이 없다는 특징을 지닌다. 

사이클(Cycle) : 특정 정점에서 빙그르르 돌고 돌아 처음 출발한 정점으로 도달하면 사이클이 있다고 표함.

 

위 사진을 보면 한 그래프에서 신장트리는 여러 개 나올 수 있다는 것을 볼 수 있다.

그러나 이 신장트리 중 가중치 합이 가장 적은 것을 최소비용 신장트리(Minimum Spanning Tree)라 한다

 

다시 한번, 최소비용 신장트리를 되짚고 가자

지니는 특성은 다음과 같다.

 

1. 그래프의 모든 정점이 포함된 트리

2. 신장트리 중 가중치의 합이 가장 작은 신장트리

3. 사이클이 존재하지 않음

그럼 그 많은 신장트리 중에서 최소비용 신장트리를 어떻게 구하는가?

MST를 구성하는 방법

- Prim 알고리즘

- Kruskal 알고리즘

두 알고리즘 모두 "그리디 알고리즘", 또는 "탐욕 알고리즘"이라 불린다.

크루스칼 알고리즘과 그리디 알고리즘은 다음에 자세히 다루겠다.

 

이번 게시물에서는 Prim 알고리즘만 보자.

Prim 알고리즘

Prim 방법을 통해 MST를 구성하는 모습

음.. 일단 그림을 보며 말로 설명을 해보고 코드를 보며 이해해 보자.

 

저 그래프를 보면, 정점의 수는 7개인 것을 확인할 수 있다.

우리가 만들 최소비용 신장트리의 정점의 개수는 7개가 나와야 한다.

그리고 사이클이 없어야 하고, 가중치의 합 중 그 값이 가장 작은 신장트리가 되어야 한다는 걸 잊지 말자

 

처음 시작은 아무 정점에서 해도 상관없다. 우리는 이해하기 쉽게 0부터 출발해 보겠다.

위 그래프의 인접행렬이다.

0에서 연결되어 있는 정점 중에 가장 작은 가중치는 7이다.

그 7은 정점 6이다.

그럼 0과 6을 이어준다.

 

이게 한 스텝이다.

 

다음, 0과 6 중에서 연결된 정점 중 가장 작은 가중치는 10이다.

그 10은 정점 1과 연결되어 있는 정점 5의 가중치이다.

그럼 0과 5를 이어준다.

 

딱 한 번만. 진짜 딱 한 번만 더하고 필살기 ...을 쓰겠다.

 

0과 5와 6, 세 정점을 잇는 가중치 가운데 가장 적은 값은 13이다.

그 13은 정점 6과 연결되어 있는 정점 2의 가중치이다.

그럼 6과 2를 이어준다.

여기까지 했음.

이제 알아서 하시고,

 

아무튼 최종적으로 다음과 같은 최소비용 신장 트리가 구성이 된다.

위 그래프의 MST이다.

정점 개수 7개, 사이클 X, 가중치들 합 중에서 가장 작은 신장트리.

이로써 최소비용 신장트리를 만든 것이다.

 

Prim 알고리즘 전체 코드 (C언어)

이제 코딩을 해보자.

우선 무한대 값을 1000으로 표현하였고, 0이 아니라면, 즉 간선이 연결되어 있다면 가중치 값을 랜덤으로 주어 인접행렬을 만들었다.

선택된 정점들의 집합 표현을 위해 selected 배열을, MST 각 정점의 부모를 저장하는 배열이다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 100
#define Infinite 1000

// 그래프의 인접행렬 생성 함수
void createGraph(int arr[][MAX_SIZE], int vertex, int edge) {
    int start, destination;
    // 인접행렬 초기화
    for (int i = 0; i < vertex; i++) {
        for (int j = 0; j < vertex; j++) {
            arr[i][j] = 0;
        }
    }

    // 간선 정보 입력
    for (int i = 0; i < edge; i++) {
        printf("간선 %d 입력 (출발지 도착지): ", i + 1);
        scanf("%d %d", &start, &destination);

        // 유효한 정점 범위인지 확인
        if (start >= 0 && start < vertex && destination >= 0 && destination < vertex) {
            arr[start][destination] = arr[destination][start] = 1;
            // 무방향 그래프의 경우 반대 방향도 1로 설정
        }
        else {
            printf("유효하지 않은 정점입니다.\\\\n");
            i--; // 잘못된 간선 입력이 있을 경우, 다시 입력하도록 i를 감소시킴
        }
    }
}

// 인접행렬 출력 함수
void displayGraph(int arr[][MAX_SIZE], int vertex) {
    printf("\t");
    for (int i = 0; i < vertex; i++) {
        printf("\\t%d", i);
    }
    printf("\n");
    for (int i = 0; i < vertex; i++) {
        printf("\t%d", i);
        for (int j = 0; j < vertex; j++) {
            printf("\t%d", arr[i][j]);
        }
        printf("\n");
    }
}

// prim알고리즘
int primMST(int arr[][MAX_SIZE], int vertex) {
    int selected[vertex]; // 선택된 정점들의 배열
    int minWeight, minVertex=0, totalWeight=0;

    // 배열 초기화
    for (int i = 0; i < vertex; i++) {
        selected[i] = 0; // 선택되지 않음
    }

    // 임의의 시작 정점 선택
    int startVertex = 0;
    selected[startVertex] = 1;

    // 정점이 V-1개가 선택될 때까지 반복
    for (int count = 0; count < vertex - 1; count++) {
        minWeight = Infinite;

        // 선택된 정점과 선택되지 않은 정점 사이의 가중치가 최소인 간선 선택
        for (int i = 0; i < vertex; i++) {
            if (selected[i]) {
                for (int j = 0; j < vertex; j++) {
                    if (!selected[j] && arr[i][j] && arr[i][j] < minWeight) {
                        minWeight = arr[i][j];
                        minVertex = j;
                    }
                }
            }
        }

        selected[minVertex] = 1; // 정점 선택
        totalWeight += minWeight; // 가중치 누적
    }

    return totalWeight;
}

int main(void) {
    srand((unsigned int)time(NULL));
    int vertex, edge;

    int arr[MAX_SIZE][MAX_SIZE] = { 0 };

    printf("정점의 개수를 입력하세요: ");
    scanf("%d", &vertex);

    printf("간선의 개수를 입력하세요: ");
    scanf("%d", &edge);

    createGraph(arr, vertex, edge);

    // 인접행렬 가중치 부여(랜덤으로)
    for (int i = 0; i < vertex; i++) {
        for (int j = i; j < vertex; j++) {
            if (i == j) {
                arr[i][j] = 0;
            }
            else if (arr[i][j] == 1) {
                arr[i][j] = rand() % 20 + 1;
                arr[j][i] = arr[i][j];
            }
            else {
                arr[i][j] = Infinite;
                arr[j][i] = Infinite;
            }
        }
    }
    displayGraph(arr, vertex);
    
    int mst = primMST(arr, vertex);
    printf("최소 신장 트리의 가중치 합: %d\n", mst);

    return 0;
}

랜덤으로 받았기 때문에 출력 한 번 찍어보고, 그 예시로 실제 MST를 그려보아 결과를 확인해 보겠다.

위 예제와 동일하게 무한대, 0이 잘 출력되고 나머지는 랜덤 값으로 가중치가 지정된 모습

처음에 0에서 시작해서 가장 낮은 가중치 값은 9이다.

그 가중치 9는 정점 5이다.

0과 5를 연결한다.

 

정점 0과 정점 5랑 연결된 정점들 중 가중치 값이 가장 적은 것은 7이다.

7은 정점 5와 정점 4의 가중치 값이다.

5와 4를 연결해 준다. 0 5 4 완성

 

...

 

해서 쭉 연결한다.

위 랜덤 인접행렬에 따른 최소신장트리 완성

이렇게 최소신장트리가 완성이 되었다.

가중치들의 합은 43인데, 프로그램 출력값과 동일하게 43이 나오는 모습을 볼 수 있다.

 

알고리즘 분석

인접행렬을 이용한 방식이기에 수행시간은 최소 O(n^2)이다.

더불어 primMST 함수에서 프림 알고리즘은 for 문을 3번 이용했기에 수행시간이 O(n^3)이 된다.