[책 정리] Chapter 10. 그래프

10.1 그래프란?

그래프 소개

그래프(graph): 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조

그래프의 역사

수학자 오일러(Euler)는 "모든 다리를 한 번만 건너서 출발했던 장소로 돌아올 수 있는가?" 라는 문제에 대한 답을 그래프 이론을 이용해서 증명했음
-> 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 경로만 존재함
정점(vertex): 위치
간선(edge): 위치 간의 관계
오일러 경로(Eulerian tour): 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로

그래프로 표현할 수 있는 것들

1. 도로
2. 영역 간 인접 관계
3. 선수 과목

그래프의 용어

그래프: 정점(vertex)와 간선(edge)들의 집합, G=(V, E)
V(G): 그래프 G의 정점들의 집합, 여러 가지 특성을 가질 수 있는 객체를 의미(= 노드(node))
E(G): 그래프 G의 간선들의 집합, 정점들 간의 관계(= 링크(link))

간선의 종류
1. 무방향 그래프(undirected graph)
-> 간선을 통해서 양 방향으로 갈 수 있음을 나타내며 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현 ((A, B) = (B, A))
2. 방향 그래프(directed graph)
-> 간선을 통해서 한쪽 방향으로만 갈 수 있음을 나타내며 정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>와 같이 표현 (<A, B> != <B, A>)

간선에 가중치 부여 유무
1. 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프(= 네트워크(network))

부분 그래프(subgraph): 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프

인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점

차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
-> 무방향 그래프에 존재하는 정점의 모든 차수를 합하면 그래프의 간선 수의 2배가 됨
진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수
진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수
-> 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합은 그래프의 간선의 수가 됨

경로 길이(path length): 경로를 구성하는데 사용된 간선의 수
단순 경로(simple path): 경로 중에서 반복되는 간선이 없는 경우
사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

1. 연결 그래프(connected graph): 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 그래프
   -> 트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프임

2. 비연결 그래프(unconnected graph): 항상 경로가 존재하는 것이 아닌 그래프

3. 완전 그래프(complete graph): 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프 -> 정점 n개면, 간선은 n(n-1)/2이 됨

   10.2 그래프 추상 자료형

   <ADT 10.2.1> 그래프

   객체: 정점의 집합과 간선의 집합
   연산
   	create_graph() ::= 그래프를 생성
      init(g) ::= 그래프 g를 초기화
      insert_vertex(g,v) ::= 그래프 g에 정점 v를 삽입
      insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v)를 삽입
      delete_vertex(g,v) ::= 그래프 g의 정점 v를 삭제
      delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v)를 삭제
      is_empty(g) ::= 그래프 g가 공백 상태인지 확인
      adjacent(v) ::= 정점 v에 인접한 정점들의 리스트를 반환
      destory_graph(g) ::= 그래프 g를 제거

10.3 그래프의 표현 방법

인접 행렬

인접 행렬(adjacency matrix): 2차원 배열로 그래프를 메모리에 표현

• 인접 행렬의 대각선 성분은 모두 0으로 표시 -> 자체 간선을 허용하지 않기 때문
• 무방향 그래프에서 인접 행렬은 대칭 행렬이 됨 -> 간선(i,j)는 정점 i에서 정점 j로의 연결뿐만 아니라 정점 j에서 정점 i로의 연결을 동시에 의미하기 때문
• 방향 그래프의 인접 행렬은 대칭이 아님
• n개의 정점을 가진 그래프를 인접 행렬로 표현하기 위해서는 간선의 수와 상관없이 항상 $n^2$개의 메모리 공간이 필요함
  -> 따라서, 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우 적합함
  -> 그래프 내에 적은 숫자의 간선만 가지는 희소 그래프(sparse graph)의 경우에는 메모리 낭비가 크므로 적합하지 않음

인접 행렬의 시간복잡도
1. 두 정점을 연결하는 간선의 존재 여부를 $O(1)$ 시간 안에 즉시 알 수 있는 장점이 있음
2. 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 $O(n)$의 연산에 의해 알 수 있음
-> 정점 i에 대한 차수 -> $degree(i) = \sum_{k=0}^{n-1}M[i][k]$, 인접 행렬의 i번째 행에 있는 값을 모두 더하면 됨
3. 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하기 때문에 $O(n^2)$의 시간이 요구 됨

인접 행렬을 이용한 그래프 추상 자료형의 구현

#define MAX_VERTICES 50
typedef struct GraphType{
	int n; // 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g){
    g->n = 0;
    for(int r=0;r<MAX_VERTICES;r++){
    	for(int c=0;c<MAX_VERTICES;c++){
        	g->adj_mat[r][c] = 0;
        }
    }
}

