西电离散大作业.docx

西电离散大作业.docx离散大作业
班级：021051
学号：02105035
姓名：戴涛
一实验要求及内容
用prime算法求解最小生成树
二实验程序
#include〃stdio. h〃
ttinclude^string. h〃
ttinclude^malloc. h〃
ttinclude^iostream. h〃
^include iomanip. h〃
ttdefine MAX 20 //最多顶点个数
ttdefine INFINIT 32768//表示极大值，即 8
typedef struct
(int adj ; //adj是权值类型
}ArcNode;
typedef struct
(int vexs [MAX], vexnum, arcnum;
/*vexs表示顶点向量;vexnum, arcnumf分别表示图的顶点数和弧数*/
ArcNode arcs [MAX] [MAX] ; /*邻接矩阵*/
}AdjMatrix;
typedef struct
(int adjvex;//存放顶点编号
int lowcost;//存放顶点权值
)Node;
Node close [MAX] ;//求最小生成树时的辅助数组 int flag=0;
int Locate (AdjMatrix *G, int V) //求顶点位置函数
{int j=-l, k;
for (k=0;k<G->vexnum;k++)
if (G~>vexs[k]二二V) {j=k;break;) return j;
}
AdjMatrix ^creat (AdjMatrix *G) //创建无向网
(int i, j, k, vl, v2, weight, m=l;
printfC请输入网中的顶点数：〃)；
scanf(〃％d〃, &G->vexnum);
if(G->vexnum<=l)
{cout<<〃\n****************最小生成树不存在! ****************** ***〃〈〈endl;
flag=l;
return G;
}
else
(printf (zz请输入网中的边数：〃)；
scanf(〃％d〃, &G->arcnum);
for (i=0; i<G->vexnum; i++) 〃初始化邻接矩阵
for(j=0;j<G->vexnum;j++)
if (i二二j) G->arcs[i][j]. adj=0;
else G->arcs[i][j]. adj=INFINIT;
printfC请输入网中的顶点编号：〃)；//输入网中的顶点编号
for(i=0;i<G->vexnum;i++)
scanf(〃%d〃, &G->vexs [i]);
printf (/z输入每条弧所对应的两个顶点及权值〈格式：起点 终点 权 值 >!\n〃)；
for(k=0;k<G->arcnum;k++)
{ cout«，,请输入第〃〈〈ni++〈<〃条弧：〃；
cin»vl»v2»weight; //输入一条弧的两个顶点及权值
i=Locate (G, vl);
j=Locate (G, v2);
G->arcs[i] [j]. adj=wei