实验六图的应用

Input Edge Value：5

Input 7 the Edge i,j：4，5 Input Edge Value：3

Input 8 the Edge i,j：4，6 Input Edge Value：4

Input 9 the Edge i，j：5，6 Input Edge Valme：4 程序运行结果为：

（请记录） 4、结果分析与讨论

本例用普里姆算法根据输入的无向带权图的数据，输出组成最小生成树的边。根据这些边，可以画出最小生成树。最小生成树不是唯一的，输入的顺序不同，输出结果可能会不同。

5、思考与练习

若用邻接表作为图的存储结构创建图，完成求邻接表表示的图的最小生成树算法。

代码：

#include #include

#define VexNum 20 /*图的最多顶点个数*/ #define MAXINT 30000 /*极大值*/

typedef char VexType; /* 顶点数据类型 */ typedef int EdgeType; /* 边数据类型 */

typedef struct

{ VexType vexs[VexNum];

EdgeType arcs[VexNum][VexNum];

int vexnum,arcnum; /* 顶点数和边数 */ }Mgraph; /* 图的邻接矩阵表示结构定义 */

typedef struct

{int adjvex;/*集合U中的顶点(始点)*/

int value;/*集合u中顶点到非U中的某个顶点的最小距离值*/ }InterEdge;

void Min_SpanTree(Mgraph G,int u); Mgraph Create_MgraphN();

int MinValue(InterEdge ee[],int n); int main() {

Mgraph G;

G=Create_MgraphN( ); Min_SpanTree(G,0); }

Mgraph Create_MgraphN()

{ /* 创建无向带权图的邻接矩阵算法 */ int i,j,k;

EdgeType v; /* 边的权值 */ Mgraph G;

printf(\：\

scanf(\.vexnum); /*顶点个数*/ printf(\：\

scanf(\.arcnum); /*边条数*/

printf(\：\\n\ scanf(\ /*顶点字符表示符*/ for(i=0;i

for(k=1;k<=G.arcnum;k++) {

printf(\：\

scanf(\ /*输入对应边起点序号和终点序号*/ printf(\：\ getchar();

scanf(\ /*输入边的权值*/ G.arcs[i][j]=v;

G.arcs[j][i]=v; /*④⑤为无向图存储边权值*/ } while(i<1|| i>G.vexnum || j<1|| j>G.vexnum)

{ printf(\ }

return G; }

int MinValue(InterEdge ee[],int n) /*比较求最小距离值,并返回对应下标*/ {

int i,j,k;

for(j=0;j0) { k=j; break; } for(j=1;j0 && ee[j].value

void Min_SpanTree(Mgraph G,int u)

{/*最小至成树的普里姆算法,以u为起始点,求用邻接矩阵表示的图G的最小生成树,然后输出*/ InterEdge ee[VexNum]; int cc=0,pp[VexNum*2]; int k=0,i,j,s1,in; for(i=0;i

ee[j].value=G.arcs[k][j]; ee[j].adjvex=k; }

}

}

printf(\for(i=0;i<2*(G.vexnum-1);i=i+2) printf(\.vexs[pp[i]],G.vexs[pp[i+1]]);/*最小生成树组成边输出*/