アルゴリズム導論コード第23章最小生成ツリー

36260 ワード

第23章最小生成木
22.2 KruskalアルゴリズムとPrimアルゴリズム
22.2.1 Kruskalアルゴリズム

#include 
#include 
#include 
#include 
typedef struct graph_type *graph;
struct edge {
	int u;
	int v;
	int w;
};
struct graph_node {
	int key;
	int w;
	struct graph_node *next;
};
void graph_node_ini(struct graph_node *x, int key, int w)
{
	x->key = key;
	x->w = w;
	x->next = NULL;
}

struct vertex {
	char str_vertex[256];	//        ，   
};
void vertex_ini(struct vertex *v)
{
	strcpy(v->str_vertex, "");
}

struct graph_type {
	struct graph_node **adj;
	struct vertex *vertex_array;
	int v_num;
	int e_num;
};
//      0~v_num-1  ,str_vertex         ，   
graph graph_create(int v_num, char *str_vertex[])
{
	graph g = malloc(sizeof(struct graph_type));
	g->v_num = v_num;
	g->e_num = 0;
	g->adj = malloc(sizeof(struct graph_node *) * v_num);
	g->vertex_array = malloc(sizeof(struct vertex) * v_num);
	for (int i = 0; i < v_num; i++) {
		g->adj[i] = NULL;
		strcpy(g->vertex_array[i].str_vertex, str_vertex[i]);
	}
	return g;
}

void graph_destroy(graph g)
{
	for (int i = 0; i < g->v_num; i++) {
		for (struct graph_node * x = g->adj[i]; x != NULL;) {
			struct graph_node *del=x;
			x=x->next;
			free(del);
		}
	}
	free(g->adj);
	free(g->vertex_array);
	free(g);
}

void graph_insert_edge(graph g, struct edge e)
{
	struct graph_node *u = malloc(sizeof(struct graph_node));
	graph_node_ini(u, e.u, e.w);
	struct graph_node *v = malloc(sizeof(struct graph_node));
	graph_node_ini(v, e.v, e.w);
	//     , v     u
	v->next = g->adj[e.u];
	g->adj[e.u] = v;
	//     , u     v
	u->next = g->adj[e.v];
	g->adj[e.v] = u;
	++g->e_num;
}

