湖北工业大学计算机学院
《算法设计技巧与分析》课程实验报告
实验名称姓
名
贪心算法的运用
系院专业
指导教师
班
级
实验序号学成
号绩
实验日期一、实验目的
1. 掌握贪心算法的基本概念和两个基本要素2. 熟练掌握贪心算法解决问题的基本步骤3. 学会利用贪心算法解决实际问题二、实验内容与要求1，实现贪心算法的经典运用2，实现贪心算法的经典运用三、实验设备地点：科技楼硬件环境：软件环境：五、实验步骤
1.用Kruskal算法实现最小生成树算法描述：假设
WN=(V,{E})
是一个含有
n 个顶点的连通网，则按照克鲁斯卡尔算法构n 个顶点，而边集为空的子图，若将该子图中
n 棵树的一个森林。之后，从网的
则将其加入子图，
若该条边的两个顶点分属不同的树，
网络实验室602
------- Kruskal算法（最小生成树）-------Prim算法（最小生成树）
Intel Pentium Processor 1.8G ，512M内存，windows 操作系统VC++6.0
造最小生成树的过程为：先构造一个只含边集
E 中选取一条权值最小的边，
各个顶点看成是各棵树上的根结点，则它是一个含有
也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有
n-1条边为止。
湖北工业大学
下面给出c语言代码实现及说明
本程序对树的存储主要是以边为存储对象，边的一个顶点。3，边的另一个顶点。算法中给出。
在Kruskal算法中有两个比较重要的部分
计算机学院
即边的结构体里面有这样几个参数：1，边的权值。2，
。Prim
4，边是否属于生成树的一条边（即最小生成树边标志）
至于边稠密的情况会在下面的
由该程序的存储结构决定了该算法比较适用于边稀疏的情形，
1，对边按权重排序。2，对一条边加入子树后是否会产
生回路的判断即判断边的两个节点是否在同一个树中（集合里）
对于问题1：可以有各种排序算法，读者可以自行选择自己喜欢的排序算法来替换代码中的排序算法。（本处使用选择排序算法（效率较低）下面主要讲解解决问题
，读者可以自己修改为快速排序或者是对排序）
2，解决这个问题一般借用不相交集的思想，即在本程序中每次以同集合
（对于根节点即标号最小的节点则标记为
0）例如对于
中所有点的编号最小的数来标识本集合。
上图实例，下面给出详细的不相交集的维护过程（给出前几步的详细说明）a,初始状态（ABCDEFG分别在数组的第0 0
A 0
B 0
C 0
1，2，3，4，5，6，7）0号位空置（均为
D 0
E 0
F 0
0）
G 0
b,选择第一条边0 0
A 0
A---D(将D的标记改为1)（因为AD最短）
B 0
C 0
D 1
E 0
F 0
G 0
对表进行维护（维护后仍同上表，因为还没有两个集合合并）0 0
A 0
B 0
C----E（修改上表）
B 0
C 0
D 1
E 3
F 0
G 0
C 0
D 1
E 0
F 0
G 0
C，选择第二条边0 0
A 0
对上表进行维护（任同上表，因为还没有两个集合合并）0 0
A 0
B 0
C 0
D 1
E 3
)
6>1
F 0
G 0
D，选择第三条边（D-----F）(根据条件DF两点不再同一集合，改边可选
然后就合并DF两点所在的集合所以表修改如下0 0
A 0
B 0
D的前去是1，即A标记为0，E的标记也为0，合并因为
C 0
D 1
E 3
F 1
G 0
湖北工业大学计算机学院
以后几步均如上判断两点是否在一个集合从而判断改边是否可取，并维护上表下面附上源代码
/**************************************************************************************************
Kruskal算法的实现09网一
殷赛
0910322113
输入：图G(用结构体数组来存储每条边，包含每条边的节点）输出：图G的最小生成树树
***************************************************************************************************/ #include #include 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
min=i;
for(j=i+1;j
if(array[min].weight>array[j].weight)
min=j;
if(min!=i) {
temp=array[i].weight;
湖北工业大学
array[i].weight=array[min].weight; 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; }
Edge *Kruskal(Edge *Graph,int num_e,int **V{
int m,n,test; int i,j,t,k;
,int num_v)//克鲁斯卡尔算法实现
for(i=0;i
for(j=1;j
if(Graph[i].dot_1==V[0][j])
m=j;
if(Graph[i].dot_2==V[0][j])
n=j;
}
if(V[1][m]!=V[1][n]&&m!=V[1][n]&&n!=V[1][m])//如果边的两个顶点不再一个集合则
)
边是生成树的边(注意首节点的标记和集合里非首节点的标记不同
Graph[i].leap=1;
if(V[1][n]==0) {
if(n
V[1][V[1][m]]=n; else
V[1][n]=V[1][m];
} else {
if(V[1][m]==0) {
if(m
V[1][V[1][n]]=m; else
V[1][m]=V[1][n];
} else {
if(V[1][m]>V[1][n])
V[1][V[1][m]]=V[1][n]; else
V[1][V[1][n]]=V[1][m];
} }
//维护不相交集
k=1;//对每个节点都检查是否为标记合格节点while(k
if(V[1][k]!=0)//
只要标记不为
0都进行整理,只不过有些节点的标记整理前后是
{
即标记符合标准的节点
)
{
t=V[1][k]; while(V[1][t]!=0) {
t=V[1][t]; } V[1][k]=t; } k++; } }
if(V[1][m]==0&&V[1][n]==0)//{
Graph[i].leap=1;
if(m>n)
V[1][m]=n; else
V[1][n]=m; //维护不相交集k=1;
while(k
if(V[1][k]!=0) {
t=V[1][k]; while(V[1][t]!=0) {
t=V[1][t]; } V[1][k]=t;
如果边的两个顶点是两个集合的首节点则可以合并
一样的(
} k++; } }
/*
printf("不相交集的情况：
\n");
for(test=1;test
printf("%-4c",V[0][test]); printf("\n");
for(test=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
V[i]=(int*)malloc(sizeof(int)*(num_v+1)); for(i=0;i
for(j=0;j
V[i][j]=0;
for(i=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
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=selectionsort(Graph,num_e); //以上部分是存储图
//--------------------------------------------------------------------------------------------------
Graph=Kruskal(Graph,num_e,V,num_v); printf("构成最小生成树的边和顶点分别是：
\n");
printf("顶点1------------顶点2-------------边\n"); for(i=0;i
if(Graph[i].leap==1) {
printf("
%c
------------
-------------
%d\n",Graph[i].dot_1,Graph[i].dot_2,Graph[i].weight); cost=cost+Graph[i].weight;
} }
printf("最小生成树的权值是：%d\n",cost);
}
%c
2.用Prim算法实现最小生成树
算法描述：假设V是图中顶点的集合法通过以下步骤可以得到最小生成树
1:初始化:U={u 0},TE={f}小生成树的初始形态并将此边的非
,E是图中边的集合,TE为最小生成树中的边的集合:
u 0的结点集U和一个空的边集
,则prim算TE作为最TE中，
:
。此步骤设立一个只有结点
,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。
2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边
U中顶点加入U中。此步骤的功能是在边集
U中的那个顶点加入到
首先边的两个顶点要分别在顶点集合到边集TE中,并把这条边上不在点在理解算法时要密切注意。
(u 0,v 0)，将此边加进集合
E中找一条边,要求这条边满足以下条件U中。这一步骤在算法中应执行多次
,每执行
U和V－U中,其次边的权要最小。找到这条边以后,把这条边放
,因此,TE和U是两个动态的集合
,这一
一次,集合TE和U都将发生变化,分别增加一条边和一个顶点
我们可以算出当
U=V
3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。时,步骤2共执行了n－1次(设n为图中顶点的数目求出的最小生成树的边（图任如上图）下面给出具体
c语言代码和详解
),TE中也增加了n－1条边,这n－1条边就是需要
该代码的存储结构是邻接矩阵上三角用来存储最小生成树的边，原图，方便输出最小生成树上图的最后邻接矩阵如下：即不相邻)
0 7 INF 5 INF INF INF
-1 0 8 9 7 INF INF
INF INF 0 INF 5 INF INF
-1 INF INF 0 15 6 INF
INF -1 -1 INF 0 8 9
INF INF INF -1 INF 0 11
树边用-1标记，下三角用来存储
(INF代表无穷，
（具体实现和解释见代码）
INF INF INF INF -1 INF 0
/*********************************************************************************
09网一
殷赛
0910322113
Prim算法的实现
输入：图G
输出：图G的最小生成树
**********************************************************************************/ #include #include #define INF 32767
/*************************************************************************************
Prim算法最重要的部分在于从可以挑选的边中间挑选出最小值
并且对加入后会产生回路的边标记为不可选（此代码中将该边权值标记为每选中一条边就会加入一个点
（就必须对与该点连接的边进行维护，
INF即无穷大）
即多产生回路边标记为无穷）
找最小边则是从上三角中所有可选的行和列中选择选中的树边则标记为
-1（其权值从下三角读出）
湖北工业大学计算机学院
***********************************************************************************
***/
void Prim(int **Graph,int num_v)//转化为对上三角的维护
{
int i,j,leap=0,temp;
int m,n,min;
int *a=(int *)malloc(sizeof(int)*num_v);
for(i=0;i
a[i]=0;
a[0]=1;
while(leap!=num_v-1)
{
min=INF;
for(i=0;i
{
if(a[i]==1)
{
for(j=i+1;j
{
if(min>Graph[i][j]&&Graph[i][j]>0)
{
min=Graph[i][j];
m=j;
n=i;
temp=0;
}
}
for(j=0;j
{
if(min>Graph[j][i]&&Graph[j][i]>0)
{
min=Graph[j][i];
m=j;
n=i;
temp=1;
}
}
}
} if(temp==0)//为了区别出是在行还是在列中搜索到的元素
Graph[n][m]=-1;
else
Graph[m][n]=-1;
for(i=0;i
{
if(a[i]==1&&Graph[i][m]>0)
{
Graph[i][m]=INF;
}
}
for(i=m+1;i
{
if(a[i]==1&&Graph[m][i]>0)
{
Graph[m][i]=INF;
}
}
a[m]=1; 去掉列中回路边
/* for(i=0;i
printf("%-4d",a[i]);
printf("\n");*/
/* for(i=0;i
{
for(j=0;j
printf("%-4d\t",Graph[i][j]);
printf("\n");
}*/
leap++;
}
}
void main()
{
int i,j;
int num_v,num_e;
int **Graph=NULL;
char *V=NULL;
char ch_1,ch_2;
int weight;
int m,n;
printf("请输入图的顶点数：");
scanf("%d",&num_v);
V=(char*)malloc(sizeof(char)*num_v);
Graph=(int**)malloc(sizeof(int*)*num_v);//动态生成二维数组用来存储图（邻接矩阵）for(i=0;i
Graph[i]=(int*)malloc(sizeof(int)*num_v);
for(i=0;i
for(j=0;j
Graph[i][j]=INF;
for(i=0;i
Graph[i][i]=0;
for(i=0;i
{
printf("请输入第%d个顶点:",i+1);
scanf(" %c",&V[i]);
}
printf("请输入图的边数：");
scanf("%d",&num_e);
for(i=0;i
{
printf("请输入第%d条边的顶点和权值:",i+1);
scanf(" %c %c%d",&ch_1,&ch_2,&weight);
for(j=0;j
{
if(V[j]==ch_1)
m=j;
if(V[j]==ch_2)
n=j;
}
Graph[m][n]=weight;
Graph[n][m]=weight;
}
//以上是对图用邻接矩阵存储
//------------------------------------------------------------------------------------
Prim(Graph,num_v);
printf("最小生成树如下：\n");
printf("顶点----------------顶点-----------------权值\n");
weight=0;
for(i=0;i
for(j=i+1;j
{
if(Graph[i][j]==-1)
{
printf(" %-2c ---------------- %-2c ----------------- %-2d\n",V[i],V[j],Graph[j][i]); weight=weight+Graph[j][i];
}
}
printf("最小生成树的权重是：
} %d\n",weight);
六、实验结果与分析
Kruskal算法适用于边稀疏的情形，而Prim算法适用于边稠密的情形
湖北工业大学计算机学院
《算法设计技巧与分析》课程实验报告
实验名称姓
名
贪心算法的运用
系院专业
指导教师
班
级
实验序号学成
号绩
实验日期一、实验目的
1. 掌握贪心算法的基本概念和两个基本要素2. 熟练掌握贪心算法解决问题的基本步骤3. 学会利用贪心算法解决实际问题二、实验内容与要求1，实现贪心算法的经典运用2，实现贪心算法的经典运用三、实验设备地点：科技楼硬件环境：软件环境：五、实验步骤
1.用Kruskal算法实现最小生成树算法描述：假设
WN=(V,{E})
是一个含有
n 个顶点的连通网，则按照克鲁斯卡尔算法构n 个顶点，而边集为空的子图，若将该子图中
n 棵树的一个森林。之后，从网的
则将其加入子图，
若该条边的两个顶点分属不同的树，
网络实验室602
------- Kruskal算法（最小生成树）-------Prim算法（最小生成树）
Intel Pentium Processor 1.8G ，512M内存，windows 操作系统VC++6.0
造最小生成树的过程为：先构造一个只含边集
E 中选取一条权值最小的边，
各个顶点看成是各棵树上的根结点，则它是一个含有
也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有
n-1条边为止。
湖北工业大学
下面给出c语言代码实现及说明
本程序对树的存储主要是以边为存储对象，边的一个顶点。3，边的另一个顶点。算法中给出。
在Kruskal算法中有两个比较重要的部分
计算机学院
即边的结构体里面有这样几个参数：1，边的权值。2，
。Prim
4，边是否属于生成树的一条边（即最小生成树边标志）
至于边稠密的情况会在下面的
由该程序的存储结构决定了该算法比较适用于边稀疏的情形，
1，对边按权重排序。2，对一条边加入子树后是否会产
生回路的判断即判断边的两个节点是否在同一个树中（集合里）
对于问题1：可以有各种排序算法，读者可以自行选择自己喜欢的排序算法来替换代码中的排序算法。（本处使用选择排序算法（效率较低）下面主要讲解解决问题
，读者可以自己修改为快速排序或者是对排序）
2，解决这个问题一般借用不相交集的思想，即在本程序中每次以同集合
（对于根节点即标号最小的节点则标记为
0）例如对于
中所有点的编号最小的数来标识本集合。
上图实例，下面给出详细的不相交集的维护过程（给出前几步的详细说明）a,初始状态（ABCDEFG分别在数组的第0 0
A 0
B 0
C 0
1，2，3，4，5，6，7）0号位空置（均为
D 0
E 0
F 0
0）
G 0
b,选择第一条边0 0
A 0
A---D(将D的标记改为1)（因为AD最短）
B 0
C 0
D 1
E 0
F 0
G 0
对表进行维护（维护后仍同上表，因为还没有两个集合合并）0 0
A 0
B 0
C----E（修改上表）
B 0
C 0
D 1
E 3
F 0
G 0
C 0
D 1
E 0
F 0
G 0
C，选择第二条边0 0
A 0
对上表进行维护（任同上表，因为还没有两个集合合并）0 0
A 0
B 0
C 0
D 1
E 3
)
6>1
F 0
G 0
D，选择第三条边（D-----F）(根据条件DF两点不再同一集合，改边可选
然后就合并DF两点所在的集合所以表修改如下0 0
A 0
B 0
D的前去是1，即A标记为0，E的标记也为0，合并因为
C 0
D 1
E 3
F 1
G 0
湖北工业大学计算机学院
以后几步均如上判断两点是否在一个集合从而判断改边是否可取，并维护上表下面附上源代码
/**************************************************************************************************
Kruskal算法的实现09网一
殷赛
0910322113
输入：图G(用结构体数组来存储每条边，包含每条边的节点）输出：图G的最小生成树树
***************************************************************************************************/ #include #include 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
min=i;
for(j=i+1;j
if(array[min].weight>array[j].weight)
min=j;
if(min!=i) {
temp=array[i].weight;
湖北工业大学
array[i].weight=array[min].weight; 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; }
Edge *Kruskal(Edge *Graph,int num_e,int **V{
int m,n,test; int i,j,t,k;
,int num_v)//克鲁斯卡尔算法实现
for(i=0;i
for(j=1;j
if(Graph[i].dot_1==V[0][j])
m=j;
if(Graph[i].dot_2==V[0][j])
n=j;
}
if(V[1][m]!=V[1][n]&&m!=V[1][n]&&n!=V[1][m])//如果边的两个顶点不再一个集合则
)
边是生成树的边(注意首节点的标记和集合里非首节点的标记不同
Graph[i].leap=1;
if(V[1][n]==0) {
if(n
V[1][V[1][m]]=n; else
V[1][n]=V[1][m];
} else {
if(V[1][m]==0) {
if(m
V[1][V[1][n]]=m; else
V[1][m]=V[1][n];
} else {
if(V[1][m]>V[1][n])
V[1][V[1][m]]=V[1][n]; else
V[1][V[1][n]]=V[1][m];
} }
//维护不相交集
k=1;//对每个节点都检查是否为标记合格节点while(k
if(V[1][k]!=0)//
只要标记不为
0都进行整理,只不过有些节点的标记整理前后是
{
即标记符合标准的节点
)
{
t=V[1][k]; while(V[1][t]!=0) {
t=V[1][t]; } V[1][k]=t; } k++; } }
if(V[1][m]==0&&V[1][n]==0)//{
Graph[i].leap=1;
if(m>n)
V[1][m]=n; else
V[1][n]=m; //维护不相交集k=1;
while(k
if(V[1][k]!=0) {
t=V[1][k]; while(V[1][t]!=0) {
t=V[1][t]; } V[1][k]=t;
如果边的两个顶点是两个集合的首节点则可以合并
一样的(
} k++; } }
/*
printf("不相交集的情况：
\n");
for(test=1;test
printf("%-4c",V[0][test]); printf("\n");
for(test=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
V[i]=(int*)malloc(sizeof(int)*(num_v+1)); for(i=0;i
for(j=0;j
V[i][j]=0;
for(i=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
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=selectionsort(Graph,num_e); //以上部分是存储图
//--------------------------------------------------------------------------------------------------
Graph=Kruskal(Graph,num_e,V,num_v); printf("构成最小生成树的边和顶点分别是：
\n");
printf("顶点1------------顶点2-------------边\n"); for(i=0;i
if(Graph[i].leap==1) {
printf("
%c
------------
-------------
%d\n",Graph[i].dot_1,Graph[i].dot_2,Graph[i].weight); cost=cost+Graph[i].weight;
} }
printf("最小生成树的权值是：%d\n",cost);
}
%c
2.用Prim算法实现最小生成树
算法描述：假设V是图中顶点的集合法通过以下步骤可以得到最小生成树
1:初始化:U={u 0},TE={f}小生成树的初始形态并将此边的非
,E是图中边的集合,TE为最小生成树中的边的集合:
u 0的结点集U和一个空的边集
,则prim算TE作为最TE中，
:
。此步骤设立一个只有结点
,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。
2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边
U中顶点加入U中。此步骤的功能是在边集
U中的那个顶点加入到
首先边的两个顶点要分别在顶点集合到边集TE中,并把这条边上不在点在理解算法时要密切注意。
(u 0,v 0)，将此边加进集合
E中找一条边,要求这条边满足以下条件U中。这一步骤在算法中应执行多次
,每执行
U和V－U中,其次边的权要最小。找到这条边以后,把这条边放
,因此,TE和U是两个动态的集合
,这一
一次,集合TE和U都将发生变化,分别增加一条边和一个顶点
我们可以算出当
U=V
3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。时,步骤2共执行了n－1次(设n为图中顶点的数目求出的最小生成树的边（图任如上图）下面给出具体
c语言代码和详解
),TE中也增加了n－1条边,这n－1条边就是需要
该代码的存储结构是邻接矩阵上三角用来存储最小生成树的边，原图，方便输出最小生成树上图的最后邻接矩阵如下：即不相邻)
0 7 INF 5 INF INF INF
-1 0 8 9 7 INF INF
INF INF 0 INF 5 INF INF
-1 INF INF 0 15 6 INF
INF -1 -1 INF 0 8 9
INF INF INF -1 INF 0 11
树边用-1标记，下三角用来存储
(INF代表无穷，
（具体实现和解释见代码）
INF INF INF INF -1 INF 0
/*********************************************************************************
09网一
殷赛
0910322113
Prim算法的实现
输入：图G
输出：图G的最小生成树
**********************************************************************************/ #include #include #define INF 32767
/*************************************************************************************
Prim算法最重要的部分在于从可以挑选的边中间挑选出最小值
并且对加入后会产生回路的边标记为不可选（此代码中将该边权值标记为每选中一条边就会加入一个点
（就必须对与该点连接的边进行维护，
INF即无穷大）
即多产生回路边标记为无穷）
找最小边则是从上三角中所有可选的行和列中选择选中的树边则标记为
-1（其权值从下三角读出）
湖北工业大学计算机学院
***********************************************************************************
***/
void Prim(int **Graph,int num_v)//转化为对上三角的维护
{
int i,j,leap=0,temp;
int m,n,min;
int *a=(int *)malloc(sizeof(int)*num_v);
for(i=0;i
a[i]=0;
a[0]=1;
while(leap!=num_v-1)
{
min=INF;
for(i=0;i
{
if(a[i]==1)
{
for(j=i+1;j
{
if(min>Graph[i][j]&&Graph[i][j]>0)
{
min=Graph[i][j];
m=j;
n=i;
temp=0;
}
}
for(j=0;j
{
if(min>Graph[j][i]&&Graph[j][i]>0)
{
min=Graph[j][i];
m=j;
n=i;
temp=1;
}
}
}
} if(temp==0)//为了区别出是在行还是在列中搜索到的元素
Graph[n][m]=-1;
else
Graph[m][n]=-1;
for(i=0;i
{
if(a[i]==1&&Graph[i][m]>0)
{
Graph[i][m]=INF;
}
}
for(i=m+1;i
{
if(a[i]==1&&Graph[m][i]>0)
{
Graph[m][i]=INF;
}
}
a[m]=1; 去掉列中回路边
/* for(i=0;i
printf("%-4d",a[i]);
printf("\n");*/
/* for(i=0;i
{
for(j=0;j
printf("%-4d\t",Graph[i][j]);
printf("\n");
}*/
leap++;
}
}
void main()
{
int i,j;
int num_v,num_e;
int **Graph=NULL;
char *V=NULL;
char ch_1,ch_2;
int weight;
int m,n;
printf("请输入图的顶点数：");
scanf("%d",&num_v);
V=(char*)malloc(sizeof(char)*num_v);
Graph=(int**)malloc(sizeof(int*)*num_v);//动态生成二维数组用来存储图（邻接矩阵）for(i=0;i
Graph[i]=(int*)malloc(sizeof(int)*num_v);
for(i=0;i
for(j=0;j
Graph[i][j]=INF;
for(i=0;i
Graph[i][i]=0;
for(i=0;i
{
printf("请输入第%d个顶点:",i+1);
scanf(" %c",&V[i]);
}
printf("请输入图的边数：");
scanf("%d",&num_e);
for(i=0;i
{
printf("请输入第%d条边的顶点和权值:",i+1);
scanf(" %c %c%d",&ch_1,&ch_2,&weight);
for(j=0;j
{
if(V[j]==ch_1)
m=j;
if(V[j]==ch_2)
n=j;
}
Graph[m][n]=weight;
Graph[n][m]=weight;
}
//以上是对图用邻接矩阵存储
//------------------------------------------------------------------------------------
Prim(Graph,num_v);
printf("最小生成树如下：\n");
printf("顶点----------------顶点-----------------权值\n");
weight=0;
for(i=0;i
for(j=i+1;j
{
if(Graph[i][j]==-1)
{
printf(" %-2c ---------------- %-2c ----------------- %-2d\n",V[i],V[j],Graph[j][i]); weight=weight+Graph[j][i];
}
}
printf("最小生成树的权重是：
} %d\n",weight);
六、实验结果与分析
Kruskal算法适用于边稀疏的情形，而Prim算法适用于边稠密的情形