最小生成树---Kruskal_小根堆只保证最顶端

/ alg_for_test.cpp : 定义控制台应用程序的入口点。
//
 
#include "stdafx.h"
 
 
#include <float.h> //FLT_MAX 
 
#include <stdlib.h>
 
#define  NUMOFDOT 6 //点的个数
 
 
//定义一条边，两个点及其边的权值
typedef struct node
{
	int node1;
	int node2; 
	float weight;
}EdgeNode;
 
void createMinHeap(EdgeNode *heap, int heapSize) ;
EdgeNode removeMin(EdgeNode *heap, int heapSize) ;
void small_root_heapify(EdgeNode *heap, int i, int heapSize) ;
 
void printHeap(EdgeNode heap[],int HeapSize);
 
void kruskal(EdgeNode myEdgeNode[] );
 
int main()
{
	float c[NUMOFDOT][NUMOFDOT] = {
		FLT_MAX, 6, 1, 5, FLT_MAX, FLT_MAX,
		6, FLT_MAX, 5, FLT_MAX, 3, FLT_MAX,
		1, 5, FLT_MAX, 5, 6, 4,
		5, FLT_MAX, 5, FLT_MAX, FLT_MAX, 2,
		FLT_MAX, 3, 6, FLT_MAX, FLT_MAX, 6,
		FLT_MAX, FLT_MAX, 4, 2, 6, FLT_MAX
	};
 
	EdgeNode myEdgeNode[NUMOFDOT * NUMOFDOT];
	int cnt = 0;
	for(int i = 0; i < NUMOFDOT; i++)
	{
		for(int j = 0; j < NUMOFDOT; j++)
		{
			myEdgeNode[cnt].node1 = i;
			myEdgeNode[cnt].node2 = j;
			myEdgeNode[cnt].weight = c[i][j];
			cnt++;
		}
	}
 
	kruskal(myEdgeNode);
 
	system("pause");
 
	return 0;
}
 
 
 
void kruskal(EdgeNode myEdgeNode[] )
{
	int e = NUMOFDOT * NUMOFDOT;
	int flag[NUMOFDOT] = {0, 1, 2, 3, 4, 5 };// 打标机，0表示未加入 "团"
 
	//printHeap(myEdgeNode, e);
 
	createMinHeap(myEdgeNode, e); 
 
	//printHeap(myEdgeNode, e);
 
	int k = 0; //用来记录已经加入的点的个数
	while(e > 0 && k < NUMOFDOT - 1)
	{
		EdgeNode x = (EdgeNode) removeMin(myEdgeNode, e); //从堆中去出权值最小的一条边
	
		//for test
		//printf("e = %d\t, %d,   %d,  %f \n", e, x.node1, x.node2, x.weight);
 
		int a = flag[x.node1];
		int b = flag[x.node2];
		//如果取出的这一条边的两个端点不在一个联通域中，这条边可连接起来
		if(a != b )
		{
 
			printf("edges %d --- %d added\n", x.node1, x.node2);
			//将这两点连接起来，ab属于一个连通域了。。
			flag[x.node2] = flag[x.node1];
 
			k++;
		}
 
		
		e--; //边数-1
 
	}
	
}
 
void printHeap(EdgeNode heap[],int HeapSize)  
{  
	for(int i = 0;i < HeapSize; ++i)  
	{  
		printf("heap's node1 = %d, node2 = %d, weight = %f\n", heap[i].node1, heap[i].node2, heap[i].weight); 
	}  
 
} 
 
void createMinHeap(EdgeNode *heap, int  heapsize)  
{  
	int start = heapsize / 2 - 1;  
 
	for (; start >= 0; start--)  
		small_root_heapify(heap, start, heapsize );  
}  
 
void small_root_heapify(EdgeNode *heap, int i, int  heapsize)  
{  
	int l = 2 * i + 1;  
	int r = 2 * i + 2;  
	int smallest;  
	EdgeNode temp;  
 
	if (l < heapsize && heap[l].weight < heap[i].weight)  
		smallest = l;  
	else  
		smallest = i;  
 
	if (r < heapsize && heap[r].weight < heap[smallest].weight)  
		smallest = r;  
 
	if (i != smallest)  
	{  
		temp = heap[i];  
		heap[i] = heap[smallest];  
		heap[smallest] = temp;    
		small_root_heapify(heap, smallest, heapsize) ;    
	}     
}  
 
EdgeNode removeMin(EdgeNode *heap, int  heapsize)  
{  
	EdgeNode min;  
	if (heapsize < 1)  
		printf("***heap underflow***");  
 
	min = heap[0];  
	heap[0] = heap[heapsize-1];  
	heapsize--;  
	small_root_heapify(heap, 0, heapsize);  
 
	return min;  
}  

以上随便写着玩的，

认真请看《算法设计与分析》