蛮力法分析库卢卡尔关于最小生成树的算法设计分析.doc

算法设计与分析实验报告三
8
1
8
V4
V1
V5
V3
V2
6
9
10
12
2
3
4
题目内容:
蛮力法分析库卢卡尔关于最小生成树的算法设计分析
Prim算法和 Kruskal算法
Prim算法逐次将最小权的边和相应顶点加到集合中,适合于求边稠密的最小生成树;Kruskal算法先将所有边都放入集合,然后再逐个选择最小权的边,适合于求稀疏的网的最小生成树。
根据克卢卡尔的最小生成树的算法,如上图
已不能形成圈为前提,先把所有边放入一维数组中,再对一维数组进行排序,选择权值最小的边。路径:v3->v2->v4->v1->v5 权值的和=1+3+2+9+4=19
算法分析(伪代码):
:a[]={1,2,3,4,6,8,8,9,10,12} 结点:u[]={v1,v2,v3,v4,v5}
=(V,E),令G的最小生成树为T=(U,TE),其初始状态为U=V,TE={}

。若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边加入到TE中去,同时把两个连通分量连接成一个连通分量;若被考察边的两个结点属于同一个连通分量,则舍去此边,以免造成回路,如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树.
蛮力法遍历代码程序:
#include<> 
#include<> 
#define M 20 
#define MAX 20 
typedef struct 
{ 
int begin; 
int end; 
int weight; 
}edge; 
typedef struct 
{
int adj; 
int weight;  
}AdjMatrix[MAX][MAX]; 
typedef struct 
{  
AdjMatrix arc;
int vexnum, um; }MGraph;
void CreatGraph(MGraph *); void sort(edge* ,MGraph *); void MiniSpanTree(MGraph *); int Find(int *, int ); void Swapn(edge *, int, int); void CreatGraph(MGraph *G) {
int i, j,n, m;
printf("请输入边数和顶点数:");
scanf("%d %d",&G->um,&G->vexnum);
for (i = 1; i <= G->vexnum; i++) {
for ( j = 1; j <= G->vexnum; j++) {
G->arc[i][j].adj = G->arc[j][i].adj = 0; } }
for ( i = 1; i <= G->um; i++) {
printf("\n请输入有边的2个顶点"); scanf("%d %d",&n,&m);
while(n < 0 || n > G->vexnum || m < 0 || n > G->