贪心算法设计实验报告

《算法设计技巧与分析》课程实验报告

五、实验步骤

1.用Kruskal算法实现最小生成树

算法描述：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

下面给出c语言代码实现及说明

本程序对树的存储主要是以边为存储对象，即边的结构体里面有这样几个参数：1，边的权值。2，边的一个顶点。3，边的另一个顶点。4，边是否属于生成树的一条边（即最小生成树边标志）。由该程序的存储结构决定了该算法比较适用于边稀疏的情形，至于边稠密的情况会在下面的Prim算法中给出。

在Kruskal算法中有两个比较重要的部分1，对边按权重排序。2，对一条边加入子树后是否会产生回路的判断即判断边的两个节点是否在同一个树中（集合里）

对于问题1：可以有各种排序算法，读者可以自行选择自己喜欢的排序算法来替换代码中的排序算法。（本处使用选择排序算法（效率较低），读者可以自己修改为快速排序或者是对排序） 下面主要讲解解决问题2，解决这个问题一般借用不相交集的思想，即在本程序中每次以同集合中所有点的编号最小的数来标识本集合。（对于根节点即标号最小的节点则标记为0）例如对于上图实例，下面给出详细的不相交集的维护过程（给出前几步的详细说明）

a,初始状态（ABCDEFG分别在数组的第1，2，3，4，5，6，7）0号位空置（均为0）

b,选择第一条边A---D(将D的标记改为1)（因为AD最短）

对表进行维护（维护后仍同上表，因为还没有两个集合合并）

C，选择第二条边C----E（修改上表）

对上表进行维护（任同上表，因为还没有两个集合合并）

D，选择第三条边（D-----F）(根据条件DF两点不再同一集合，改边可选)

然后就合并DF两点所在的集合D的前去是1，即A标记为0，E的标记也为0，合并因为6>1所以表修改如下

以后几步均如上判断两点是否在一个集合从而判断改边是否可取，并维护上表 下面附上源代码

/**************************************************************************************************

Kruskal算法的实现

09网一 殷赛 0910322113

输入：图G(用结构体数组来存储每条边，包含每条边的节点） 输出：图G的最小生成树树

***************************************************************************************************/ #include<stdio.h> #include<stdlib.h> typedef struct Edge {

char dot_1; char dot_2; int weight; int leap;

}Edge;

Edge* selectionsort(Edge *array,int n)//选择排序（对边按权重由高到低排序） {

int i,j,min,temp; for(i=0;i<n;i++) {

min=i;

for(j=i+1;j<n;j++)

if(array[min].weight>array[j].weight)

min=j;

if(min!=i) {

temp=array[i].weight;

}

Edge *Kruskal(Edge *Graph,int num_e,int **V,int num_v)//克鲁斯卡尔算法实现 {

if(V[1][m]!=V[1][n]&&m!=V[1][n]&&n!=V[1][m])//如果边的两个顶点不再一个集合则边是生成树的边(注意首节点的标记和集合里非首节点的标记不同)

array[min].weight=temp;

temp=array[i].dot_1;

array[i].dot_1=array[min].dot_1; array[min].dot_1=temp;

}

}

temp=array[i].dot_2;

array[i].dot_2=array[min].dot_2; array[min].dot_2=temp;

return array;

int m,n,test; int i,j,t,k;

for(i=0;i<num_e;i++) {

for(j=1;j<num_v+1;j++) { }

if(Graph[i].dot_1==V[0][j])

m=j;

if(Graph[i].dot_2==V[0][j])

n=j;

Graph[i].leap=1;

if(V[1][n]==0) { } else { }

//维护不相交集

k=1;//对每个节点都检查是否为标记合格节点 while(k<num_v+1) {

if(V[1][k]!=0)//只要标记不为0都进行整理,只不过有些节点的标记整理前后是

if(V[1][m]==0) { } else { }

if(V[1][m]>V[1][n]) else

V[1][V[1][n]]=V[1][m]; V[1][V[1][m]]=V[1][n]; if(m<V[1][n]) else

V[1][m]=V[1][n]; V[1][V[1][n]]=m;

if(n<V[1][m]) else

V[1][n]=V[1][m]; V[1][V[1][m]]=n;

一样的(即标记符合标准的节点)

}

if(V[1][m]==0&&V[1][n]==0)//如果边的两个顶点是两个集合的首节点则可以合并 {

Graph[i].leap=1; if(m>n) else

V[1][n]=m; V[1][m]=n; }

{ } k++;

t=V[1][k]; while(V[1][t]!=0) { } V[1][k]=t;

t=V[1][t];

//维护不相交集 k=1;

while(k<num_v+1) {

if(V[1][k]!=0) {

t=V[1][k]; while(V[1][t]!=0) { } V[1][k]=t;

t=V[1][t];

} k++;

}

}

/* printf("不相交集的情况：\n"); for(test=1;test<num_v+1;test++)

printf("%-4c",V[0][test]); printf("\n");

for(test=1;test<num_v+1;test++)

printf("%-4d",V[1][test]);

printf("\n");*/

}

return Graph;

}

void main() { int i,j,num_v,num_e,cost=0; Edge *Graph=NULL; int **V=NULL;

printf("请输入土中有多少个顶点!\n"); scanf("%d",&num_v);

V=(int**)malloc(sizeof(int*)*2); for(i=0;i<2;i++)

V[i]=(int*)malloc(sizeof(int)*(num_v+1));

for(i=0;i<2;i++) for(j=0;j<num_v+1;j++)

V[i][j]=0;

for(i=1;i<num_v+1;i++)

{ }

printf("请输入第%d个顶点:",i); scanf(" %c",&V[0][i]);

printf("请输入图中有多少条边!\n"); scanf("%d",&num_e);

Graph=(Edge*)malloc(sizeof(Edge)*num_e); for(i=0;i<num_e;i++) { }

Graph=selectionsort(Graph,num_e);

printf("请输入第%d条边的权值和两个顶点！\n",i+1);

scanf("%d %c %c",&Graph[i].weight,&Graph[i].dot_1,&Graph[i].dot_2); Graph[i].leap=0;

//以上部分是存储图

//--------------------------------------------------------------------------------------------------

Graph=Kruskal(Graph,num_e,V,num_v);

printf("构成最小生成树的边和顶点分别是：\n"); printf("顶点1------ …… 此处隐藏：3448字，全部文档内容请下载后查看。喜欢就下载吧 ……