最小生成树算法的设计与实现

一、实验目的

1、根据算法设计需要, 掌握连通网的灵活表示方法;

2、掌握最小生成树算法，如Prim、Kruskal算法;

3、基本掌握贪心算法的一般设计方法;

4、进一步掌握集合的表示与操作算法的应用.

二、预习与参考

1、认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法;

2、设计Kruskal算法实验程序.

[参考数据类型或变量]

typedef NodeNumber int; /* 节点编号 */ typedef CostType int; /* 成本值类型 */

typedef ElemType NodeNumber /* 实型或任意其它元素类型 */

typedef struct { int ElemType; int tag; }NODE; typedef struct { CostType cost; NodeNumber node1, node2; }EDGE; NODE set[]={{1,-1},…,{n,-1}}; /* 节点集, n为连通网的节点数 */ EDGE es[ ]={{values of e1},…,{ values of em}}; /* 边集, m为连通网的边数 */ EDGE st[n-1]; /* 最小生成树的边集 */

[参考子程序接口与功能描述]

int Find(NODE *set, ElemType elem) 功能: 在数组set中顺序查找元素elem, 如果不成功, 返回-1; 否则, 使用带压缩规则的查找算法,返回所在子集的根节点索引.

int Union(NODE *set, ElemType elem1, ElemType elem2)

功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.

void Sort(EDGE *es, int n)

功能: 用任意分类算法将连通图的边集按成本值的非降次序分类.

void Kruskal(EDGE *es, int m, NODE *set, int n, EDGE *st)

功能: 对有n个节点, m条边的连通网, 应用Kruskal算法生成最小生成树, 最小生成树的边存储在数组st中.

void Output(EDGE *st, int n)

功能: 输出最小生成树的各条边.

三、实验要求

上机实验时，一人一组，独立上机。

有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。

四、实验步骤

1、设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止;

2、待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成功能模块存盘备用.

五、测试

Input:

6

1 2 6

1 3 1

1 4 5

2 3 5

2 5 6

3 4 5

3 5 6

3 6 4

4 6 2

5 6 6

0 0 0

Putout:

18

六、实验报告要求

1、阐述实验目的和实验内容;

2、阐述Kruskal算法的原理方法;

3、提交实验程序的功能模块;

4、提供测试数据和相应的最小生成树。

七、思考题

1、设计由连通网初始边集数组生成最小堆的算法;

2、设计输出堆顶元素, 并将剩余元素调整成最小堆的算法;

3、针对连通网初始边集最小堆表示, 设计Kruskal算法;

4、采用成本邻接矩阵表示连通网时, 在剩余边中如何实现最小成本边的查找? 采用成本邻接矩阵表示连通网时, 用C语言实现Prim算法.

 

第二篇：算法分析与设计实验报告-单源最短路径、最小生成树

实验报告

实验三 单源最短路径、最小生成树

一．实验目的

（1） 学习单源最短路径问题的简单算法，掌握原理，运用C++编程实现。

（2） 学习最小生成树问题的简单算法，掌握原理，运用C++编程实现。

二．实验内容

（1）设计单源最短路径问题的算法，上机编程实现。

（2）设计最小生成树问题的算法，上机编程实现。

三．实验代码

1 . 单源最短路径问题的程序代码如下：

#include <iostream>

using namespace std;

#define MAX 999

void getdata(int **c,int n)

{ int i,j;

int begin,end,weight;

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

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

{ if(i==j)

c[i][j]=0;

else

c[i][j]=MAX;

}

}

do {

cout<<"请输入 起点 终点 权值(-1退出)：";

cin>>begin;

if(begin==-1) break;

cin>>end>>weight;

c[begin][end]=weight;

} while(begin!=-1);

}

void Dijkstra(int n,int v ,int *dist,int *prev,int **c)

{ bool s[MAX];

int i,j;

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

{ dist[i]=c[v][i]; //从源点到各点的值

s[i]=false;

if(dist[i]==MAX) prev[i]=0; //最大值没有路径

else prev[i]=v; //前驱为源点

}

dist[v]=0;s[v]=true;

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

{ int temp=MAX;

int u=v;

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

if((!s[j])&&(dist[j]<temp)) {u=j;temp=dist[j];}//不在集合里，值《temp，选最小值 s[u]=true;

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

{ if((!s[j])&&(c[u][j]<MAX))

{ int newdist=dist[u]+c[u][j];

if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}//前驱u记录下来 }

}

}

}

void PrintPath(int *prev,int n,int begin,int end)

{ int *path=new int [n+1];

int i,m=n;

bool k=true;

path[end]=end;

for(i=end-1;i>1;i--)

{ path[i]=prev[path[i+1]]; //构造路径

m--;

}

for (i=m;i<=end;i++) {

cout<<path[i]<<"->"; //输出路径

}

cout<<"\b\b"<<" "<<endl;

}

