2017太原理工大学软件课程设计

【总结】

这个实验要熟悉线性表的各个操作，才能做出来完整的程序。

题目四 构造可以使n 个城市连接的最

小生成树

【问题描述】

给定一个地区的n 个城市间的距离网，用Prim 算法或Kruskal 算法建立最小生成树，并计算

得到的最小生成树的代价。

【设计及分析】

1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义， 若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。

2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成

树的代价。

3、表示城市间距离网的邻接矩阵（要求至少6 个城市，10 条边）。

【设计功能的实现】

#include\ #include<> #include<>

#include using namespace std;

#define MaxVextexNum 30 /* 最大顶点数为30 */ /*#define INFINITY 1000 定义一个权值的最大值 */ typedef struct{

int vexs[MaxVextexNum]; /* 顶点表 */

int arcs[MaxVextexNum][MaxVextexNum]; /* 邻接矩阵，即边表 */ int n; /* 顶点数和边数 */

}MGraph; /* MGragh是以邻接矩阵存储的图类型 */ typedef struct{

int adjvertex; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */ int lowcost; /* 某顶点与已构造好的部分生成树的顶点之 间的最小权值 */

}ClosEdge[MaxVextexNum]; /* 用prim算法求最小生成树时的辅助数组 */ void CreatGraph(MGraph *G) /* 建立有向图G的邻接矩阵存储 */ {

printf(\请输入顶点数n :\);

scanf(\, &(G->n));/* 输入顶点数和边数 */ printf(\请输顶点字符信息(共%d个)：\, G->n); for (i = 0; in; i++) {

scanf(\, &(G->vexs[i])); /* 输入顶点信息，建立顶点表 */ int i, j;

}

}

printf(\请输入邻接矩阵，不存在则输入1000\\n\); for (i = 0; i < G->n; i++) { }

printf(\此连邻接矩阵为（1000为不存在）：\\n\); for (i = 0; in; i++) { }

for (j = 0; jn; j++)

printf(\, G->arcs[i][j]); printf(\);

for (j = 0; j < G->n; j++) { }

cin >> G->arcs[i][j];

void PRIM(MGraph G, int u, ClosEdge closedge)

{/* 从第u个顶点出发构造图G的最小生成树，最小生成树顶点信息存放在数组closedge中*/

int i, j, w, k, cost = 0;

for (i = 0; i<; i++) /* 辅助数组初始化 */ if (i != u) { }

closedge[u].lowcost = 0; /* 初始，U={u} */ for (i = 0; i< - 1; i++) /* 选择其余的个顶点 */ { }

w = 1000;

for (j = 0; j<; j++) /* 在辅助数组closedge中选择权值最小的顶点*/ if (closedge[j].lowcost != 0 && closedge[j].lowcost

w = closedge[j].lowcost; k = j;

closedge[i].adjvertex = u; closedge[i].lowcost = [u][i];

} /* 求出生成树的下一个顶点k */

closedge[k].lowcost = 0; /* 第k顶点并入U集 */ for (j = 0; j<; j++) /* 新顶点并入U后，修改辅助数组*/ if [k][j]

closedge[j].adjvertex = k; closedge[j].lowcost = [k][j];

}

printf(\最小生成树中包括的城市间的道路:\\n\); for (i = 0; i<; i++) /*打印最小生成树的各条边*/ if (i != u) { }

printf(\最小生成树的代价为:%d\\n\\n\, cost);

printf(\, i, closedge[i].adjvertex, [i][closedge[i].adjvertex]); cost = cost + [i][closedge[i].adjvertex];

int main() { }

int t; MGraph G;

ClosEdge closedge; CreatGraph(&G);

printf(\请输入起始点：\); scanf(\, &t); PRIM(G, t, closedge); return 1;

【测试及运行结果】

【总结】

这个实验必须把普利姆算法搞懂，将思路理清晰，才能让程序完

整的被写出来。