void graph_display(graph g)
{
	printf("%d vertices,%d edges
", g->v_num, g->e_num);
	for (int i = 0; i < g->v_num; i++) {
		printf("%s: ", g->vertex_array[i].str_vertex);
		for (struct graph_node * x = g->adj[i]; x != NULL; x = x->next) {
			printf("%s,%d ", g->vertex_array[x->key].str_vertex,x->w);
		}
		printf("
");
	}
}

void swap(void *a, void *b, size_t elem_size)
{
	if (a == NULL || b == NULL || a == b)
		return;
	char temp[elem_size];	/*     */
	memcpy(temp, a, elem_size);
	memcpy(a, b, elem_size);
	memcpy(b, temp, elem_size);
}

int partition(void *base, size_t elem_size, int p, int r,
	      int (*comp) (const void *, const void *))
{
	char *cbase = base;
	void *key = &cbase[r * elem_size];
	int i = p - 1;
	for (int j = p; j < r; j++) {
		if (comp(&cbase[j * elem_size], key) <= 0) {
			++i;
			swap(&cbase[i * elem_size], &cbase[j * elem_size],
			     elem_size);
		}
	}
	swap(&cbase[(i + 1) * elem_size], key, elem_size);
	return i + 1;
}

void quick_sort(void *base, size_t elem_size, int p, int r,
		int (*comp) (const void *, const void *))
{
	if (p < r) {
		int q = partition(base, elem_size, p, r, comp);
		quick_sort(base, elem_size, p, q - 1, comp);
		quick_sort(base, elem_size, q + 1, r, comp);
	}
}

typedef struct set_type *set;
struct set_node {
	void *key;
	int rank;
	struct set_node *parent;
};

void set_node_ini(struct set_node *x, void *key)
{
	x->key = key;
	x->rank = 0;
	x->parent = NULL;
}

struct set_type {
	struct set_node *root;
};

set set_create(void *key)
{
	set s = malloc(sizeof(struct set_type));
	s->root = malloc(sizeof(struct set_node));
	set_node_ini(s->root, key);
	s->root->parent = s->root;
	s->root->rank = 0;
	return s;
}

void link(struct set_node *x, struct set_node *y)
{
	if (x->rank > y->rank) {
		y->parent = x;
	} else {
		x->parent = y;
		if (x->rank == y->rank) {
			++y->rank;
		}
	}
}

struct set_node *find_set_path_compression(struct set_node *x)
{
	if (x != x->parent) {
		x->parent = find_set_path_compression(x->parent);
	}
	return x->parent;
}

struct set_node *find_set(set s)
{
	return find_set_path_compression(s->root);
}

void set_destroy(set s, void (*free_key) (void *))
{
	free_key(s->root->key);
	free(s->root);
	free(s);
}

void set_union(set sa, set sb)
{
	link(find_set(sa), find_set(sb));
}

void graph_get_edges(graph g, struct edge edges[], int *edge_num)
{
	*edge_num = 0;
	for (int i = 0; i < g->v_num; i++) {
		int u = i;
		for (struct graph_node * x = g->adj[i]; x != NULL; x = x->next) {
			int v = x->key;
			if (u <= v) {
				struct edge edge = { u, v, x->w };
				edges[(*edge_num)++] = edge;
			}
		}
	}
}

int cmp_edge(const void *p1, const void *p2)
{
	const struct edge *pa = p1;
	const struct edge *pb = p2;
	if (pa->w < pb->w)
		return -1;
	if (pa->w == pb->w)
		return 0;
	return 1;
}

void graph_mst_kruskal(graph g, struct edge tree_edges[], int *tree_edge_num)
{
	set set_array[g->v_num];
	for (int i = 0; i < g->v_num; i++) {
		int *p = malloc(sizeof(int));
		*p = i;
		set_array[i] = set_create(p);
	}
	struct edge edges[g->e_num];
	int edge_num = 0;
	graph_get_edges(g,edges, &edge_num);
	quick_sort(edges, sizeof(struct edge), 0, edge_num - 1, cmp_edge);
	*tree_edge_num = 0;
	for (int i = 0; i < edge_num; i++) {
		struct edge edge = edges[i];
		if (find_set(set_array[edge.u]) !=
		    find_set(set_array[edge.v])) {
			tree_edges[(*tree_edge_num)++] = edge;
			set_union(set_array[edge.u], set_array[edge.v]);
		}
	}
	for(int i=0;iv_num;i++)
	{
		set_destroy(set_array[i],free);
	}
}

int main()
{
	//        23-1
	char *str_vertex[9] = { "a", "b", "c", "d", "e", "f", "g", "h", "i" };
	graph g = graph_create(9, str_vertex);
	struct edge edges[] = {
		{0, 1, 4}, {0, 7, 8}, {1, 7, 11},
		{1, 2, 8}, {2, 8, 2}, {2, 5, 4}, {2, 3, 7},
		{3, 4, 9}, {3, 5, 14}, {4, 5, 10}, {5, 6, 2},
		{6, 7, 1}, {6, 8, 6}, {7, 8, 7}
	};
	for (unsigned i = 0; i < sizeof(edges) / sizeof(edges[0]); i++) {
		graph_insert_edge(g,edges[i]);
	}
	printf("   :
");
	graph_display(g);
	struct edge tree_edges[sizeof(edges) / sizeof(edges[0])];
	int edge_tree_num;
	printf("         :
");
	graph_mst_kruskal(g,tree_edges, &edge_tree_num);
	int weight_sum = 0;
	for (int i = 0; i < edge_tree_num; i++) {
		struct edge e = tree_edges[i];
		weight_sum += e.w;
		printf("%s %s %d
", str_vertex[e.u],str_vertex[e.v],e.w);
	}
	printf("           :%d
",weight_sum);
	graph_destroy(g);
	return 0;
}

22.2.2 Primアルゴリズム
22.2.2.1 Primアルゴリズム、最小優先度キューを使用して実現

 
   #include 
#include 
#include 
#include 
#include 
typedef struct graph_type *graph;
struct edge {
	int u;
	int v;
	int w;
};
struct graph_node {
	int key;
	int w;
	struct graph_node *next;
};
void graph_node_ini(struct graph_node *x, int key, int w)
{
	x->key = key;
	x->w = w;
	x->next = NULL;
}

struct vertex {
	int dis;
	int parent;
	bool in_queue;		//       
	char str_vertex[256];	//        ，   
};
void vertex_ini(struct vertex *v)
{
	v->dis = INT_MAX;
	v->parent = -1;
	v->in_queue = false;
	strcpy(v->str_vertex, "");
}

struct graph_type {
	struct graph_node **adj;
	struct vertex *vertex_array;
	int v_num;
	int e_num;
};
//      0~v_num-1  ,str_vertex         ，   
graph graph_create(int v_num, char *str_vertex[])
{
	graph g = malloc(sizeof(struct graph_type));
	g->v_num = v_num;
	g->e_num = 0;
	g->adj = malloc(sizeof(struct graph_node *) * v_num);
	g->vertex_array = malloc(sizeof(struct vertex) * v_num);
	for (int i = 0; i < v_num; i++) {
		g->adj[i] = NULL;
		strcpy(g->vertex_array[i].str_vertex, str_vertex[i]);
	}
	return g;
}

void graph_destroy(graph g)
{
	for (int i = 0; i < g->v_num; i++) {
		for (struct graph_node * x = g->adj[i]; x != NULL;) {
			struct graph_node *del = x;
			x = x->next;
			free(del);
		}
	}
	free(g->adj);
	free(g->vertex_array);
	free(g);
}

void graph_insert_edge(graph g, struct edge e)
{
	struct graph_node *u = malloc(sizeof(struct graph_node));
	graph_node_ini(u, e.u, e.w);
	struct graph_node *v = malloc(sizeof(struct graph_node));
	graph_node_ini(v, e.v, e.w);
	//     , v     u
	v->next = g->adj[e.u];
	g->adj[e.u] = v;
	//     , u     v
	u->next = g->adj[e.v];
	g->adj[e.v] = u;
	++g->e_num;
}

void graph_display(graph g)
{
	printf("%d vertices,%d edges
", g->v_num, g->e_num);
	for (int i = 0; i < g->v_num; i++) {
		printf("%s: ", g->vertex_array[i].str_vertex);
		for (struct graph_node * x = g->adj[i]; x != NULL; x = x->next) {
			printf("%s,%d ", g->vertex_array[x->key].str_vertex,
			       x->w);
		}
		printf("
");
	}
}

void swap(void *a, void *b, size_t elem_size)
{
	if (a == NULL || b == NULL || a == b)
		return;
	char temp[elem_size];	/*     */
	memcpy(temp, a, elem_size);
	memcpy(a, b, elem_size);
	memcpy(b, temp, elem_size);
}

/*          */
typedef struct priority_queue_index_type *priority_queue;
struct priority_queue_index_type {
	int heap_size;
	int *index_array;
	int *index_pos_array;	/*               */
	void *data_array;
	size_t elem_size;
	int (*comp) (const void *, const void *);
};
int parent(int i)
{
	return (i - 1) / 2;
}

int left_child(int i)
{
	return i * 2 + 1;
}

int right_child(int i)
{
	return i * 2 + 2;
}

void swap_index(priority_queue pq, int i, int j)
{
	swap(&pq->index_pos_array[i], &pq->index_pos_array[j], sizeof(int));
	pq->index_array[pq->index_pos_array[i]] = i;
	pq->index_array[pq->index_pos_array[j]] = j;
}

/*         */
bool compare(priority_queue pq, int left, int right)
{
	if (pq->data_array == NULL)
		return false;
	char *pc_array = pq->data_array;
	return pq->comp(&pc_array[left * pq->elem_size],
			&pc_array[right * pq->elem_size]) > 0;
}

void heapify(priority_queue pq, int i)
{
	int left = left_child(i);
	int right = right_child(i);
	int largest = i;
	if (left < pq->heap_size
	    && compare(pq, pq->index_array[largest], pq->index_array[left])) {
		largest = left;
	}
	if (right < pq->heap_size
	    && compare(pq, pq->index_array[largest], pq->index_array[right])) {
		largest = right;
	}
	if (largest != i) {
		swap_index(pq, pq->index_array[i], pq->index_array[largest]);
		heapify(pq, largest);
	}
}

void fix_up(priority_queue pq, int i)
{
	while (i > 0
	       && compare(pq, pq->index_array[parent(i)], pq->index_array[i])) {
		swap_index(pq, pq->index_array[parent(i)], pq->index_array[i]);
		i = parent(i);
	}
}

priority_queue priority_queue_create(void *p_data_array, size_t elem_size,
				     int length, int (*comp) (const void *,
							      const void *))
{
	priority_queue pq = malloc(sizeof(struct priority_queue_index_type));
	pq->index_array = malloc(sizeof(int) * length);
	pq->index_pos_array = malloc(sizeof(int) * length);
	pq->data_array = p_data_array;
	pq->elem_size = elem_size;
	pq->heap_size = 0;
	pq->comp = comp;
	return pq;
}

void priority_queue_destroy(priority_queue pq)
{
	free(pq->index_array);
	free(pq->index_pos_array);
	free(pq);
}

int priority_queue_top(priority_queue pq)
{
	return pq->index_array[0];
}

/*             */
int priority_queue_extract_top(priority_queue pq)
{
	swap_index(pq, pq->index_array[0], pq->index_array[pq->heap_size - 1]);
	--pq->heap_size;
	heapify(pq, 0);
	return pq->index_array[pq->heap_size];
}

/*           */
void priority_queue_insert(priority_queue pq, int index)
{
	++pq->heap_size;
	int i = pq->heap_size - 1;
	pq->index_array[i] = index;
	pq->index_pos_array[index] = i;
	fix_up(pq, i);
}

bool priority_queue_is_empty(priority_queue pq)
{
	return pq->heap_size == 0;
}

/*   index      ，            */
void priority_queue_change_index(priority_queue pq, int index)
{
	fix_up(pq, pq->index_pos_array[index]);
	heapify(pq, pq->index_pos_array[index]);
}

int cmp_vertex(const void *p1, const void *p2)
{
	const struct vertex *pa = p1;
	const struct vertex *pb = p2;
	if (pa->dis < pb->dis)
		return -1;
	if (pa->dis == pb->dis)
		return 0;
	return 1;
}

void graph_mst_prim(graph g, int r, struct edge tree_edges[],
		    int *tree_edge_num)
{
	priority_queue pq =
	    priority_queue_create(g->vertex_array, sizeof(struct vertex),
				  g->v_num, cmp_vertex);
	for (int i = 0; i < g->v_num; i++) {
		g->vertex_array[i].dis = INT_MAX;
		g->vertex_array[i].parent = -1;
		g->vertex_array[i].in_queue = true;
		priority_queue_insert(pq, i);
	}
	g->vertex_array[r].dis = 0;
	priority_queue_change_index(pq, r);
	*tree_edge_num = 0;
	while (!priority_queue_is_empty(pq)) {
		int u = priority_queue_extract_top(pq);
		if (u != r) {
			struct edge edge = { g->vertex_array[u].parent, u,
				g->vertex_array[u].dis
			};
			tree_edges[(*tree_edge_num)++] = edge;
		}
		g->vertex_array[u].in_queue = false;	//      
		for (struct graph_node * x = g->adj[u]; x != NULL; x = x->next) {
			int v = x->key;
			//    
			if (g->vertex_array[v].in_queue
			    && x->w < g->vertex_array[v].dis) {
				g->vertex_array[v].parent = u;
				g->vertex_array[v].dis = x->w;
				priority_queue_change_index(pq, v);
			}
		}
	}
	priority_queue_destroy(pq);
}

int main()
{
	//        23-1
	char *str_vertex[9] = { "a", "b", "c", "d", "e", "f", "g", "h", "i" };
	graph g = graph_create(9, str_vertex);
	struct edge edges[] = {
		{0, 1, 4}, {0, 7, 8}, {1, 7, 11},
		{1, 2, 8}, {2, 8, 2}, {2, 5, 4}, {2, 3, 7},
		{3, 4, 9}, {3, 5, 14}, {4, 5, 10}, {5, 6, 2},
		{6, 7, 1}, {6, 8, 6}, {7, 8, 7}
	};
	for (unsigned i = 0; i < sizeof(edges) / sizeof(edges[0]); i++) {
		graph_insert_edge(g, edges[i]);
	}
	printf("   :
");
	graph_display(g);
	struct edge tree_edges[sizeof(edges) / sizeof(edges[0])];
	int edge_tree_num;
	printf("         :
");
	graph_mst_prim(g, 0, tree_edges, &edge_tree_num);
	int weight_sum = 0;
	for (int i = 0; i < edge_tree_num; i++) {
		struct edge e = tree_edges[i];
		weight_sum += e.w;
		printf("%s %s %d
", str_vertex[e.u], str_vertex[e.v], e.w);
	}
	printf("           :%d
", weight_sum);
	graph_destroy(g);
	return 0;
}
  
  
 
  22.2.2.2 Prim  ,          
   
   #include 
#include 
#include 
#include 
#include 
#include 
typedef struct graph_type *graph;
struct edge {
	int u;
	int v;
	int w;
};
struct graph_node {
	int key;
	int w;
	struct graph_node *next;
};
void graph_node_ini(struct graph_node *x, int key, int w)
{
	x->key = key;
	x->w = w;
	x->next = NULL;
}

struct vertex {
	int v;			//  
	int dis;
	int parent;
	char str_vertex[256];	//        ，   
};
void vertex_ini(struct vertex *v)
{
	v->v = -1;
	v->dis = INT_MAX;
	v->parent = -1;
	strcpy(v->str_vertex, "");
}

struct graph_type {
	struct graph_node **adj;
	struct vertex *vertex_array;
	int v_num;
	int e_num;
};
//      0~v_num-1  ,str_vertex         ，   
graph graph_create(int v_num, char *str_vertex[])
{
	graph g = malloc(sizeof(struct graph_type));
	g->v_num = v_num;
	g->e_num = 0;
	g->adj = malloc(sizeof(struct graph_node *) * v_num);
	g->vertex_array = malloc(sizeof(struct vertex) * v_num);
	for (int i = 0; i < v_num; i++) {
		g->adj[i] = NULL;
		strcpy(g->vertex_array[i].str_vertex, str_vertex[i]);
	}
	return g;
}

void graph_destroy(graph g)
{
	for (int i = 0; i < g->v_num; i++) {
		for (struct graph_node * x = g->adj[i]; x != NULL;) {
			struct graph_node *del = x;
			x = x->next;
			free(del);
		}
	}
	free(g->adj);
	free(g->vertex_array);
	free(g);
}

void graph_insert_edge(graph g, struct edge e)
{
	struct graph_node *u = malloc(sizeof(struct graph_node));
	graph_node_ini(u, e.u, e.w);
	struct graph_node *v = malloc(sizeof(struct graph_node));
	graph_node_ini(v, e.v, e.w);
	//     , v     u
	v->next = g->adj[e.u];
	g->adj[e.u] = v;
	//     , u     v
	u->next = g->adj[e.v];
	g->adj[e.v] = u;
	++g->e_num;
}

void graph_display(graph g)
{
	printf("%d vertices,%d edges
", g->v_num, g->e_num);
	for (int i = 0; i < g->v_num; i++) {
		printf("%s: ", g->vertex_array[i].str_vertex);
		for (struct graph_node * x = g->adj[i]; x != NULL; x = x->next) {
			printf("%s,%d ", g->vertex_array[x->key].str_vertex,
			       x->w);
		}
		printf("
");
	}
}

typedef struct heap *heap;
struct heap_node {
	void *key;
	int degree;
	bool mark;
	struct heap_node *child;
	struct heap_node *left;
	struct heap_node *right;
	struct heap_node *parent;
};
struct heap {
	int (*comp) (const void *, const void *);
	struct heap_node *min;
	int num;
};
void heap_node_ini(struct heap_node *x, void *key)
{
	x->key = key;
	x->degree = 0;
	x->mark = false;
	x->parent = NULL;
	x->child = NULL;
	x->left = x;
	x->right = x;
}

void swap(void *a, void *b, size_t elem_size)
{
	if (a == NULL || b == NULL || a == b)
		return;
	char temp[elem_size];	/*     */
	memcpy(temp, a, elem_size);
	memcpy(a, b, elem_size);
	memcpy(b, temp, elem_size);
}

heap heap_create(int (*comp) (const void *, const void *))
{
	heap h = malloc(sizeof(struct heap));
	h->comp = comp;
	h->num = 0;
	h->min = NULL;
	return h;
}

//    ，    x      ，      
void list_delete(struct heap_node **pos, struct heap_node *x)
{
	if (x->right == x)	//      
	{
		*pos = NULL;
		return;
	}
	x->left->right = x->right;
	x->right->left = x->left;
	if (*pos == x) {
		*pos = x->right;
	}
}

//    x pos   ,  pos  ，pos＝x
void list_insert(struct heap_node **pos, struct heap_node *x)
{
	if (*pos == NULL) {
		*pos = x;
		x->left = x;
		x->right = x;
	} else {
		x->left = (*pos)->left;
		(*pos)->left->right = x;
		x->right = (*pos);
		(*pos)->left = x;
	}
}

void add_root(heap h, struct heap_node *x)
{
	list_insert(&h->min, x);
	x->parent = NULL;
	x->mark = false;
	if (h->comp(x->key, h->min->key) < 0) {
		h->min = x;
	}
}

//        x        ，    x    ， key[x]      
void heap_insert(heap h, struct heap_node *x)
{
	x->degree = 0;
	x->parent = NULL;
	x->child = NULL;
	x->left = x;
	x->right = x;
	add_root(h, x);
	++h->num;
}

//    
struct heap_node *heap_minimum(heap h)
{
	return h->min;
}

void heap_destroy(heap h);
//               ，               
void heap_union(heap ha, heap hb)
{
	if (hb == NULL || hb->min == NULL) {
		return;
	}
	if (ha->min == NULL) {
		ha->min = hb->min;
	} else {
		//         
		struct heap_node *ha_min_right = ha->min->right;
		ha->min->right = hb->min;
		//            ，       
		struct heap_node *hb_min_left = hb->min->left;
		hb->min->left = ha->min;
		hb_min_left->right = ha_min_right;
		ha_min_right->left = hb_min_left;
	}
	if (ha->min == NULL
	    || (hb->min != NULL && ha->comp(hb->min->key, ha->min->key) < 0)) {
		ha->min = hb->min;
	}
	ha->num += hb->num;
	hb->min = NULL;
	heap_destroy(hb);
}

void link(heap h, struct heap_node *y, struct heap_node *x)
{
	list_delete(&h->min, y);
	list_insert(&x->child, y);
	y->parent = x;
	y->mark = false;
	++x->degree;
}

//    
void consolidate(heap h)
{
	if (h->min == NULL)
		return;
	int D = floor(log(h->num) / log(1.618));	//  D 
	struct heap_node *A[D];
	for (int i = 0; i < D; i++) {
		A[i] = NULL;
	}
	struct heap_node *x = NULL;
	struct heap_node *y = NULL;
	int d;
	struct heap_node *w = h->min;
	struct heap_node *end = h->min->left;
	bool loop_flag = true;
	while (loop_flag) {
		x = w;
		if (w != end) {
			w = w->right;
		} else {
			loop_flag = false;	//w        ，    
		}
		d = x->degree;
		while (A[d] != NULL) {
			y = A[d];
			if (h->comp(x->key, y->key) > 0) {
				swap(&x, &y, sizeof(struct heap_node *));
			}
			link(h, y, x);
			A[d] = NULL;
			++d;
		}
		A[d] = x;
	}
	h->min = NULL;
	for (int i = 0; i < D; ++i) {
		if (A[i] != NULL) {
			add_root(h, A[i]);
		}
	}
}

//            ，             
struct heap_node *heap_extract_min(heap h)
{
	struct heap_node *z = h->min;
	if (z == NULL)
		return NULL;
	struct heap_node *x = NULL;
	while (z->degree > 0) {
		x = z->child;
		if (x->right == x) {
			z->child = NULL;
		} else {
			z->child = z->child->right;
		}
		list_delete(&z->child, x);
		add_root(h, x);
		--z->degree;
	}
	if (z == z->right) {
		list_delete(&h->min, z);
	} else {
		list_delete(&h->min, z);
		consolidate(h);
	}
	--h->num;
	return z;
}

void cut(heap h, struct heap_node *x, struct heap_node *y)
{
	list_delete(&y->child, x);
	add_root(h, x);
	--y->degree;
}

void cascading_cut(heap h, struct heap_node *y)
{
	struct heap_node *z = y->parent;
	if (z == NULL)
		return;
	if (y->mark == false) {
		y->mark = true;
	} else {
		cut(h, y, z);
		cascading_cut(h, z);
	}
}

//            x           k，  k  x       ，    
void heap_decrease_key(heap h, struct heap_node *x)
{
	struct heap_node *y = x->parent;
	if (y != NULL && h->comp(x->key, y->key) < 0) {
		cut(h, x, y);
		cascading_cut(h, y);
	}
	if (h->comp(x->key, h->min->key) < 0) {
		h->min = x;
	}
}

bool heap_is_empty(heap h)
{
	return h->min == NULL;
}

void heap_destroy(heap h)
{
	while (!heap_is_empty(h)) {
		struct heap_node *x = heap_extract_min(h);
		free(x->key);
		free(x);
	}
	free(h);
}

int cmp_vertex(const void *p1, const void *p2)
{
	const struct vertex *pa = p1;
	const struct vertex *pb = p2;
	if (pa->dis < pb->dis)
		return -1;
	if (pa->dis == pb->dis)
		return 0;
	return 1;
}

void graph_mst_prim(graph g, int r, struct edge tree_edges[],
		    int *tree_edge_num)
{
	heap h = heap_create(cmp_vertex);
	struct heap_node *x = NULL;
	struct heap_node *node_array[g->v_num];
	struct vertex *p_vertex;
	for (int i = 0; i < g->v_num; i++) {
		x = malloc(sizeof(struct heap_node));
		heap_node_ini(x,&g->vertex_array[i]);
		p_vertex=x->key;
		p_vertex->dis = INT_MAX;
		p_vertex->parent = -1;
		p_vertex->v = i;
		node_array[i] = x;
		heap_insert(h, x);
	}
	p_vertex = node_array[r]->key;
	p_vertex->dis = 0;
	heap_decrease_key(h, node_array[r]);
	*tree_edge_num = 0;
	while (!heap_is_empty(h)) {
		x = heap_extract_min(h);
		p_vertex = x->key;
		int u = p_vertex->v;
		if (u != r) {
			struct edge e = { p_vertex->parent, u, p_vertex->dis };
			tree_edges[(*tree_edge_num)++] = e;
		}
		free(x);
		node_array[u] = NULL;
		for (struct graph_node * p = g->adj[u]; p != NULL; p = p->next) {
			int v = p->key;
			//    
			if (node_array[v] != NULL) {
				p_vertex = node_array[v]->key;
				if (p->w < p_vertex->dis) {
					p_vertex->parent = u;
					p_vertex->dis = p->w;
					heap_decrease_key(h, node_array[v]);
				}
			}
		}
	}
	heap_destroy(h);
}

int main()
{
	//        23-1
	char *str_vertex[9] = { "a", "b", "c", "d", "e", "f", "g", "h", "i" };
	graph g = graph_create(9, str_vertex);
	struct edge edges[] = {
		{0, 1, 4}, {0, 7, 8}, {1, 7, 11},
		{1, 2, 8}, {2, 8, 2}, {2, 5, 4}, {2, 3, 7},
		{3, 4, 9}, {3, 5, 14}, {4, 5, 10}, {5, 6, 2},
		{6, 7, 1}, {6, 8, 6}, {7, 8, 7}
	};
	for (unsigned i = 0; i < sizeof(edges) / sizeof(edges[0]); i++) {
		graph_insert_edge(g, edges[i]);
	}
	printf("   :
");
	graph_display(g);
	struct edge tree_edges[sizeof(edges) / sizeof(edges[0])];
	int edge_tree_num;
	printf("         :
");
	graph_mst_prim(g, 0, tree_edges, &edge_tree_num);
	int weight_sum = 0;
	for (int i = 0; i < edge_tree_num; i++) {
		struct edge e = tree_edges[i];
		weight_sum += e.w;
		printf("%s %s %d
", str_vertex[e.u], str_vertex[e.v], e.w);
	}
	printf("           :%d
", weight_sum);
	graph_destroy(g);
	return 0;
}  
  
 
  22.2.2.3 Prim  ,        
   
   
   #include 
#include 
#include 
#include 
#include 
typedef struct graph_type *graph;
struct edge {
	int u;
	int v;
	int w;
};
struct vertex {
	int v;			//  
	int dis;
	int parent;
	char str_vertex[256];	//        ，   
	//        ，              
	struct heap_node **node_array;
};
struct graph_node {
	int key;
	int w;
	struct graph_node *next;
};
void graph_node_ini(struct graph_node *x, int key, int w)
{
	x->key = key;
	x->w = w;
	x->next = NULL;
}

struct graph_type {
	struct graph_node **adj;
	struct vertex *vertex_array;
	int v_num;
	int e_num;
};
//      0~v_num-1  ,str_vertex         ，   
graph graph_create(int v_num, char *str_vertex[])
{
	graph g = malloc(sizeof(struct graph_type));
	g->v_num = v_num;
	g->e_num = 0;
	g->adj = malloc(sizeof(struct graph_node *) * v_num);
	g->vertex_array = malloc(sizeof(struct vertex) * v_num);
	for (int i = 0; i < v_num; i++) {
		g->adj[i] = NULL;
		strcpy(g->vertex_array[i].str_vertex, str_vertex[i]);
	}
	return g;
}

void graph_destroy(graph g)
{
	for (int i = 0; i < g->v_num; i++) {
		for (struct graph_node * x = g->adj[i]; x != NULL;) {
			struct graph_node *del = x;
			x = x->next;
			free(del);
		}
	}
	free(g->adj);
	free(g->vertex_array);
	free(g);
}

void graph_insert_edge(graph g, struct edge e)
{
	struct graph_node *u = malloc(sizeof(struct graph_node));
	graph_node_ini(u, e.u, e.w);
	struct graph_node *v = malloc(sizeof(struct graph_node));
	graph_node_ini(v, e.v, e.w);
	//     , v     u
	v->next = g->adj[e.u];
	g->adj[e.u] = v;
	//     , u     v
	u->next = g->adj[e.v];
	g->adj[e.v] = u;
	++g->e_num;
}

void graph_display(graph g)
{
	printf("%d vertices,%d edges
", g->v_num, g->e_num);
	for (int i = 0; i < g->v_num; i++) {
		printf("%s: ", g->vertex_array[i].str_vertex);
		for (struct graph_node * x = g->adj[i]; x != NULL; x = x->next) {
			printf("%s,%d ", g->vertex_array[x->key].str_vertex,
			       x->w);
		}
		printf("
");
	}
}

typedef struct binomial_heap *heap;
struct heap_node {
	void *key;
	int degree;
	struct heap_node *child;
	struct heap_node *sibling;
	struct heap_node *parent;
};
struct binomial_heap {
	int (*comp) (const void *, const void *);
	//                
	void (*on_swap) (struct heap_node *, struct heap_node *);
	struct heap_node *head;
};
void swap(void *a, void *b, size_t elem_size)
{
	if (a == NULL || b == NULL || a == b)
		return;
	char temp[elem_size];	/*     */
	memcpy(temp, a, elem_size);
	memcpy(a, b, elem_size);
	memcpy(b, temp, elem_size);
}

void heap_node_ini(struct heap_node *x, void *key)
{
	x->key = key;
	x->degree = 0;
	x->parent = NULL;
	x->child = NULL;
	x->sibling = NULL;
}

heap heap_create(int (*comp) (const void *, const void *),
		 void (*on_swap) (struct heap_node *, struct heap_node *))
{
	heap h = malloc(sizeof(struct binomial_heap));
	h->comp = comp;
	h->on_swap = on_swap;
	h->head = NULL;
	return h;
}

//      ，     n       H           
struct heap_node *heap_minimum(heap h)
{
	struct heap_node *y = NULL;
	struct heap_node *x = h->head;
	void *min;
	bool first = true;
	while (x != NULL) {
		if (first || h->comp(x->key, min) < 0) {
			first = false;
			min = x->key;
			y = x;
		}
		x = x->sibling;
	}
	return y;
}

bool heap_is_empty(heap h)
{
	return h->head == NULL;
}

//   y   z        ， z  y    
void link(struct heap_node *y, struct heap_node *z)
{
	y->parent = z;
	y->sibling = z->child;
	z->child = y;
	z->degree = z->degree + 1;
}

void heap_destroy(heap h);
// ha hb                    
struct heap_node *heap_merge(heap ha, heap hb)
{
	struct heap_node *pa = ha->head;
	struct heap_node *pb = hb->head;
	struct heap_node *head = NULL;
	struct heap_node *tail = NULL;
	while (pa != NULL && pb != NULL) {
		if (pa->degree <= pb->degree) {
			if (head == NULL) {
				head = pa;
				tail = pa;
				pa = pa->sibling;
				tail->sibling = NULL;
			} else {
				tail->sibling = pa;
				pa = pa->sibling;
				tail = tail->sibling;
				tail->sibling = NULL;
			}
		} else {
			if (head == NULL) {
				head = pb;
				tail = pb;
				pb = pb->sibling;
				tail->sibling = NULL;
			} else {
				tail->sibling = pb;
				pb = pb->sibling;
				tail = tail->sibling;
				tail->sibling = NULL;
			}
		}
	}
	if (pa != NULL && pb == NULL) {
		if (head == NULL) {
			head = pa;
			tail = pa;
		} else {
			tail->sibling = pa;
		}
	}
	if (pa == NULL && pb != NULL) {
		if (head == NULL) {
			head = pb;
			tail = pb;
		} else {
			tail->sibling = pb;
		}
	}
	hb->head = NULL;
	heap_destroy(hb);
	return head;
}

// hb   ha 
void heap_union(heap ha, heap hb)
{
	// ha hb                       
	ha->head = heap_merge(ha, hb);
	if (ha->head == NULL) {
		return;
	}
	struct heap_node *prev = NULL;
	struct heap_node *x = ha->head;
	struct heap_node *next = x->sibling;
	while (next != NULL) {
		//  1:x->degree!=next->degree
		//  2:x->degree==next->degree==next->sibling->degree
		if ((x->degree != next->degree) ||
		    (next->sibling != NULL
		     && next->sibling->degree == x->degree)) {
			prev = x;
			x = next;
		} else if (ha->comp(x->key, next->key) <= 0) {
			//  3:x->degree==next->degree!=next->sibling->degree,x->key<=next->key
			x->sibling = next->sibling;
			link(next, x);
		} else {
			//  4:x->degree==next->degree!=next->sibling->degree,next->key<=x->key
			if (prev == NULL) {
				ha->head = next;
			} else {
				prev->sibling = next;
			}
			link(x, next);
			x = next;
		}
		next = x->sibling;
	}
}

//  x   ，   x          
void reverse_children(struct heap_node *x)
{
	if (x == NULL || x->child == NULL)
		return;
	struct heap_node *prev = x->child;
	struct heap_node *current = prev->sibling;
	struct heap_node *next = NULL;
	while (current != NULL) {
		next = current->sibling;
		current->sibling = prev;
		current->parent = NULL;
		prev = current;
		current = next;
	}
	x->child->sibling = NULL;
	x->child->parent = NULL;
	x->child = prev;
}

//        x      ，    x    ， key[x]      
void heap_insert(heap h, struct heap_node *x)
{
	heap hb = heap_create(h->comp, h->on_swap);
	hb->head = x;
	heap_union(h, hb);
}

struct heap_node *heap_remove_minimum(heap h)
{
	struct heap_node *x = h->head;
	if (x == NULL)
		return NULL;
	struct heap_node *prev = NULL;
	struct heap_node *min_prev = NULL;
	void *min;
	bool first = true;
	while (x != NULL) {
		if (first || h->comp(x->key, min) < 0) {
			first = false;
			min = x->key;
			min_prev = prev;
		}
		prev = x;
		x = x->sibling;
	}
	//    x
	if (min_prev == NULL) {
		x = h->head;
		h->head = x->sibling;
	} else {
		x = min_prev->sibling;
		min_prev->sibling = x->sibling;
	}
	return x;
}

//            ，             
struct heap_node *heap_extract_min(heap h)
{
	struct heap_node *x = heap_remove_minimum(h);
	if (x == NULL)
		return NULL;
	reverse_children(x);
	heap hb = heap_create(h->comp, h->on_swap);
	hb->head = x->child;
	heap_union(h, hb);
	return x;
}

//          x           k，  k  x       ，    
void heap_decrease_key(heap h, struct heap_node *x)
{
	struct heap_node *y = x;
	struct heap_node *z = y->parent;
	while (z != NULL && h->comp(y->key, z->key) < 0) {
		swap(&y->key, &z->key, sizeof(void *));
		if (h->on_swap != NULL) {
			h->on_swap(y, z);
		}
		y = z;
		z = y->parent;
	}
}

void display_node(struct heap_node *x, void (*print_key) (const void *))
{
	print_key(x->key);
	printf(" ");
	if (x->child != NULL) {
		display_node(x->child, print_key);
	}
	if (x->sibling != NULL) {
		display_node(x->sibling, print_key);
	}
}

void heap_display(heap h, void (*print_key) (const void *))
{
	display_node(h->head, print_key);
	printf("
");
}

void heap_destroy(heap h)
{
	while (!heap_is_empty(h)) {
		struct heap_node *x = heap_extract_min(h);
		free(x->key);
		free(x);
	}
	free(h);
}

void vertex_ini(struct vertex *v)
{
	v->v = -1;
	v->dis = INT_MAX;
	v->parent = -1;
	strcpy(v->str_vertex, "");
}

void on_swap(struct heap_node *left, struct heap_node *right)
{
	struct vertex *lv = left->key;
	struct vertex *rv = right->key;
	lv->node_array[lv->v] = left;
	lv->node_array[rv->v] = right;
}

int cmp_vertex(const void *p1, const void *p2)
{
	const struct vertex *pa = p1;
	const struct vertex *pb = p2;
	if (pa->dis < pb->dis)
		return -1;
	if (pa->dis == pb->dis)
		return 0;
	return 1;
}

void graph_mst_prim(graph g, int r, struct edge tree_edges[],
		    int *tree_edge_num)
{
	heap h = heap_create(cmp_vertex, on_swap);
	struct heap_node *x = NULL;
	struct heap_node *node_array[g->v_num];
	struct vertex *p_vertex;
	for (int i = 0; i < g->v_num; i++) {
		x = malloc(sizeof(struct heap_node));
		heap_node_ini(x,&g->vertex_array[i]);
		p_vertex = x->key;
		p_vertex->dis = INT_MAX;
		p_vertex->parent = -1;
		p_vertex->v = i;
		p_vertex->node_array = node_array;
		node_array[i] = x;
		heap_insert(h, x);
	}
	p_vertex = node_array[r]->key;
	p_vertex->dis = 0;
	heap_decrease_key(h, node_array[r]);
	*tree_edge_num = 0;
	while (!heap_is_empty(h)) {
		x = heap_extract_min(h);
		p_vertex = x->key;
		int u = p_vertex->v;
		if (u != r) {
			struct edge e = { p_vertex->parent, u, p_vertex->dis };
			tree_edges[(*tree_edge_num)++] = e;
		}
		free(x);
		node_array[u] = NULL;
		for (struct graph_node * p = g->adj[u]; p != NULL; p = p->next) {
			int v = p->key;
			//    
			if (node_array[v] != NULL) {
				p_vertex = node_array[v]->key;
				if (p->w < p_vertex->dis) {
					p_vertex->parent = u;
					p_vertex->dis = p->w;
					heap_decrease_key(h, node_array[v]);
				}
			}
		}
	}
	heap_destroy(h);
}

int main()
{
	//        23-1
	char *str_vertex[9] = { "a", "b", "c", "d", "e", "f", "g", "h", "i" };
	graph g = graph_create(9, str_vertex);
	struct edge edges[] = {
		{0, 1, 4}, {0, 7, 8}, {1, 7, 11},
		{1, 2, 8}, {2, 8, 2}, {2, 5, 4}, {2, 3, 7},
		{3, 4, 9}, {3, 5, 14}, {4, 5, 10}, {5, 6, 2},
		{6, 7, 1}, {6, 8, 6}, {7, 8, 7}
	};
	for (unsigned i = 0; i < sizeof(edges) / sizeof(edges[0]); i++) {
		graph_insert_edge(g, edges[i]);
	}
	printf("   :
");
	graph_display(g);
	struct edge tree_edges[sizeof(edges) / sizeof(edges[0])];
	int edge_tree_num;
	printf("         :
");
	graph_mst_prim(g, 0, tree_edges, &edge_tree_num);
	int weight_sum = 0;
	for (int i = 0; i < edge_tree_num; i++) {
		struct edge e = tree_edges[i];
		weight_sum += e.w;
		printf("%s %s %d
", str_vertex[e.u], str_vertex[e.v], e.w);
	}
	printf("           :%d
", weight_sum);
	graph_destroy(g);
	return 0;
}

アルゴリズム--正規表現の一致

データ構造疎行列の三元群加算と高速回転アルゴリズム