void main()

{ int n,i;

int v=1;

cout<<"请输入顶点个数：";

cin>>n;

int *dist=new int [n+1];

int *prev=new int [n+1];

int **c;

c=new int *[n+1];

for (i=0;i<=n;i++)

{ c[i]=new int [n+1]; }

getdata(c,n); //获取数据

int begin=1,end;

cout<<"请输入所求单源路径的 起点 终点：";

cin>>begin>>end;

v=begin;

Dijkstra(n,v,dist,prev,c); //计算路径

PrintPath(prev,n,begin,end); //输出路径

}

2. 最小生成树问题的程序代码如下：

#include"malloc.h"

#include"stdlib.h"

#include"stdio.h"

#include <io.h>

#include <windows.h>

#include <limits.h>

#define MAX_VERTEX_NUM 20 // 最大顶点个数

#define MAX_NAME 3 // 顶点字符串的最大长度+1

#define MAX_INFO 20 // 相关信息字符串的最大长度+1

#define INFINITY INT_MAX // 用整型最大值代替∞

typedef int VRType;

typedef char InfoType;

typedef char VertexType[MAX_NAME];

// 邻接矩阵的数据结构

typedef struct

{ VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；

// 对带权图，则为权值类型

InfoType *info; // 该弧相关信息的指针(可无)

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 图的数据结构

typedef struct

{ VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量

AdjMatrix arcs; // 邻接矩阵

int vexnum, // 图的当前顶点数

arcnum; // 图的当前弧数

} MGraph;

// 记录从顶点集U到V-U的代价最小的边的辅助数组定义

typedef struct

{ VertexType adjvex;

VRType lowcost;

}minside[MAX_VERTEX_NUM];

// 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。

int LocateVex(MGraph G,VertexType u)

{ int i;

for(i = 0; i < G.vexnum; ++i)

if( strcmp(u, G.vexs[i]) == 0)

return i;

return -1;

}

int CreateAN(MGraph *G)

{ int i,j,k,w,IncInfo;

char s[MAX_INFO],*info;

VertexType va,vb;

printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分) "); scanf("%d%d%d%*c",&(*G).vexnum,&(*G).arcnum,&IncInfo);

printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME); for(i=0;i<(*G).vexnum;++i) // 构造顶点向量

scanf("%s",(*G).vexs[i]);

for(i=0;i<(*G).vexnum;++i) // 初始化邻接矩阵

for(j=0;j<(*G).vexnum;++j)

{ (*G).arcs[i][j].adj=INFINITY; // 网初始化为无穷大

(*G).arcs[i][j].info=NULL;

}

printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum); for(k=0;k<(*G).arcnum;++k)

{ scanf("%s%s%d%*c",va,vb,&w); // %*c吃掉回车符

i=LocateVex(*G,va);

j=LocateVex(*G,vb);

(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; // 无向

if(IncInfo)

{ printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);

gets(s);

w=strlen(s);

if(w)

{ info=(char*)malloc((w+1)*sizeof(char));

strcpy(info,s);

(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; // 无向

}

}

}

return 1;

}

// 求closedge.lowcost的最小正值

int minimum(minside SZ,MGraph G)

{ int i=0,j,k,min;

while(!SZ[i].lowcost)

i++;

min=SZ[i].lowcost; // 第一个不为0的值

k=i;

for(j=i+1;j<G.vexnum;j++)

if(SZ[j].lowcost>0)

if(min>SZ[j].lowcost)

{ min=SZ[j].lowcost;

k=j;

}

return k;

}

// 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 void MiniSpanTree_PRIM(MGraph G,VertexType u)

{ int i,j,k;

minside closedge;

k=LocateVex(G,u);

for(j=0;j<G.vexnum;++j) // 辅助数组初始化

{ if(j!=k)

{ strcpy(closedge[j].adjvex,u);

closedge[j].lowcost=G.arcs[k][j].adj;

}

}

closedge[k].lowcost=0; // 初始,U={u}

printf("最小代价生成树的各条边为:\n");

for(i=1;i<G.vexnum;++i)

{ // 选择其余G.vexnum-1个顶点

k=minimum(closedge,G); // 求出T的下一个结点：第K顶点

printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); // 输出生成树的边 closedge[k].lowcost=0; // 第K顶点并入U集

for(j=0;j<G.vexnum;++j)

if(G.arcs[k][j].adj<closedge[j].lowcost)

{ // 新顶点并入U集后重新选择最小边

strcpy(closedge[j].adjvex,G.vexs[k]);

closedge[j].lowcost=G.arcs[k][j].adj;

}

}

}

int main()

{ MGraph G;

CreateAN(&G);

MiniSpanTree_PRIM(G,G.vexs[0]);

} system("pause"); return 0;

四．实验结果

（1）单源最短路径运行结果如下：

（2）最小生成树运行结果如下：

五．总结与思考