[C언어로 쉽게 풀어쓴 자료구조] 11장 그래프 Ⅱ

11.1 최소 비용 신장 트리

신장 트리(Spanning tree)

• 그래프내의 모든 정점을 포함하는 트리
• 모든 정점들이 연결되어 하고 사이클을 포함하면 안된다.
• 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결해야 한다.

신장 트리 예

 

최소 비용 신장 트리(MST, Minimum Spanning Tree)

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

---

11.2 크루스칼의 MST 알고리즘

• 그리디 알고리즘 사용: 선택할 대마다 그 순간 가장 좋다고 생각되는 것을 선택하는 방법
  • 그리디 알고리즘에서 순간의 선택은 그 당시에는 최적이다.
  • 하지만 최적의 지역적인 해답을 모은것이 반드시 전역적으로 최적이라는 보장은 없다.
• 가중치를 기준으로 간선을 정렬 후 MST가 될 때까지 간선을 하나씩 선택 or 삭제하는 알고리즘

오름차순

• 낮은 가중치 간선부터 시작해서 하나씩 그래프에 추가
• 사이클을 형성하는 간선은 추가하지 않는다.
• 간선 + 1 = 정점

크루스칼 오른차순

 

내림차순

• 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 삭제
• 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선을 제거하지 않는다.
• 간선 + 1 = 정점

크루스칼 내림차순

 

#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;	// 간선의 개수
	struct Edge edges[2 * MAX_VERTICES];
} GraphType;

// 그래프 초기화 
void graph_init(GraphType* g)
{
	g->n = 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->n);				// 집합 초기화
	qsort(g->edges, g->n, sizeof(struct Edge), compare);

	printf("크루스칼 최소 신장 트리 알고리즘 \n");
	int i = 0;
	while (edge_accepted < (g->n - 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);

	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;
}

---

11.3 프림의 MST 알고리즘

• 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법
• 트리가 n- 1개의 간선을 가질 때까지 계속된다.

프림의 MST 알고리즘

#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;
	for (i = 0; i <n; i++)
		if (!selected[i]) {
			v = i;
			break;
		}
	for (i = 0; i < n; i++)
		if (!selected[i] && (distance[i] < distance[v])) v = i;
	return (v);
}
//
void prim(GraphType* g, int s)
{
	int i, u, v;

	for (u = 0; u<g->n; u++)
		distance[u] = INF;
	distance[s] = 0;
	for (i = 0; i<g->n; i++) {
		u = get_min_vertex(g->n);
		selected[u] = TRUE;
		if (distance[u] == INF) return;
		printf("정점 %d 추가\n", u);
		for (v = 0; v<g->n; v++)
			if (g->weight[u][v] != INF)
				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;
}

---

11.5 다익스트라의 최단 경로 알고리즘

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

 

1. S 정점에서 시작

 

2. A정점을 거쳐가는 최단 경로 탐색

 

 

3. C정점을 거쳐가는 최단 경로 탐색

 

4. D 정점을 거쳐가는 최단 경로 탐색

 

5. B, E  정점을 거쳐가는 최단 경로 탐색

 

 

#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 found[])
{
	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;
}

 

---

11.6 플로이드 최단 경로 알고리즘

• 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 찾아주는 알고리즘
• 2차원 인접 행렬 구성
• 정점의 개수만큼 라운드를 진행
• 각 라운드마다 새로운 경로로 사용 가능한 더 짧은 길이를 선택하는 과정을 반복한다.

 

초기상태

 

1,2 라운드

 

3,4 라운드

 

5라운드

 

총 5개의 정점이 존재함으로 5번의 라운드를 진행하고 알고리즘을 종료

#include <stdio.h>
#include <stdlib.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 A[MAX_VERTICES][MAX_VERTICES]; // 최단 거리 행렬

// 최단 거리 행렬 출력 함수
void printA(GraphType *g) {
    int i, j;
    printf("===============================\n");
    for (i = 0; i < g->n; i++) {
        for (j = 0; j < g->n; j++) {
            if (A[i][j] == INF)
                printf("  * "); // 무한대는 '*'로 표시
            else
                printf("%3d ", A[i][j]);
        }
        printf("\n");
    }
    printf("===============================\n");
}

// 플로이드-워셜 알고리즘을 이용한 최단 거리 계산 함수
void floyd(GraphType* g) {
    int i, j, k;
    
    // 초기 거리 행렬 설정 (입력된 그래프의 가중치 행렬을 복사)
    for (i = 0; i < g->n; i++)
        for (j = 0; j < g->n; j++)
            A[i][j] = g->weight[i][j];
    
    printA(g); // 초기 거리 행렬 출력

    // 모든 정점 쌍에 대해 최단 거리 계산 수행
    for (k = 0; k < g->n; k++) { // k는 경유지 정점
        for (i = 0; i < g->n; i++) { // i는 출발 정점
            for (j = 0; j < g->n; j++) { // j는 도착 정점
                // 현재 i에서 j까지의 최단 거리보다, i -> k -> j 경로를 거치는 것이 더 짧다면 갱신
                if (A[i][k] + A[k][j] < A[i][j])
                    A[i][j] = A[i][k] + A[k][j]; // 최단 거리 갱신
            }
        }
        printA(g); // 갱신된 거리 행렬 출력
    }
}

int main(void) {
    // 예제 그래프 초기화 (7개의 정점, 가중치 행렬 정의)
    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 } }
    };
    
    floyd(&g); // 플로이드-워셜 알고리즘 실행
    return 0;
}

 

---

11.7 위상 정렬

• 사이클이 없는 방향 그래프에서 정점을 선형으로 정렬
• 순서가 정해진 작업을 수행해야 할 때 그 순서를 결정
• 여러 경우의 수가 있을 수 있다.
• 입학 → 1 → 2 → 3 → 4 → 졸업
    ↓→→→→→→→→→→→→↑ 
                      시험 (예를 들어 시험을 통해 한번에 졸업하는 경우)

 

위상 정렬 진행 순서

1. 진입 차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
3. 큐가 빌때까지 반복

※ 모든 원소가 방문 전 큐가 비어있으면 사이클이 존재

※ 진입차수: 들어오는 간선의 수

※ 진출차수: 나가는 간선의 수

위는 진입차수, 아래는 진출차수

 

 

 

#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 GraphType {
	int n;	// 정점의 개수
	GraphNode *adj_list[MAX_VERTICES];
} GraphType;

// 그래프 초기화 
void graph_init(GraphType *g)
{
	int v;
	g->n = 0;
	for (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 (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		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 item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->stack[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->stack[(s->top)--];
}

// 위상정렬을 수행한다.
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이면 실패
}
//	
int main(void)
{
	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);
	//정점 2의 인접 리스트 생성
	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);
	// 동적 메모리 반환 코드 생략
	return 0;
}