1월 3일(화) - 그래프 정리(2)

 

1. MST(최소 비용 신장트리) 알고리즘

1-1) Kruskal의 MST 알고리즘

1-2) Prim의 MST 알고리즘

//Kruskal의 MST(최소비용신장트리) 알고리즘

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

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 root_1 = set_find(a);
	int root_2 = set_find(b);
	if (root_1 != root_2)
	{
		parent[root_1] = root_2;
	}
}

struct Edge {
	int start, end, weight;
};

typedef struct GraphType {
	int n;
	int n_vertex;
	struct Edge edges[2 * MAX_VERTICES];
}GraphType;

void graph_init(GraphType* g)
{
	g->n = g->n_vertex = 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++;
}

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

void kruskal(GraphType* g)
{
	int edge_accepted = 0;
	int u_set, v_set;
	struct Edge e;

	set_init(g->n_vertex);
	qsort(g->edges, g->n, sizeof(struct Edge), compare);

	printf("크루스칼 최소 신장 트리 알고리즘 \n");
	int i = 0;
	while (edge_accepted < (g->n_vertex - 1))
	{
		e = g->edges[i];
		u_set = set_find(e.start);
		v_set = set_find(e.end);
		if (u_set != v_set)
		{
			printf("간선 (%d, %d) %d 선택\n", e.start, e.end, e.weight);
			edge_accepted++;
			set_union(u_set, v_set);
		}
		i++;
	}
}

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

	g->n_vertex = 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;
}

//Prim의 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];

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

2. 최단 경로 알고리즘

2-1) Dijkstra의 최단 경로 알고리즘

2-2) Floyd의 최단 경로 알고리즘

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

출처: c언어로 쉽게 풀어쓴 자료구조