11 그래프2 (C언어로 쉽게 풀어쓴 자료구조)

11.1 최소 비용 신장 트리

신장 트리

신장 트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리

 

1.모든 정점들이 연결되어 있어야 하고
2.사이클을 포함해서는 안된다

=>그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다

 

-깊이우선/너비우선 탐색 도중 사용된 간선들만 표시하면 만들 수 있다

-그래프의 최소 연결 부분 그래프

• 최소: 간선의 수가 가장 적다(최소 n-1개의 간선)

-통신 네트워크 구축에 많이 사용

-각 링크의 구축 비용이 같지 않기 때문에 가장 적은 링크만 사용한다고 해서 최소 비용이 얻어지는 것은 아니다

 

 

최소 비용 신장 트리

최소 비용 신장 트리(MST: minimum spanning tree): 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것

-사용된 간선들의 가중치 합이 최소인 신장트리

-ex)도로 건설, 전기 회로, 통신, 배관

-Kruskal과 Prim이 제안한 알고리즘

• 간선의 가중치 합이 최소
• 반드시 (n-1)개의 간선만 사용
• 사이클 포함X

p.398 quiz

11.2 Kruskal의 MST 알고리즘

-탐욕적인 방법(greedy method) 이용: 선택할 때마다 그 순간 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법

-그 해답이 반드시 전역적으로 최적이라는 보장이 없음->항상 최적의 해답을 주는지 검증해야 한다(Kruskal의 알고리즘은 이미 검증됨~)

1.먼저 그래프의 간선들을 가중치의 오름차순으로 정렬한다
2.정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아서
3.현재의 최소 비용 신장 트리의 집합에 추가한다
4.만약 사이클을 현성하면 그 간선은 제외된다

 

사이클을 어떻게 피할까?

-지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사하여야 한다

=>union-find 알고리즘

 

union-find 연산

union(x, y): 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다

find(x): 원소 x가 속해있는 집합을 반환한다

 

ex) S={1, 2, 3, 4, 5, 6}

일단 집합의 원소를 하나씩 분리하여 독자적인 집합으로 만든다

{1}, {2}, {3}, {4}, {5}, {6}

 

union(1,4), union(5,2)

{1,4}, {5,2}, {3}, {6}

 

union(4,5}, union(3,6)

{1,4,5,2},{3,6}

 

union-find 연산의 구현

비트 벡터, 배열, 연결 리스트를 이용하여 구현할 수 있다. 우리는 가장 효율적인 방법인 트리형태를 사용하여 구현해보자!

 

"부모 포인터 표현": 각 노드에 대해 그 노드의 부모에 대한 포인터만 저장하는 것

-이 방법은 왼쪽/오른쪽 자식을 찾는 것에는 부적절하지만 "두 노드가 같은 트리에 있습니까?"와 같은 질문에는 적절하다

-포인터를 사용하지 않고 1차원 배열로 구현 가능

-배열은 부모 노드의 인덱스를 저장한다

-배열의 값이 -1이면 부모 노드가 없다

 

초기 상태

union(A, B)

union(C, H)

 

#define MAX_VERTICES 100

int parent[MAX_VERTICES]; //부모 노드

//초기화
void set_init(int n)
{
    for (int i=0; i<n; i++)
        parent[i] = -1;
}

//curr가 속하는 집합을 반환한다
int set_find(int curr)
{
    if (parent[curr] == -1)
        return curr;
    while (parent[curr] != -1) 
        curr = parent[curr];
    return curr;
}

//두 개의 원소가 속한 집합을 합친다
void set_union(int a, int b)
{
    int root1 = set_find(a); //노드 a의 루트를 찾는다
    int root2 = set_find(b); //노드 b의 루트를 찾는다
    if (root1 != root2)
        parent[root1] = root2;
}

 

Kruskal의 알고리즘 구현

-간선들을 정렬해야하므로 그래프가 간선들의 집합으로 저장되어있다

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

#define TRUE 1
#define FALSE 0

#define MAX_VERTICES 100
#define INF 1000

int parent[MAX_VERTICES]; //부모 노드

//초기화
void set_init(int n)
{
    for (int i=0; i<n; i++)
        parent[i] = -1;
}

//curr가 속하는 집합을 반환한다
int set_find(int curr)
{
    if (parent[curr] == -1)
        return curr;
    while (parent[curr] != -1) 
        curr = parent[curr];
    return curr;
}

//두 개의 원소가 속한 집합을 합친다
void set_union(int a, int b)
{
    int root1 = set_find(a); //노드 a의 루트를 찾는다
    int root2 = set_find(b); //노드 b의 루트를 찾는다
    if (root1 != root2)
        parent[root1] = root2;
}