// 정점 삽입 연산
void insert_vertex(GraphType *g, int v){
	if((g->n+1) > MAX_VERTICES){
    	fprintf(stderr,"그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

// 간선 삽입 연산
void insert_edge(GraphType *g, int start, int end){
	if(g->n <= start || g->n <= end ){
    	fprintf(stderr,"그래프: 정점 번호 오류");
        return;
    }
	g->adj_mat[start][end] = g->adj_mat[end][start] = 1; // 무방향 그래프
}

인접 리스트

인접 리스트(adjacency list): 그래프를 표현함에 있어 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것

• 각 연결 리스트는 헤드 포인터를 가지고 있음, 헤드 포인터들은 하나의 배열로 구성됨
• 인접 리스트의 각각의 연결 리스트에 정점들이 입력되는 순서에 따라 연결 리스트내에서 정점들의 순서가 달라질 수 있음 -> 그래프의 일관성을 유지하기 위해 인접 리스트가 정점의 오름차순으로 연결된다고 가정
• 정점의 수가 n개, 간선의 수가 e개인 무방향 그래프를 표현하기 위해서는, n개의 연결리스트가 필요하고, n개의 헤드 포인터와 2e개의 노드가 필요함
  -> 따라서, 연결 리스트 표현은 간선의 개수가 적은 희소 그래프(sparse graph)에 적합

인접 리스트의 시간복잡도
1. 그래프의 간선 (i, j)의 존재 여부나 정점 i의 차수를 알기 위해서는 인접 리스트에서의 정점 i의 연결리스트를 탐색해야 하므로 연결리스트에 있는 노드의 수(정점의 차수)만큼 시간이 필요함
2. n개 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함한 모든 인접 리스트를 조사해야 하므로 $O(n+e)$의 연산이 요구됨

인접 리스트를 이용한 그래프 추상 자료형의 구현

#define MAX_VERTICES 50

typedef struct GraphNode{
	int vertex;
    struct GraphNode *link;
}GraphNode;

typedef struct GraphType{
	int n; // 정점의 개수
    GraphNode *adj_list[MAX_VERTICES]; // 정점의 개수만큼의 헤드 포인터 배열이 필요함
}GraphType;

// 그래프 초기화
void graph_init(GraphType *g){
	g->n = 0;
    for(int v=0;v<MAX_VERTICES;v++){
    	g->adj_list[v] = NULL;
    }
}

// 정점 삽입 연산
void insert_vertex(GraphType *g, int v){
	if((g->n+1) > MAX_VERTICES){
    	fprintf(stderr,"그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입 
void insert_edge(GraphType *g, int u, int v){

	GraphNode *node; // 간선을 나타내는 노드
    if(g->n <= u || g->n <= v){
    	fprintf(stderr,"그래프: 정점 번호 오류");
        return;
    }
    
    node = (GraphNode *)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

10.4 그래프의 탐색

그래프의 탐색: 그래프의 가장 기본적인 연산으로서, 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것임

10.4.1 깊이 우선 탐색

깊이 우선 탐색의 개념

깊이 우선 탐색(depth first search: DFS): 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 탐색을 진행하는 방법과 유사
1. 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하고 방문하였다고 표시함
2. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택 만약 그러한 정점이 없다면 탐색은 종료
3. 지금 방문하지 않은 u가 있으면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작함
4. 이 탐색이 끝나면 다시 v에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾고 없으면 종료, 있으면 다시 3번을 반복

<알고리즘 10.4.1.1> 깊이 우선 탐색

depth_first_search(v)

v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do
	if (u가 아직 방문되지 않았으면)
    	then depth_first_search(u)

깊이 우선 탐색의 구현

1. 순환 호출 이용하는 방법
2. 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업하는 방법

<프로그램 10.4.1.1> 인접 배열로 표현된 그래프에 대한 깊이 우선 탐색 프로그램

int visited[MAX_VERTICES]; // 방문 여부를 기록하기 위한 배열

// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType *g, int v){
	visited[v] = true; // 정점 v의 방문 표시
    printf("%d ",v); // 방문한 정점 출력
    for(int w =0;w<g->n;w++){ // 인접 정점 탐색
    	if(g->adj_mat[v][w] && !visited[w] ){ // adj_mat[v][w] == 1 : 정점 v와 정점 w가 인접한 것
        	dfs_mat(g,w); // 정점 w에서 DFS 새로 시작
        }
    }
}

<프로그램 10.4.1.2> 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 프로그램

int visited[MAX_VERTICES];

// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType *g, int v){
	visited[v] = true; // 정점 v의 방문 표시
    printf("%d ",v); // 방문한 정점 출력
    GraphNode *w;
    for(w= g->adj_list[v]; w; w=w->link){ // 인접 정점 탐색
    	if(!visited[w->vertex]){
        	dfs_list(g, w->vertex); // 정점 w->vertex에서 DFS 새로 시작
        }
    }
}

깊이 우선 탐색의 분석

• 깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점 수가 n이고, 간선의 수가 e인 경우, 인접 리스트로 표현되어 있다면 $O(n+e)$, 인접 행렬로 표현되어 있다면 $O(n^2)$
• 희소 그래프인 경우 깊이 우선 탐색은 인접 리스트의 사용이 인접 행렬의 사용보다 시간적으로 유리함

10.4.2 너비 우선 탐색

너비 우선 탐색의 개념

너비 우선 탐색(breadth first search: BFS): 시작 정점으로부터 거리가 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 (거리란 시작 정점으로부터 어떤 정점까지의 경로 중 가장 짧은 경로의 길이)

• 방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요함
• 정점이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 됨
• 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 소진될 때까지 계속함

<알고리즘 10.4.2.1> 너비 우선 탐색 알고리즘

breadth_first_search(v)

v를 방문되었다고 표시;
큐 Q에 정점 v를 삽입;
while(not is_empty(Q)) do
	큐 Q에서 정점 w를 삭제;
    for all u ∈ (w에 인접한 정점) do
    	if(u가 아직 방문되지 않았으면)
        	then u를 큐 Q에 삽입;
            	 u를 방문되었다고 표시;

너비 우선 탐색의 구현

<프로그램 10.4.2.1> 인접 행렬로 표현된 그래프에 대한 너비 우선 탐색 프로그램

void bfs_mat(GraphType *g, int v){
	QueueType q;
    init(&q); // 큐 초기화
    
    visited[v] = true; // 정점 v 방문 표시
    printf("%d ",v); // 정점 출력
    enqueue(&q, v); // 시작 정점을 큐에 저장
    
    while(!is_empty(&q)){
    	v = dequeue(&q); // 큐에서 정점 추출
        for(int w =0; w<g->n;w++){ // 인접 정점 탐색
        	if(g->adj_mat[v][w] && !visited[w]){
            	visited[w] = true; // 방문 표시
                printf("%d ", w); // 정점 출력
                enqueue(&q, w); // 방문한 정점을 큐에 저장 
            }
        }
    }
}

<프로그램 10.4.2.2> 인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 프로그램

void bfs_list(GraphType *g, int v){
	GraphNode *w;
    
    QueueType q;
    init(&q); // 큐 초기화
    
    visited[v] = true; // 정점 v 방문 표시
    printf("%d ", v); // 정점 v 출력
    enqueue(&q, v); // 시작 정점을 큐에 저장
    
    while(!is_empty(&q)){
		v = dequeue(&q); // 큐에서 정점 출력
        for(w=g->adj_list[v];w;w=w->link){ // 인접 정점 탐색
        	if(!visited[w->vertex]){ // 미방문 정점 탐색
            	visited[w->vertex] = true; // 방문 표시
                printf("%d ", w->vertex); // 정점 출력
            	enqueue(&q, w->vertex); // 방문한 정점을 큐에 삽입
            }
        }
    }
}

전체 프로그램

<프로그램 10.4.2.3> 인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 전체 프로그램

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

typedef int element;
typedef struct QueueNode{
    element item;
    struct QueueNode* link;
} QueueNode;

typedef struct{
    QueueNode *front, *rear;
} QueueType;

typedef struct GraphNode{
    int vertex;
    struct GraphNode* link;
} GraphNode;

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

// 그래프 초기화
void graph_init(GraphType *g){
    g->n = 0;
    for (int i = 0; i < MAX_VERTICES;i++){
        g->adj_list[i] = NULL;
    }
}

// 정점 삽입 연산
void insert_vertex(GraphType *g, int v){
    if(((g->n)+1) > MAX_VERTICES){
        fprintf(stderr, "graph: Exceeding the number of vertices\n");
        exit(1);
    }
    g->n++;
}

// 간선 삽입 연산
void insert_edge(GraphType *g, int u, int v){
    if( g->n <= u || g->n <= v ){
        fprintf(stderr, "graph: Number error at vertex\n");
        exit(1);
    }
    GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

void print(GraphType *g){
    for (int i = 0; i < g->n; i++) {
        printf("vertex: %d adj_vertex: ", i);
        for (GraphNode* w = g->adj_list[i]; w;w=w->link){
            printf("%d ", w->vertex);
        }
        printf("\n");
    }
}

int visited[MAX_VERTICES];

// 연결 리스트 큐 소스를 여기에
void init(QueueType *q){
    q->front = NULL;
    q->rear = NULL;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q){
    return (q->front == NULL);
}

// 삽입 함수
void enqueue(QueueType *q, element item){
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    if(node == NULL){
        fprintf(stderr, "Memory allocate error\n");
        exit(1);
    }else{
        node->item = item; // 데이터 저장
        node->link = NULL; // 링크 필드를 NULL로 설정
        if(is_empty(q)){ // 큐가 공백이면
            q->front = node;
            q->rear = node;
        }else{ // 큐가 공백이 아니면
            q->rear->link = node; // 마지막에 삽입
            q->rear = node;
        }
    }

}

element dequeue(QueueType *q){
    QueueNode* node = q->front;
    element item;
    if(is_empty(q)){ // 공백 상태
        fprintf(stderr, "Queue empty\n");
        exit(1);
    }else{
        item = node->item; // 데이터를 꺼냄
        q->front = q->front->link; // front를 다음 노드를 가리키도록 함
        if(q->front == NULL){ // 공백 상태
            q->rear = NULL;
        }
        free(node); // 노드 메모리 해제
        return item; // 데이터 반환
    }
}

element peek(QueueType* q)
{
    if (is_empty(q)) { // 공백 상태
        fprintf(stderr, "Queue empty\n");
        exit(1);
    } else {
        return q->front->item; // 데이터 반환
    }
}

void bfs_list(GraphType*g,int v){
    QueueType q;
    init(&q);

    visited[v] = TRUE;
    printf("%d ", v);
    enqueue(&q, v);

    while(!is_empty(&q)){
        v = dequeue(&q);
        for (GraphNode *w = g->adj_list[v]; w;w=w->link){
            // printf("%d ", w->vertex);

            if(!visited[w->vertex]){
                visited[w->vertex] = TRUE;
                printf("%d ", w->vertex);
                enqueue(&q, w->vertex);
            }
        }
    }
}

int main(){
    GraphType g;
    graph_init(&g);

    // 인접 리스트 생성
    for (int i = 0; i < 4;i++){
        insert_vertex(&g, i);
    }
    insert_edge(&g, 0, 1);
    insert_edge(&g, 1, 0);
    insert_edge(&g, 0, 3);
    insert_edge(&g, 3, 0);
    insert_edge(&g, 1, 2);
    insert_edge(&g, 2, 1);
    insert_edge(&g, 1, 3);
    insert_edge(&g, 3, 1);
    insert_edge(&g, 2, 3);
    insert_edge(&g, 3, 2);
    print(&g);

    bfs_list(&g, 0);
}

10.5 연결 성분

연결 성분(connected component): 최대로 연결된 부분 그래프
1. 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 됨
2. 다음에 방문 안된 정점을 선택해서 다시 탐색을 실행하면 그 정점을 포함하는 연결 성분이 구해짐
3. 그래프 상의 모든 정점이 방문될 때가지 이 과정을 되풀이하면 그래프에 존재하는 모든 연결 성분들을 찾을 수 있음

<프로그램 10.5.1> 연결 성분 프로그램

void find_connected_component(GraphType *g){
    count = 0;
    for(int i=0; i<g->n;i++){
    	if(!visited[i]){ // 방문되지 않았으면
        	count++;
            dfs_mat(g,i);
        }
    }
}

10.6 신장 트리

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

• 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고, 사이클을 포함해서는 안됨
• 따라서, 신장 트리의 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 됨
  -> 신장 트리는 그래프의 최소 연결 부분 그래프가 됨, 최소의 의미: 간선의 수가 가장 적다는 의미

깊이 우선 신장 트리: 맨 왼쪽 신장 트리, 시작 정점 0으로 깊이 우선 탐색할 때 사용된 간선으로만 만들어진 신장 트리
너비 우선 신장 트리: 중간 신장 트리, 시작 정점 0으로 너비 우선 탐색할 때 사용된 간선으로만 만들어진 신장 트리

<알고리즘 10.6.1> 신장 트리 알고리즘

depth_first_search(v)

v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do
	if (u가 아직 방문되지 않았으면)
    	then (v,u)를 신장 트리 간선이라고 표시
        	 depth_first_search(u)

10.7 최소 비용 신장 트리

최소 비용 신장 트리(MST: minimum spanning tree): 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리

• 도로 건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
• 전기 회로: 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
• 통신: 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
• 배관: 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제

최소 신장 트리 구하는 방법
-> Kruskal, Prim이 제안한 알고리즘
-> 최소 비용 신장 트리가 간선의 가중치의 합이 최소여야함
-> 반드시 (n-1)개의 간선만 사용해야 함
-> 사이클이 포함되어서는 안됨

10.7.1 Kruskal의 MST 알고리즘

Kruskal 알고리즘

• 탐욕적인 방법(greedy method)을 이용함 -> 결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달
• 그 순간의 선택은 그 당시에는 최적임, 그러나 최적이라고 생각했던 해답들을 모아서 최종적인 해답을 만들었다고 해서 그 해답이 전체적인 관점에서 최적이라는 보장은 없음
  -> 따라서 탐욕적인 방법은 항상 최적의 해답을 주는지 반드시 검증해야 함
• 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 따라 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택함, 이러한 과정을 반복함으로써 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구할 수 있음

1. 그래프의 e개의 간선들을 가중치의 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성 하지 않는 간선을 선택하여 현재의 최소 비용 신장 트리의 집합에 추가함
3. 사이클을 형성하면 그 간선은 제외됨

<알고리즘 10.7.1.1> Kruskal 최소 비용 신장 트리 알고리즘

// 최소 비용 신장 트리를 구하는 kruskal의 알고리즘
// 입력: 가중치 그래프 G = (V, E), n은 노드의 개수
// 출력: Et, 최소 비용 신장 트리를 이루는 간선들의 집합

kruskal(G)

	E를 w(e1) <= ... <= w(ee)가 되도록 정렬
    Et <- Φ; ecounter <- 0 
    k <- 0
    while ecounter < (n-1) do
    	k <- k + 1
        if Et U {ek}가 사이클을 포함하지 않으면
        	then Et <- Et U {ek}; ecounter <- ecounter + 1    
    return Et 

사이클 생성 여부 체크

• 새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결하는 경우 사이클 형성
• 간선의 양 끝 점이 같은 집합에 속한 경우 사이클 형성, 다른 집합에 속한 경우 사이클 형성 안됨
  -> 간선의 양 끝 점이 같은 집합에 속해 있는지 검사 필요 => union-find 연산

union-find 연산

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

• union 연산 시에 정점의 개수가 적은 트리의 루트가 큰 트리를 가리키도록 하면 좋음

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

• find 연산의 수행 시간을 줄이기 위해서는 특정 정점과 루트의 거리가 가까워야 함 -> 모든 정점이 루트 바로 아래 있도록 함

ex) S = {1,2,3,4,5,6}
1. 집합의 원소를 하나씩 분리하여 독자적인 집합으로 만듦
{1}, {2}, {3}, {4}, {5}, {6}
2. union(1,4), union(5,2)를 하면
{1,4}, {5,2}, {3}, {6}
3. union(4,5), union(3,6)을 하면
{1,4,5,2},{3,6}

집합을 구현하는데 여러가지 방법 존재

• 비트 벡터, 배열, 연결 리스트, 트리

<프로그램 10.7.1.1> union-find 프로그램

int parent[MAX_VERTICES]; // 부모 노드
int num[MAX_VERTICES]; // 각 집합의 크기

// 초기화
void set_init(int n){
	for(int i=0;i<n;i++){
    	parent[i] = -1; // 루트의 정점은 부모 배열에서 -1을 가짐
        num[i] = 1;
    }
}

// vertex가 속하는 집합을 반환
int set_find(int vertex){
	int p,s,i=-1;
	for(i=vertex; (p = parent[i]) >=0;i=p){ // 루트 노드까지 반복
    }
    s = i; // 집합의 대표 원소
    for(i=vertex;(p = parent[i]) >=0;i=p){
    	parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정
    }
    return s;
}

// 두 개의 원소가 속한 집합을 합침
void set_union(int s1, int s2){
	if(num[s1] < num[s2] ){
    	parent[s1] = s2;
        num[s2] += num[s1];
    }else{
    	parent[s2] = s1;
        num[s1] += num[s2];
    }
}

<프로그램 10.7.1.2> Kruskal의 최소 비용 신장 트리 프로그램

#include <stdio.h>

#define MAX_VERTICES 100
#define INF 1000

int parent[MAX_VERTICES]; // 부모 노드
int num[MAX_VERTICES]; // 각 집합의 크기

// 집합 초기화
void set_init(int n)
{
    for (int i = 0; i < n; i++) {
        parent[i] = -1; // 루트의 정점은 부모 배열에서 -1을 가짐
        num[i] = 1;
    }
}

// vertex가 속하는 집합을 반환
int set_find(int vertex)
{
    int p, s, i = -1;
    for (i = vertex; (p = parent[i]) >= 0; i = p) { // 루트노드까지 반복
    }
    s = i; // 집합의 대표 원소
    for (i = vertex; (p = parent[i]) >= 0; i = p) {
        parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정
    }
    return s;
}

// 두 개의 원소가 속한 집합을 합침
void set_union(int s1, int s2)
{
    if (num[s1] < num[s2]) {
        parent[s1] = s2;
        num[s2] += num[s1];
    } else {
        parent[s2] = s1;
        num[s1] += num[s2];
    }
}

// 힙의 요소 타입 정의
typedef struct {
    int key; // 간선의 가중치
    int u; // 정점1
    int v; // 정점2
} element;

#define MAX_ELEMENT 100

// 최소 힙 프로그램 - krusal에서 간선들의 가중치의 오름차순으로 정렬하기 때문
typedef struct{
    element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;

// 힙 초기화 함수
void init(HeapType *h){
    h->heap_size = 0;
}

int is_empty(HeapType*h){
    if(h->heap_size == 0){
        return true;
    }else{
        return false;
    }
}

// 삽입함수
void insert_min_heap(HeapType*h, element item){
    int i = ++h->heap_size;


    // 트리를 거슬러 올라가면서 부모 노드와 비교
    while((i != 1) && (item.key < h->heap[i/2].key)){
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = item; // 새로운 노드 삽입
}

// 삭제 함수
element delete_min_heap(HeapType*h){
    element item = h->heap[1];
    element tmp = h->heap[(h->heap_size)--];
    int parent = 1;
    int child = 2;

    while(child <=h->heap_size){
        // 현재 노드의 자식 노드 중 더 작은 자식 노드를 찾음
        if((child < h->heap_size) && (h->heap[child].key > h->heap[child+1].key) ){
            child++;
        }

        if(tmp.key <= h->heap[child].key)
            break;
        // 한단계 아래로 이동
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    h->heap[parent] = tmp;
    return item;
}

// 정점u와 정점 v를 연결하는 가중치가 weight인 간선을 힙에 삽입
void insert_heap_edge(HeapType *h, int u, int v, int weight){
    element e;
    e.u = u;
    e.v = v;
    e.key = weight;
    insert_min_heap(h, e);
}

// 인접행렬이나 인접리스트에서 간선들을 읽어서 최소 힙에 삽입
// 현재는 예제 그래프의 간선들을 삽입함
void insert_all_edges(HeapType *h){
    insert_heap_edge(h, 0, 1, 29);
    insert_heap_edge(h, 1, 2, 16);
    insert_heap_edge(h, 2, 3, 12);
    insert_heap_edge(h, 3, 4, 22);
    insert_heap_edge(h, 4, 5, 27);
    insert_heap_edge(h, 5, 0, 10);
    insert_heap_edge(h, 6, 1, 15);
    insert_heap_edge(h, 6, 3, 18);
    insert_heap_edge(h, 6, 2, 25);
}

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

    init(&h); // 힙 초기화
    insert_all_edges(&h); // 힙에 간선들을 삽입
    set_init(n); // 집합 초기화

    while(edge_accepted < (n-1)){
        e = delete_min_heap(&h); // 최소 힙에서 삭제
        uset = set_find(e.u); // 정점 u의 집합 번호
        vset = set_find(e.v); // 정점 v의 집합 번호
        if(uset != vset){ // 서로 속한 집합이 다르면
            printf("(%d %d) %d\n", e.u, e.v, e.key);
            edge_accepted++;
            set_union(uset, vset); // 두개의 집합을 합침
        }
    }
}

int main(){
    kruskal(7);
}

시간복잡도

• 간선들을 정렬하는 시간에 좌우됨
• 따라서 퀵 정렬를 이용하여 간선 e를 정렬할 경우, $O(eloge)$가 됨

10.7.2 Prim의 MST 알고리즘

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

• 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함됨
• 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장함
• 트리가 n-1개의 간선을 가질 때까지 계속됨

Kruskal 알고리즘 = 간선 선택을 기반으로 하는 알고리즘, 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법
Prim 알고리즘 = 정점 선택을 기반으로 하는 알고리즘, 이전 단계에서 만들어진 신장 트리를 확장하는 방법

<알고리즘 10.7.2.1> Prim의 최소 비용 신장 트리 알고리즘 #1

// 최소 비용 신장 트리를 구하는 Prim의 알고리즘
// 입력: 네트워크 G=(V,E), S는 시작 정점
// 출력: Vt, 최소 비용 신장 트리를 이루는 정점들의 집합

Prim(G,s)

	Vt <- {s}: vcounter <- 1
    while vcounter < n do
    	(u,v)는 u∈Vt and v∉Vt인 최저 비용 간선;
        if (그러한 (u,v)가 존재하면)
        	then Vt <- Vt U v; vcounter <- vcounter +1
        else 실패
   return Vt

prim 알고리즘의 구현

1. dist라는 정점의 개수 크기의 배열이 필요함, 현재까지 알려진 신장 트리 정점 집합에서 각 정점까지의 거리를 가지고 있음.
2. 처음에는 시작 노드만 값이 0이고 다른 노드는 전부 무한대 값을 가짐
3. 정점들이 트리 집합에 추가되면서 dis 값은 변경됨
4. 우선순위 큐 Q가 하나 필요함, 우선순위 큐 Q에 모든 정점을 삽입, 이때 우선순위는 dist 배열 값이 됨
5. while 루프로 Q에서 가장 작은 dist 값을 가지는 정점을 추출
6. 추출된 정점이 트리 집합에 추가됨
7. 트리 집합에 새로운 정점 u가 추가되었으므로 u에 인접한 정점 v들의 dist 값들을 변경시켜줌 -> 기존의 dist[v]값 보다 간선 (u,v)의 가중치가 적으면 간선 (u,v)의 가중치로 dist[v]를 변경시킴
8. Q에 있는 모든 정점들이 소진될 때까지 이러한 과정을 되풀이하면 됨

<알고리즘 10.7.2.2> Prim의 최소 비용 신장 트리 알고리즘 #2

// 최소 신장 트리를 구하는 Prim의 알고리즘
// 입력: 네트워크 G=(V,E), s는 시작 정점
// 출력: 최소 비용 신장 트리를 이루는 정점들의 집합
Prim(G, s)

	for each u ∈ V do
    	dist[u] <- ∞
    dist[s] <- 0 
    우선순위 큐Q에 모든 정점을 삽입(우선순위는 dist[])
    for i <- 0 to n-1 do
    	u <- delete_min(Q)
        화면에 u 출력
        for each v ∈ (u의 인접 정점)
        	if(v ∈ Q and weight[u][v] < dist[v])
            	then dist[v] <- weight[u][v]

<프로그램 10.7.2.1> Prim의 최소 비용 신장 트리 프로그램

#include <stdio.h>
#define TRUE 1
#define FALSE 0

#define MAX_VERTICES 7
#define INF 1000L

int weight[MAX_VERTICES][MAX_VERTICES] = {
    { 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 }
};

int selected[MAX_VERTICES];
int dist[MAX_VERTICES];

// 최소 dist[v]값을 갖는 정점을 반환
int get_min_vertex(int n){
    int v;
    for (int i = 0; i < n;i++){
        if(!selected[i]){
            v = i;
            break;
        }
    }

    for (int i = 0; i < n;i++){
        if(!selected[i] &&(dist[i] < dist[v]))
            v = i;
    }
    return v;
}

void prim(int s, int n){
    int i, u, v;

    // 초기화
    for (u = 0; u < n;u++){
        dist[u] = INF;
        selected[u] = FALSE;
    }
    dist[s] = 0;

    for (i = 0; i < n;i++){
        u = get_min_vertex(n);
        selected[u] = TRUE;
        if(dist[u] == INF)
            return;
        printf("%d ", u);
        for (v = 0; v < n;v++){
            if(weight[u][v] != INF){
                if(!selected[v] && weight[u][v] < dist[v]){
                    dist[v] = weight[u][v];
                }
            }
        }
    }
}

int main(){
    prim(0, MAX_VERTICES);
}

Prim 알고리즘의 분석

• 주 반복문이 정점의 수 n만큼 반복, 내부 반복문이 n번 반복하므로 시간복잡도는 $O(n^2)$
• 희박한 그래프를 대상으로할 경우 Kurskal의 알고리즘이 적합, 밀집한 그래프의 경우 Prim의 알고리즘이 적합

10.8 최단 경로

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

1. Dijkstra 알고리즘: 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로를 구함
2. Floyd 알고리즘: 모든 정점에서 다른 모든 정점까지의 최단 경로를 구함

인접 행렬: 간선이 없으면 인접 행렬의 값은 0
가중치 인접 행렬: 간선의 가중치가 0일 수도 있기 때문에 간선이 없는 경우 값은 무한대(정수 중에서 상당히 큰 값)

10.8.1 Dijkstra의 최단 경로 알고리즘

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

• 최단 경로: 경로의 길이순으로 구해짐

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

• Dijkstra에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열이 필요 -> 1차원 배열: distance
  - distance의 초기값

  • 시작 정점 distance[v] = 0
  • 다른 정점 distance[w] = weight[v][w] (시작 정점과 해당 정점 간의 가중치)

• 알고리즘은 매 단계에서 집합 S 안에 있지 않은 정점 중에서 가장 distance 값이 작은 정점을 집합 S에 추가
  

  1. 현재 집합 S에 들어 있지 않은 정점 중 distance 값이 가장 작은 정점이 u일 때, 시작 정점 v에서 정점 u까지의 최단 거리는 경로 (1)이 됨
  2. 정점 w를 거쳐서 정점 u로 가는 가상적은 더 짧은 경로가 있을 경우, 정점 v에서 정점 u까지의 최단 거리는 정점 v에서 정점 w까지의 거리 (2)와 정점 w에서 정점 u로 가는 거리 (3)을 합한 값이 됨
     -> 하지만, 현재 distance 값이 가장 작은 정점은 u이기 때문에 경로 (2)는 경로 (1)보다 항상 길 수밖에 없음
  3. 새로운 정점 u가 집합 S에 추가되면, S에 있지 않은 다른 정점들의 distance 값을 수정

     distance[w] = min(distance[w], distance[u] + weight[u][w]) // 새로 추가된 정점 u를 거쳐서 정점까지 가는 거리와 기존 거리를 비교해서 더 작은 거리로  distance 값을 수정

<알고리즘 10.8.1.1> 최단 경로 알고리즘

// 입력: 가중치 그래프 G, 가중치는 음수가 아님
// 출력: distance 배열, distance[u]는 v에서 u까지의 최단 거리
shortest_path(G, v)

	S <- {v}
    for 각 정점 w ∈ G do
    	distance[w] <- weight[u][w];
    while 모든 정점이 S에 포함되지 않으면 do
    	u <- 집합 S에 속하지 않는 정점 중에서 최소 distance 정점;
        S <- S U {u}
        for u에 인접하고 S에 있지 않은 각 정점 w do
        	if distanace[u] + weight[u][w] < distance[w]
            	then distance[w] <- distance[u] + weight[u][w];

<프로그램 10.8.1.1> 최단 경로 Dijkstra 프로그램

#include <stdio.h>

#define INT_MAX 2147483647 // 최대 정수
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 7 // 정점의 수
#define INF 1000 // 무한대(연결이 없는 경우)

int weight[MAX_VERTICES][MAX_VERTICES] = { // 네트워크 인접 행렬
    { 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 }
};

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

void print(int n)
{

    printf("S = ");
    for (int i = 0; i < n; i++) {
        printf("%d ", found[i]);
    }
    printf("\n");

    printf("distance[] = ");
    for (int i = 0; i < n; i++) {
        printf("%d ", distance[i]);
    }
    printf("\n");
}

int choose(int distance[], int n, int found[]){ // 최소값을 선택
    int min = INT_MAX;
    int minpos = -1;
    for (int i = 0; i < n;i++){
        if(distance[i] < min && !found[i]){
            min = distance[i];
            minpos = i;
        }
    }
    return minpos;
}

void shortest_path(int start, int n){
    
    // 초기화
    for (int i = 0; i < n;i++){
        distance[i] = weight[start][i];
        found[i] = FALSE;
    }

    found[start] = TRUE; // 시작 정점 방문 표시
    distance[start] = 0;
    print(n);

    for (int i = 0; i < n - 1;i++){
        int u = choose(distance, n, found);
        found[u] = TRUE;
        for (int w = 0; w < n;w++){
            if(!found[w]){
                if(distance[u] + weight[u][w] < distance[w]){
                    distance[w] = distance[u] + weight[u][w];
                }
            }
        }
        print(n);
    }
}

int main(){
    shortest_path(0, MAX_VERTICES);
}

시간복잡도

• 주 반복문 n번 반복, 내부 반복문을 2n번 반복하므로 $O(n^2)$의 복잡도를 가짐

10.8.2 Floyd의 최단 경로 알고리즘

인접행렬 weight
1. i == j, weight[i][j] =0
2. 정점 i, j 사이 간선이 존재하지 않으면, weight[i][j] = 무한대
3. 정점 i, j 사이 간선이 존재하면, weight[i][j] = 간선(i, j)의 가중치

<알고리즘 10.8.2.1> Floyd의 최단 경로 알고리즘

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])

<프로그램 10.8.2.1> Floyd의 최단 경로 알고리즘

#include <stdio.h>
#define min(x,y) (((x) < (y)) ? (x):(y))
#define MAX_VERTICES 7 // 정점의 수
#define INF 1000 // 무한대(연결이 없는 경우)

int weight[MAX_VERTICES][MAX_VERTICES] = { // 네트워크 인접 행렬
    { 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 }
};

int A[MAX_VERTICES][MAX_VERTICES];

void print(int n){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%4d ", A[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void floyd(int n){
    for (int i = 0; i < n;i++){
        for (int j = 0; j < n;j++){
            A[i][j] = weight[i][j];
        }
    }

    for (int k = 0; k < n;k++){
        for (int i = 0; i < n;i++){
            for (int j = 0; j < n;j++){
                A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
            }
        }
        print(n);
    }
}

int main(){
    floyd(MAX_VERTICES);
}

시간복잡도

• 두 개의 정점 사이의 최단 경로를 찾는 Dijkstra의 알고리즘은 시간복잡도가 $O(n^2)$이므로, 모든 정점 쌍의 최단 경로를 구하려면 n번 반복해야하기 때문에 시간복잡도가 $O(n^3)$이됨
• 한 번에 모든 정점 간의 최단 경로를 구하는 Floyd의 알고리즘은 3중 반복문 실행으로 시간복잡도 $O(n^3)$이 됨
  -> Dijkstra의 알고리즘과 비교해도 차이가 없다고 할 수 있지만, Floyd 알고리즘은 매우 간결한 반복 구문을 사용하므로 Dijkstra의 알고리즘보다 상당히 빨리 모든 정점 간의 최단 경로를 찾을 수 있음

	크루스칼(Kruskal)	다익스트라(Dijkstra)
구현 방법	우선순위 큐 + union-find(서로소집합)	우선순위 큐+ dp(점화식)
중심	간선	정점
시작점	간선의 가중치가 작은 것부터 시작(오름차순 정렬)	출발점이 정해져 있는 경우
Queue 진입 시점	모든 정점을 유선순위 큐에 넣고 시작	dp 갱신될 때만(최단 경로 갱신) 그 정점에서 출발하는 간선을 우선순위 큐에 추가
용도	최소 신장 트리를 그릴 때	한 정점에서 다른 정점의 최단 거리를 구하는 경우
최단 거리	최소의 비용(최단 거리) 모든 점을 다 연결할 때 사용 모든 점을 다 이은 경로가 최단 거리라고 말할 수 있지만 임의의 두 점 간의 거리가 최단 거리라는 보장은 없음	임의의 두 점 간의 최단 거리 구할 때 사용

10.9 위상 정렬

위상 정렬(topological sort): 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
1. 진입 차수가 0인 정점을 선택
-> 진입 차수 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방함(하나의 그래프에는 복수의 위산 순서가 있을 수 있음)
2. 선택된 정점과 여기에 부속된 모든 간선 삭제
3. 1,2을 반복하다가 모든 정점이 선택 및 삭제되면 종료
-> 이 과정에서 선택되는 정점의 순서를 위상 순서(topological order)라고 함

<알고리즘 10.9.1> 그래프 위상 정렬 알고리즘

// input: 그래프 G=(V,E)
// output: 위상 정렬 순서

topo_sort(G)

	for i <- 0 to n-1 do
    	if( 모든 정점이 선행 정점을 가지면 )
        	then 사이클이 존재하고 위상 정렬 불가;
        선행 정점을 가지지 않는 정점 v를 선택;
        v를 출력;
        v와 v에 부속한 모든 간선들을 그래프에서 삭제;

1. in_degree라는 1차원 배열을 만들어 각 정점의 진입 차수를 기록
   -> in_degree[i]: 정점 i로 들어오는 간선들의 개수
   -> in_degree[i] == 0일 경우 i는 후보 정점
2. 알고리즘이 진행되면서, 진입 차수가 0인 정점이 그래프에서 제거되면 그 정점에 인접한 정점의 in_degree는 1만큼 감소
3. 후보 정점들은 스택에 저장

<프로그램 10.9.1> 그래프 위상 정렬 프로그램

// 위상 정렬을 수행함
void topo_sort(GraphType *g){
	StackType s;
    GraphNode *node;
    // 모든 정점의 진입 차수를 계산
    int *in_degree = (int *)malloc(g->n* sizeof(int));
    for(int i=0;i<g->n;i++){ // 초기화
    	in_degree[i] = 0;
    }
    for(int i=0;i<g->n;i++){
    	node = g->adj_list[[i]; // 정점 i에서 나오는 간선들
        while(node != NULL){
        	in_degree[node->vertex]++;
            node = node->link;
        }
    }
    
    // 진입 차수가 0인 정점(후보 정점)을 스택에 삽입
    init(&s)
    for(int 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);
    return; // 반환 값이 1이면 성공, 0이면 실패
}

<프로그램 10.9.2> 그래프 위상 정렬 전체 프로그램

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

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

typedef struct GraphNode{
    int vertex;
    struct GraphNode* link;
} GraphNode;

typedef struct{
    int n; // wjdwjadml rotn
    GraphNode* adj_list[MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g){
    g->n = 0;
    for (int i = 0; i < MAX_VERTICES;i++){
        g->adj_list[i] = NULL;
    }
}

// 정점 삽입 연산
void insert_vertex(GraphType *g, int v){
    if((g->n+1) >MAX_VERTICES){
        fprintf(stderr, "graph: Exceeding the number of vertices\n");
        return;
    }
    g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입
void insert_edge(GraphType*g, int u, int v){
    GraphNode* node;
    if(u >=g->n || v>=g->n){
        fprintf(stderr, "graph: Number error at vertex\n");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

// 스택 소스 추가
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
    element stack[MAX_STACK_SIZE];
    int top;
} StackType;

// 스택 초기화 함수
void init(StackType *s){
    s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s){
    return (s->top == -1);
}

// 포화 상태 검출 함수
int is_full(StackType *s){
    return (s->top == (MAX_STACK_SIZE-1));
}

// 삽입 함수
void push(StackType *s, element data){
    if(is_full(s)){
        fprintf(stderr, "overflow\n");
        exit(1);
    }else{
        s->stack[++(s->top)] = data;
    }
}

// 삭제 함수
element pop(StackType *s){
    if(is_empty(s)){
        fprintf(stderr, "underflow\n");
        exit(1);
    }else{
        return s->stack[(s->top)--];
    }
}

// 피크 함수
element peek(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "underflow\n");
        exit(1);
    } else {
        return s->stack[s->top];
    }
}

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

    // 진입 차수가 0인 정점을 스택에 삽입
    init(&s);
    for (int 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);
    return; // 반환 값이 1이면 성공, 0이면 실패
}

int main(){
    GraphType g;

    graph_init(&g);
    insert_vertex(&g, 0);
    insert_vertex(&g, 1);
    insert_vertex(&g, 2);
    insert_vertex(&g, 3);
    insert_vertex(&g, 4);
    insert_vertex(&g, 5);

    // 정점 0의 인접 리스트 생성
    insert_edge(&g, 0, 2);
    insert_edge(&g, 0, 3);
    // 정점 1의 인접 리스트 생성
    insert_edge(&g, 1, 3);
    insert_edge(&g, 1, 4);
    // 정점 21의 인접 리스트 생성
    insert_edge(&g, 2, 3);
    insert_edge(&g, 2, 5);
    // 정점 3의 인접 리스트 생성
    insert_edge(&g, 3, 5);
    // 정점 4의 인접 리스트 생성
    insert_edge(&g, 4, 5);

    // 위상 정렬
    topo_sort(&g);
    // 간선을 삭제하는 함수 추가
}

<참고자료>
천인국 · 공용해 · 하상호 지음,『C언어로 쉽게 풀어쓴 자료구조』, 생능출판(2016)