哈工大数据结构大作业——最小生成树.doc

一、 问题描述1. 用户手动输入带全图（10 个结点） ；2. 通过 Prim 算法输出对应的最小生成树二、 方法思路1. 关于存储带权图我采用 10*10 的数组存储[i,j]表示第 i 行 j 列的元素，存储结点 i 和 j 之间的权值；显然，[i,j]=[j,i]对于两结点之间不直接相连的情况，用 100 这个较大权值表示对于数组中，[i,i]的情况，也用 100 表示，因为结点自身到自身的权值不做考虑2. 关于 Prim 算法引入集合 U U 和 T TU U 存放生成树的顶点，T T 存放生成树的边集初值 U={1}U={1}，T=ØT=Ø选择有最小权的边( ( u,u, v)v)，u u∈U,U, v v∈(V-U),(V-U),将 v v 加入 U,U,（u,vu,v）加入 T T重复这一过程，直到 U=VU=V voidvoid Prim(Prim( G,G, T T ) ){ { T T = = Ø;Ø;U U = = { { 1 1 };};whilewhile ( ( (V(V ––U)U) !=!= Ø)Ø) { {设( ( u,u, v v ) ) 是使 u u∈U U 与 v v∈(V-U)(V-U)且权最小的边；T T = = T T∪{ { ( ( u,u, v v ) ) } } ; ;U U = = U U ∪ { { v v };};} }} }3. 形象表示三、主要数据结构及源程序代码及其注释静态数组：数二维组 C 用来存储带权图；用一维数组 U 存储 10 个结点的最小生成树排序结果；用一维数组 M 存储第2-10 个结点；用一维数组 W 存储 M 中的结点到 U 中结点的最小权值。

include “stdafx.h“#include#define n 10//结点数目int main(){int C[n+1][n+1];//存储带权图int e=45;//边数int i,j,m,a;int w;int U[n+1];//存储结点的最小生成树排序int M[n];//存储-10结点int W[n];//存储M中到U中的最小权值int min;int k;int t;for (i=0;i<=n;i++)//结点自身到自身的权值附{for (j=0;j<=n;j++){if(i=j){C[i][i]=100;}}}for(i=0;i<=n;i++)//第行不使用C[0][i]=C[i][0]=100;for(m=1;m<=e;m++)//存储带权图{printf(“Input Vertex,Vertex,weight(如果两点不直接相连，输入权值；形式（节点一，节点二，权值）):\n“);scanf(“%d,%d,%d“,getchar();C[i][j]=w;C[j][i]=w;}U[1]=1;for(i=1;i<=n-1;i++)//Prim算法实现M[i]=i+1;for(i=1;i<=n-1;i++){W[i]=C[1][i+1];}for(i=1;i<=n-1;i++){min=W[1];k=1;t=1;while(min==50)//防止最小权值选成已放入U中的结点{min=W[t+1];k=t+1;t++;}for(j=2;j<=n-1;j++)//选择权值最小结点{if((W[j]