急!(最小生成树问题)请教高手!!

发布网友发布时间：2022-05-29 07:47

共2个回答

热心网友时间：2023-10-11 14:59

例子：
最小生成树问题
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
答：
用邻接矩阵表示的图的prim算法的源程序
*/#include<stdio.h>
#define MAXVEX 6
typedef char VexType;
typedef float AdjType;
typedef struct {
int n; /* 图的顶点个数 */
/*VexType vexs[MAXVEX]; 顶点信息 */
AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */
} GraphMatrix;
typedef struct{
int start_vex, stop_vex; /* 边的起点和终点 */
AdjType weight; /* 边的权 */
} Edge;
Edge mst[5];
#define MAX 1e+8
void prim(GraphMatrix * pgraph, Edge mst[]) {
int i, j, min, vx, vy;
float weight, minweight; Edge edge;
for (i = 0; i < pgraph->n-1; i++) {
mst[i].start_vex = 0;
mst[i].stop_vex = i+1;
mst[i].weight = pgraph->arcs[0][i+1];
}
for (i = 0; i < pgraph->n-1; i++) { /* 共n-1条边 */
minweight = MAX; min = i;
for (j = i; j < pgraph->n-1; j++)/* 从所有边(vx,vy)(vx∈U,vy∈V-U)中选出最短的边 */
if(mst[j].weight < minweight) {
minweight = mst[j].weight;
min = j;
}
/* mst[min]是最短的边(vx,vy)(vx∈U, vy∈V-U)，将mst[min]加入最小生成树 */
edge = mst[min];
mst[min] = mst[i];
mst[i] = edge;
vx = mst[i].stop_vex; /* vx为刚加入最小生成树的顶点的下标 */

for(j = i+1; j < pgraph->n-1; j++) { /* 调整mst[i+1]到mst[n-1] */
vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];
if (weight < mst[j].weight) {
mst[j].weight = weight;
mst[j].start_vex = vx;
}
}
}
}
GraphMatrix graph = {
6,
,
,
,
,
,

}
};
int main(){
int i;
prim(&graph,mst);
for (i = 0; i < graph.n-1; i++)
printf("(%d %d %.0f)\n", mst[i].start_vex,
mst[i].stop_vex, mst[i].weight);
return 0;
}

热心网友时间：2023-10-11 15:00

快排快啊。。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct road
{
int st;
int ed;
int w;
};
road all[900];
int A[30];
int cmp(const void *a,const void *b)
{
return (*(road *)a).w - (*(road *)b).w;
}
int find(int x)
{
if (x != A[x])
A[x] = find(A[x]);
return A[x];
}
int main()
{
int i,j,k,q,p,m,n,sum;
char s,e;
while (scanf("%d",&n) != EOF)
{
if (n == 0) break;
memset(A,0,sizeof(int));
for (i = 1;i <= n;i++)
A[i] = i;
m = 0;
for (i = 1;i < n;i++)
{
scanf(" %c%d",&s,&p);
while (p--)
{
scanf(" %c%d",&e,&q);
all[m].st = s - 'A';
all[m].ed = e - 'A';
all[m].w = q;
m++;
}
}
qsort(all,m,sizeof(all[0]),cmp);
k = 0;sum = 0;
while (k < m)
{
all[k].st = find(all[k].st);
all[k].ed = find(all[k].ed);
if (all[k].st != all[k].ed)
{
sum += all[k].w;
A[all[k].st] = all[k].ed;
}
k++;
}
printf("%d\n",sum);
}
system("pause");
return 0;
}