数据结构西电大作业!

最小生成树

#include #include #include

#define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define MAX 1000 typedef struct Arcell

{double adj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct

{char vexs[MAX_VERTEX_NUM]; AdjMatrix arcs;

int vexnum,arcnum;}MGraph; typedef struct Pnode

{char adjvex;double lowcost;}Pnode,Closedge[MAX_VERTEX_NUM]; typedef struct Knode {char ch1; char ch2;

double value;}Knode,Dgevalue[MAX_VERTEX_NUM]; int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch);

int Minimum(MGraph G,Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); int CreateUDG(MGraph & G,Dgevalue & dgevalue) {int i,j,k;

cout<<\请输入图中节点个数和边/弧的条数:\cin>>G.vexnum>>G.arcnum; cout<<\请输入节点:\for(i=0;i>G.vexs[i];

for(i=0;i

cout<<\请输入一条边依附的定点及边的权值:\for(k=0;k

{cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;i=LocateVex(G,dgevalue[k].ch1); j=LocateVex(G,dgevalue[k].ch2); G.arcs[i][j].adj=dgevalue[k].value; G.arcs[j][i].adj=G.arcs[i][j].adj; }

return OK; }

int LocateVex(MGraph G,char ch) {int a;

for(int i=0; i

void MiniSpanTree_PRIM(MGraph G,char u) {int i,j,k;Closedge closedge; k=LocateVex(G,u);

for(j=0; j

{closedge[j].adjvex=u;

closedge[j].lowcost=G.arcs[k][j].adj;} }closedge[k].lowcost=0; for(i=1; i

cout<<\.vexs[k]<<\ge[k].lowcost=0;

for(j=0; j

{if(G.arcs[k][j].adj

closedge[j].lowcost=G.arcs[k][j].adj;} } } }

int Minimum(MGraph G,Closedge closedge) {int i,j;double k=1000; for(i=0; i

{if(closedge[i].lowcost!=0 && closedge[i].lowcost

}return j; }

void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue) {int p1,p2,i,j;

int bj[MAX_VERTEX_NUM]; for(i=0; i

Sortdge(dgevalue,G); for(i=0; i

{p1=bj[LocateVex(G,dgevalue[i].ch1)]; p2=bj[LocateVex(G,dgevalue[i].ch2)];

if(p1!=p2)

{cout<<\for(j=0; j

void Sortdge(Dgevalue & dgevalue,MGraph G) {int i,j;

double temp; char ch1,ch2;

for(i=0; i

{if(dgevalue[i].value > dgevalue[j].value) {temp = dgevalue[i].value;

dgevalue[i].value = dgevalue[j].value; dgevalue[j].value = temp; ch1 = dgevalue[i].ch1;

dgevalue[i].ch1 = dgevalue[j].ch1;dgevalue[j].ch1 = ch1; ch2 = dgevalue[i].ch2;

dgevalue[i].ch2 = dgevalue[j].ch2; dgevalue[j].ch2 = ch2;} } } }

void main() {int i,j; MGraph G; char u;

Dgevalue dgevalue;

CreateUDG(G,dgevalue);

cout<<\图的邻接矩阵为:\for(i=0; i

cout<<\普利姆算法===============\\n\cout<<\请输入起始点:\

cout<<\构成最小代价生成树的边集为:\\n\MiniSpanTree_PRIM(G,u);

cout<<\克鲁斯科尔算法=============\\n\cout<<\构成最小代价生成树的边集为:\\n\

MiniSpanTree_KRSL(G,dgevalue); }

程序运行结果如下

假设有三个结点三条边 结点1 结点2 结点3 结点1到结点2的权值为1 结点2到结点3的权值为2 结点1到结点3的权值为3 得出邻接矩阵

假设输入起始点为结点2 得出的最小成树

结果一表示prim算法得出的最小生成树 结果二表示kruskal 算法得出的最小生成树