//간선을 나타내는 구조체
struct Edge {
    int start, end, weight;
};

typedef struct GraphType
{
    int n; //간선의 개수
    int nvertex; //정점의 개수
    struct Edge edges[2 * MAX_VERTICES];
} GraphType;

//그래프 초기화
void graph_init(GraphType* g)
{
    g->n = g->nvertex = 0;
    for (int i=0; i<2*MAX_VERTICES; i++) {
        g->edges[i].start = 0;
        g->edges[i].end = 0;
        g->edges[i].weight = INF;
    }
}

//간선 삽입 연산
void insert_edge(GraphType* g, int start, int end, int w)
{
    g->edges[g->n].start = start;
    g->edges[g->n].end = end;
    g->edges[g->n].weight = w;
    g->n++;
}

//qsort에 사용되는 함수
int compare(const void* a, const void* b)
{
    struct Edge* x = (struct Edge*)a;
    struct Edge* y = (struct Edge*)b;
    return (x->weight - y->weight);
}

//kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType *g)
{
    int edge_accepted = 0; //현재까지 선택된 간선의 수
    int uset, vset; //정점 u와 정점 v의 집합 번호
    struct Edge e;

    set_init(g->nvertex); //집합 초기화
    qsort(g->edges, g->n, sizeof(struct Edge), compare);

    printf("크루스칼 최소 신장 트리 알고리즘 \n");
    int i=0;
    while (edge_accepted < (g->nvertex -1)) //간선의 수<(n-1)
    {
        e=g->edges[i];
        uset = set_find(e.start); //정점 u의 집합 번호
        vset = set_find(e.end); //정점 v의 집합 번호
        if (uset != vset) { //서로 속한 집합이 다르면
            printf("간선 (%d,%d) %d 선택\n", e.start, e.end, e.weight);
            edge_accepted++;
            set_union(uset, vset); //두 개의 집합을 합친다
        }
        i++;
    }
}

int main(void)
{
    GraphType *g;
    g=(GraphType *)malloc(sizeof(GraphType));
    graph_init(g);

    g->nvertex = 7;
    insert_edge(g, 0, 1, 29);
    insert_edge(g, 1, 2, 16);
    insert_edge(g, 2, 3, 12);
    insert_edge(g, 3, 4, 22);
    insert_edge(g, 4, 5, 27);
    insert_edge(g, 5, 0, 10);
    insert_edge(g, 6, 1, 15);
    insert_edge(g, 6, 3, 18);
    insert_edge(g, 6, 4, 25);

    kruskal(g);
    free(g);
    return 0;
}

 

시간 복잡도 분석

O(|e|log2|e|) : 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다

p.408 quiz

 

11.3 Prim의 MST 알고리즘

Prim의 알고리즘: 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법

-시작 단계에서는 시작 정점만이 신장 트리 집합에 포함

-앞 단계에서 만들어진 신장 트리 집합에, 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장한다

-트리가 n-1개의 간선을 가질 때까지 계속된다

 

Kruskal vs Prim

Kruskal의 알고리즘: 간선을 기반으로 하는 알고리즘, 이전 단계에서 만들어진 신장트리와는 상관없이 무조건 최저 간선만을 선택

Prim의 알고리즘: 정점을 기반으로 하는 알고리즘, 이전 단계에서 만들어진 신장 트리를 확장하는 방식

 

 

Prim의 알고리즘의 구현

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

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L

