克鲁斯卡尔算法.cpp

四后问题算法和克鲁卡斯尔算法的具体实现算法

# include<iostream.h>

typedef struct {		// 边的数据结构 
    float     key;		// 边的权 
    int	      u;			// 与边关联的顶点编号
    int	      v;			// 与边关联的顶点编号 
} EDGE;
typedef struct node {	// 顶点的数据结构
    struct node   *p;		// 指向父亲结点 
    int	      rank;		// 结点的秩
    int	      u;			// 顶点编号
};
typedef struct node NODE;
EDGE      E[ m + 1 ], T[ n ];	// 图的边集及生成树
NODE      V[ n ]; 			// 图的顶点集合


void main ()
{
	

}

void kruskal (NODE V[],EDGE E[],EDGE T[],int n,int m)
{
	int i,j,k;
	EDGE e;
	NODE *u,*v;
	make_heap(E,m);//用边集构成最小堆
	for (i=0;i<n;i++){  //每个顶点都作为树的根结点，构成森林
		V[i].rank=0;V[i].p=NULL;
	}
 i = j = 0;  
    while ((i<n-1) && (m>0) {		
        e = delete_min(E, &m);	  // 从堆中取下权最小的边
         u = find(&V[ e.u ]);    	  // 检索该边两顶点所在
         v = find(&V[ e.v ]);	  //         树根		
       if (u != v) {			  // 两顶点不在同一棵树
            union(u, v);                   // 合并成一棵树
            T[ j++ ] = e;		  // 该边置于生成树中	
            i++;
        }                                                    
     }         
}