Question

数据结构中关于最小生成树的步骤

Answer 1

普里姆算法的基本思想:取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。
克鲁斯卡尔算法
克鲁斯卡尔算法的基本思想：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。
具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。

Answer 2

#include<stdio.h>
#include<stdlib.h>
#define INFINITY 100000//相当于无穷大
#define MAX_VERTEX_NUM 20//最多能有多少个点
//邻接矩阵图
typedef struct{
char vexs[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
}MGraph;
//保存路径起始点，终点，以及权值
typedef struct{
int adjvex;
int endvex;
int lowcost;
}closedge[MAX_VERTEX_NUM];
//创建邻接矩阵
void CreateUDN(MGraph &G);
//找到输入字符对应的数字
int LocateVex(MGraph G,char v);
//输出邻接矩阵图
void PrintUDN(MGraph G);
//找出最小生成树
void MiniSpanTree_PRIM(MGraph G,closedge &minedge);
//输出最小生成树的每条边的起点，终点和权值
void PrintMinEdge(MGraph G,closedge minedge);
int main()
{
MGraph G;
closedge minedge;
CreateUDN(G);
printf("该图的邻接矩阵存储示意图如下：\n");
PrintUDN(G);
printf("\n");
MiniSpanTree_PRIM(G,minedge);
printf("该图生成树的边如下：\n");
PrintMinEdge(G,minedge);
printf("\n");
return 0;
}
//创建邻接矩阵
void CreateUDN(MGraph &G)
{
int i,j;
char vex1,vex2;//起点，终点字符
int vex1Index,vex2Index;//字符对应的数字
int weight;
char ch;
printf("请输入有多少个顶点，多少条边：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入顶点向量：\n");
scanf("%s",G.vexs);
//初始化都为0
for(i=0;i<G.arcnum;i++)
for(j=0;j<G.arcnum;j++)
G.arcs[i][j]=0;
//输入并赋值有路径的
printf("请输入所有边的起点，终点和权值：\n");
for(i=0;i<G.arcnum;i++)
{
while((ch=getchar())!='\n'); //吸收换行符
scanf("%c%c",&vex1,&vex2);
scanf("%d",&weight);
vex1Index=LocateVex(G,vex1);
vex2Index=LocateVex(G,vex2);
G.arcs[vex1Index][vex2Index]=G.arcs[vex2Index][vex1Index]=weight;
}
//剩下没路径的（当然不包括自己到自己）赋值无穷大
for(i=0;i<G.arcnum;i++)
{
for(j=0;j<G.arcnum;j++)
if(G.arcs[i][j]==0&&i!=j)
{
G.arcs[i][j]=INFINITY;
}
}
}
//将输入的字符转换成对应的数字（A-0，B-1，...）
int LocateVex(MGraph G,char v)
{
int i;
for(i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
return i;
}
//输出对应矩阵
void PrintUDN(MGraph G)
{
int i,j;
for(i=0;i<=G.vexnum;i++)
{
for(j=0;j<=G.vexnum;j++)
{
if(i==0&&j==0)
printf("\t");
else if(i==0)
{
printf("%c\t",G.vexs[j-1]);
}
else if(j==0)
{
printf("%c\t",G.vexs[i-1]);
}
else
{
if(G.arcs[i-1][j-1]==INFINITY)
printf("∞\t");
else
printf("%d\t",G.arcs[i-1][j-1]);
}
}
printf("\n");
}
}
//生成最小生成树（实则就是记录最小路径的起点，终点，权值）
void MiniSpanTree_PRIM(MGraph G,closedge &minedge)
{
int i,j,k,z;
int temp;
int currentmin;
//起始初始化
k=0;
for(j=1;j<G.vexnum;++j)
{
minedge[j-1].adjvex=k;
minedge[j-1].endvex=j;
minedge[j-1].lowcost=G.arcs[k][j];
}
//找最小路径
for(i=0;i<G.vexnum-1;++i)
{
//找第一个路径最短的可达点
currentmin=minedge[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum-1;j++)
{
if(minedge[j].lowcost<currentmin)
{
currentmin=minedge[j].lowcost;
k=j;
}
}
//做相应操作
{
temp=minedge[i].adjvex;
minedge[i].adjvex=minedge[k].adjvex;
minedge[k].adjvex=temp;
temp=minedge[i].endvex;
minedge[i].endvex=minedge[k].endvex;
minedge[k].endvex=temp;
temp=minedge[i].lowcost;
minedge[i].lowcost=minedge[k].lowcost;
minedge[k].lowcost=temp;
}
//依次找后面的可达最小路径
for(j=i+1;j<G.vexnum-1;++j)
{
z=minedge[i].endvex;
k=minedge[j].endvex;
if(k!=z)
{
if(G.arcs[z][k]<minedge[j].lowcost)
{
minedge[j].adjvex=z;
minedge[j].lowcost=G.arcs[z][k];
}
}
}
}
}
//输出最小生成树
void PrintMinEdge(MGraph G,closedge minedge)
{
int i;
for(i=0;i<G.vexnum-1;i++)
printf("%c%c\t%d\n",G.vexs[minedge[i].adjvex],G.vexs[minedge[i].endvex],minedge[i].lowcost);
}

Answer 3

比较典型的是Prim算法和Kruskal算法。

Answer 4

jrj