typedef struct GraphType
{
    int n; //정점의 개수
    int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int selected[MAX_VERTICES];
int distance[MAX_VERTICES]; //정점의 개수 크기의 배열. 현재까지 알려진 신장트리 정점집합에서 각 정점까지의 거리를 가지고 있다

//최소 dist[v] 값을 갖는 정점을 반환
int get_min_vertex(int n)
{
    int v, i;
    // 첫 번째 루프: 선택되지 않은 정점 중 하나를 찾아서 v에 할당
    for (i=0; i<n; i++) {
        if (!selected[i]) {
            v=i; // 첫 번째로 발견한 선택되지 않은 정점을 v에 저장
            break;
        }
        // 두 번째 루프: 선택되지 않은 정점 중 dist[v] 값이 최소인 정점을 찾음
        for (i=0; i<n; i++)
            if (!selected[i] && (distance[i] < distance[v])) // 선택되지 않았고, 거리가 더 작은 정점이 있으면
                v=i;                                         // 그 정점을 v에 저장
        return (v);
    }
}

void prim(GraphType* g, int s)
{
    int i, u, v;

    // 모든 정점의 초기 거리를 무한대로 설정
    for(u=0; u<g->n; u++)
        distance[u] = INF;
    
    // 시작 정점의 거리 값을 0으로 설정
    distance[s] = 0;

    // 모든 정점을 처리할 때까지 반복
    for (i=0; i<g->n; i++) {
        // 선택되지 않은 정점 중 가장 작은 거리 값을 가진 정점을 찾음
        u = get_min_vertex(g->n);
        selected[u] = TRUE; // 정점 u를 선택 상태로 표시

        // 만약 선택된 정점의 거리가 무한대(INF)라면, 더 이상 연결된 정점이 없으므로 종료
        if (distance[u] == INF) return;
        // 현재 선택된 정점을 MST에 추가
        printf("정점 %d 추가\n", u);

        // 선택된 정점 u의 인접한 정점 v를 탐색
        for (v=0; v<g->n; v++)
            // 정점 u에서 정점 v로 가는 간선이 존재하고(selected[v]가 선택되지 않음)
            // 그 간선의 가중치가 기존 distance[v]보다 작으면 업데이트
            if (g->weight[u][v] != INF) // u와 v 사이의 간선이 존재할 때
                if (!selected[v] && g->weight[u][v] < distance[v])
                    distance[v] = g->weight[u][v]; // 더 작은 가중치로 갱신
    }
}

int main(void)
{
    GraphType g = {7,
    {{ 0, 29, INF, INF, INF, 10, INF},
    { 29, 0, 16, INF, INF, INF, 15},
    { INF, 16, 0, 12, INF, INF, INF},
    { INF, INF, 12, 0, 22, INF, 18},
    { INF, INF, INF, 22, 0, 27, 25},
    { 10, INF, INF, INF, 27, 0, INF},
    { INF, 15, INF, 18, 25, INF, 0}}
    };
    prim(&g, 0);
    return 0;
}

 

Prim의 알고리즘의 분석

O(n^2)의 복잡도: 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로

Kruskal 알고리즘의 복잡도: O(elog2e)이므로,

희소그래프->Kruskal이 적합

밀집그래프->Prim이 적합

p.414 quiz

11.4 최단 경로

최단 경로(shortest path) 문제: 네트워크에서 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제

 

가중치는 가중치 인접 행렬에 저장되어 있다

-Dijkstra 알고리즘: 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다

-Floyd 알고리즘: 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다

 

인접행렬 vs 가정치 인접 행렬: 인접행렬에는 간선이 없으면 인접행렬의 값이 0인데 가중치 인접행렬에서는 간선의 가중치가 0일 수도 있기 때문에 무한대의 값을 가중치 인접 행렬에 저장한다

 

11.5 Dijkstra의 최단 경로 알고리즘

Dijkstar의 최단 경로 알고리즘: 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단경로를 찾는 알고리즘

-최단경로는 경로의 길이 순으로 구해진다

-distance 배열: 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열

-집합 S: 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합

 

1/알고리즘의 각 단계에서 S안에 있지 않은 정점 중에서 가장 distance 값이 작은 정점을 S에 추가한다

현재 distance값이 가장 작은 정점이 u이기 때문에 다른 정점은 정점 u까지의 거리보다 항상 더 길 것이다

2.새로운 정점 u가 S에 추가되면, S에 있지 않은 다른 정점들의 distance 값을 수정한다

(u를 거쳐서 정점까지 가는 거리 vs 기존의 거리 를 비교한 후 더 작은 거리로 distance 값을 수정한다)

 

 

ex)

 

Dijkstra 알고리즘 구현

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

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000 /* 무한대 (연결이 없는 경우)*/

