数据结构最小生成树问题

Question

【最小生成树算法实例】
现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？
【输入】 第一行两个数v(v<=200),e，分别代表城市数和边数 以下e行，每行为两个顶点和它们之间的边权w(w<1000)。
【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。
【输入样例】
6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33

【输出样例】
1 2 10
2 3 5
2 4 6
2 6 11
4 5 18

求此题的代码，要求用C编写的

哪位大哥帮下忙额

Answer 1

#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 2

6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33

1 2 10
2 3 5
2 4 6
2 6 11
4 5 18本回答被网友采纳