1691: 图-最小生成树
金币值：2
定数：9
时间限制：1.000 s
内存限制：128 M
正确：2
提交：3
正确率：66.67% 命题人：
题目描述
已知一个加权连通图，输出该图最小生成树上的各边及其权重。要求存储结构使用邻接矩阵，算法使用普里姆算法，顶点从0开始编号，并且从编号为0的顶点开始构造最小生成树。
#include <stdio.h>
#define MAXVEX 100 // 最大顶点数由用户定义
#define INFINITY 65535
typedef char VertexType; // 顶点类型应由用户定义
typedef int EdgeType; // 边上的权值类型应由用户定义
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numNodes;
int numEdges;
} MGraph;
typedef struct {
int u;
int v;
int w;
} Edge;//定义边类型
void CreateMGraph(MGraph &G) {
int u, v, w, i, j;
for(i=0; i<G.numNodes; i++)
for(j=0; j<G.numNodes; j++) {
G.arc[i][j] = INFINITY;
}
for(i=1; i<=G.numEdges; i++) {
scanf("%d %d %d",&u,&v,&w);
G.arc[v] = w;
G.arc[v] = w;
}
}
void Output(Edge edges[],int n) {
for(int i=0; i<n; i++)
if (edges[i].u < edges[i].v) printf("%d %d %d\n",edges[i].u,edges[i].v, edges[i].w);
else printf("%d %d %d\n",edges[i].v,edges[i].u, edges[i].w);
}
int main(void) {
void MiniSpanTree_Prim(MGraph G, int v0, Edge edges[]);
MGraph G;
Edge edges[MAXVEX];
scanf("%d %d",&G.numNodes,&G.numEdges); // n表示图中顶点的个数，m表示图中边的个数
CreateMGraph(G); // 建立图的存储结构（邻接矩阵）
MiniSpanTree_Prim(G,0,edges); // 从编号为0的顶点开始应用普里姆算法构造最小生成树
Output(edges,G.numNodes-1); // 输出最小生成树中的所有边（共G.numNodes-1）条
return 0;
}
/*提交以下代码*/
void MiniSpanTree_Prim(MGraph G, int v0, Edge edges[]) { //使用Prim算法生成最小生成树
} 输入格式
第1行输入两个整数，分别表示图中的顶点数n和边数m。
第2-m+1行，每行输入3个整数，分别表示每条边上的两个顶点及其权重。
第2-m+1行，每行输入3个整数，分别表示每条边上的两个顶点及其权重。
输出格式
输出n-1行，每行3个整数，分别表示最小生成树上每条边上的两个顶点和权重（要求按照构造的先后顺序输出）
输入样例 复制
6 10
0 1 6
0 2 1
0 3 5
1 2 5
1 4 3
2 3 5
2 4 6
2 5 4
3 5 2
4 5 6输出样例 复制
0 2 1
2 5 4
3 5 2
1 2 5
1 4 3提示
主要步骤：
1 定义边表（有些教材中有lowcost数组和closet数组表示）
2 初始化边表
3 循环n-1次
3.1 查找权值最小的边
3.2 处理当前找到的边
3.3 更新边表
1 定义边表（有些教材中有lowcost数组和closet数组表示）
2 初始化边表
3 循环n-1次
3.1 查找权值最小的边
3.2 处理当前找到的边
3.3 更新边表
void MiniSpanTree_Prim(MGraph G, int v0, Edge edges[]) {
int i,j,k,min,count=0;
int lowcost[MAXVEX],closet[MAXVEX];
for(i=0; i<G.numNodes; i++) { //初始化边表
if (i!=v0) {
} else {
}
}
for(i=1; i<G.numNodes; i++) {
min=INFINITY;
for(j=0; j<G.numNodes; j++) //寻找具有权重最小的边
if () {
}
edges[count].u = ; //保存边
edges[count].v = ;
edges[count].w = ;
count++;
lowcost[k]=0; //更新边表
for(j=0; j<G.numNodes; j++) {
if() {
}
}
}
}