typedef struct GraphType
{
    int n; //정점의 개수
    int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;

int distance[MAX_VERTICES]; /* 시작정점으로부터의 최단경로 거리 */
int found[MAX_VERTICES]; /* 방문한 정점 표시 */

int choose(int distance[], int n, int foundp[])
{
    int i, min, minpos;
    min = INT_MAX;
    minpos = -1;
    for (i=0; i<n; i++)
        if (distance[i] < min && !found[i]) {
            min = distance[i];
            minpos = i;
        }
        return minpos;
}

void print_status(GraphType* g)
{
    static int step = 1;
    printf("STEP %d: ", step++);
    printf("distance: ");
    for (int i=0; i<g->n; i++) {
        if (distance[i] == INF)
            printf(" * ");
        else
            printf("%2d ", distance[i]);
    }
    printf("\n");
    printf(" found: ");
    for (int i=0; i<g->n; i++)
        printf("%2d ", found[i]);
    printf("\n\n");
}

void shortest_path(GraphType *g, int start)
{
    int i, u, w;
    for (i=0; i<g->n; i++)
    {
        distance[i] = g->weight[start][i];
        found[i] = FALSE;
    }
    found[start] = TRUE; /* 시작 정점 방문 표시 */
    distance[start] = 0;
    for (i=0; i<g->n-1; i++) {
        print_status(g);
        u = choose(distance, g->n, found);
        found[u] = TRUE;
        for (w=0; w<g->n; w++)
            if (!found[w])
                if (distance[u] + g->weight[u][w]<distance[w])
                    distance[w] = distance[u] + g->weight[u][w];
    }
}

int main(void)
{
     GraphType g = {7,
    {{ 0, 7, INF, INF, 3, 10, INF},
    { 7, 0, 4, 10, 2, 6, INF},
    { INF, 4, 0, 2, INF, INF, INF},
    { INF, 10, 2, 0, 11, 9, 4},
    { 3, 2, INF, 11, 0, INF, 5},
    { 10, 6, INF, 9, INF, 0, INF},
    { INF, INF, INF, 4, 5, INF, 0}}
    };
    shortest_path(&g, 0);
    return 0;
}

-최소값을 선택하는 choose 함수를 우선순위큐로 대치하면 더 빠르게 수행할 수 있다

 

Dijkstra의 분석

O(n^2): 네트워크에 n개의 정점이 있다면 주반복문 n번, 내부반복문 n번 반복

 

p.424 거릿값이 같은 때는 인덱스가 작은 애를 먼저 선택한다고 가정한다

 

 

11.6 Floyd의 최단 경로 알고리즘

Floyd의 최단 경로 알고리즘: 그래프에 존재하는 모든 정점 사이의 최단 경로를 한 번에 모두 찾아주는 알고리즘

-2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성

-인접행렬 weight:

• i==j이면 weight[i][j]=0
• i와 j 사이에 간선이 존재하지 않으면 weight[i][j]=∞
• i와 j 사이에 간선이 존재하면 weight[i][j]=i와 j 사이의 간선의 가중치

floyd(G):
    
    for k <- 0 to n-1
        for i <- 0 to n-1
            for j <- 0 to n-1
                A[i][j] = min(A[i][j], A[i][k], A[k][j])

 

 

A^(k-1)까지는 완벽한 최단 거리가 구해져있다고 가정하자.

k번째 정점이 추가되는 상황을 생각해보자! 0~k까지의 정점만 사용해서 정점 i->j로 가는 상황은 두 가지로 나뉜다

(1) k를 거치지 않고 가기 : A^(k-1)[i][j]

(2) k를 거쳐서 가기: A^(k-1)[i][k] + A^(k-1)[k][j]

이거 두 개를 비교해서 더 작은 게 최종 경로가 될 것이다 -> A^k[i][j] = min(A^(k-1)[i][j], A^(k-1)[i][k] + A^(k-1)[k][j])

 

 

Floyd 최단 경로 알고리즘의 구현

 

Floyd 최단 경로 알고리즘의 분석

O(n^3): Dijkstra 알고리즘을 n번 반복해야 하므로
-매우 간결한 반복 구문을 사용하므로 Dijkstra의 알고리즘보다 상당히 빨리 모든 정점 간의 최단 경로를 찾을 수 있다

 

p.430 quiz

11.7 위상 정렬

위상 정렬(topological sort): 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

 

위상정렬 알고리즘

1)먼저 진입차수가 0인 정점을 선택

2)선택된 정점과 여기에 부착된 모든 간선을 삭제

3)모든 정점이 선택/삭제 되면 반복 종료

 

 

위상정렬 알고리즘의 구현

// 위상 정렬을 수행한다
int topo_sort(GraphType *g)
{
    int i;
    StackType s;
    GraphNode *node;

    // 모든 정점의 진입 차수를 계산
    int *in_degree = (int *)malloc(g->n * sizeof(int));
    // 초기화
    for (i=0; i<g->n; i++) {
        in_degree[i] = 0;
    }
    for (i=0; i < g->n; i++) {
        GraphNode *node = g->adj_list[i]; // 정점 i에서 나오는 간선들
        while (node != NULL) {
            in_degree[node->vertex]++;
            node = node->link;
        }
    }

    // 진입 차수가 0인 정점을 스택에 삽입
    init(&s);
    // 후보 정점을 스택에 저장
    for (i=0; i<g->n; i++) {
        if (in_degree[i] == 0) push(&s, i);
    }
    // 위상 순서를 생성
    while (!is_empty(&s)) {
        int w;
        w = pop(&s);
        printf("정점 %d ->", w); // 정점 출력
        node = g->adj_list[w]; // 각 정점의 진입 차수를 변경
        while (node != NULL) {
            int u = node->vertex;
            in_degree[u]--; // 진입 차수를 감소
            if (in_degree[u] == 0) push(&s, u);
            node = node->link; // 다음 정점
        }
    }
    free(in_degree);
    printf("\n");
    return (i == g->n); // 반환값이 1이면 성공, 0이면 실패
}

p.437 quiz