最小生成树问的题目课程设计报告材料.docx

精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
数据结构课程设计
设计目的错误！未定义书签.
设计内容1
概要设计1
1、 功能模块图1
2、 各个模块详细的功能描述 2
详细设计3
1 .主函数和其他函MGraph & G ,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵
(
int i,j,k;
cout<<"请输入城市个数与其之间的可连接线路数目： ";
cin>>>>;
cout<<"请输入各个城市名称(分别用一个字符代替)：〞；
for(i=0;i<G .vexnum;++i)
cin>>[i];
for(i=0;i<G .vexnum;++i)// 初始化数组
for(j=0;j<G .vexnum;++j)
(
Garcs[i][j].adj=MAX;
)
cout<<"请输入两个城市名称与其连接费用(严禁连接重复输入!): "<<endl;
for(k=0;k<G .arum;++k)
(
cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;
i = LocateVex(G,dgevalue[k].ch1);
j = LocateVex(G,dgevalue[k].ch2);
[i][j].adj = dgevalue[k].value;
].adj = G .arcs[i][j].adj;
)
return OK;
)
※临接矩阵的输出：
void Adjacency_Matrix(MGraph G) //用邻接矩阵存储数据
( 一
int i,j;
for(i=0; i<G .vexnum; i++)
(
for(j=0; j<G .vexnum; j++)
if([i][j].adj==MAX)
cout<<0<<" ";
else
cout<<[i][j].adj<<" ";
cout<<endl;
)
)
※邻接表的输出：
void Adjacency_List(MGraph G,Dgevalue dgevalue) 〃用邻接表储存数据 { —
int i,j;
for(i=0;i<G .vexnum;i++)
(
cout<<Gvexs[i]<<"->";
for(j=0;j<G .arum;j++)
if(dgevalue[j].ch1==[i]&&dgevalue[j].ch2!=G .vexs[i]) cout<<dgevalue[j].ch2<<"->";
else if(dgevalue[j].ch1!=[i]&&dgevalue[j].ch2==G .vexs[i]) cout<<dgevalue[j].ch1<<"->";
cout<<"\b\b "<<endl;
}
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
}
※最小生成树PRIM算法：
void MiniSpanTree_PRIM(MGraph G,char u)// 普里姆算法求最小生成树
(
int i,j,k;
Closedge closedge;
k = LocateVex(G,u);
for(j=0; j<; j++) // 辅助数组初始化
(
if(j != k)
(
closedge[j].adjvex = u;
closedge[j].lowcost = [k][j].adj;
}
}
closedge[k].lowcost = 0;
for(i=1; i<; i++)
(
k = Minimum(G,closedge);
cout<<" 城市"<<closedge[k].adjvex<<" 与城市"<<[k]<<"连
接."<<endl;
closedge[k].lowcost = 0;
for(j=0; j<; ++j)
(
if([k][j].adj < closedge[j].lowcost)
(
closedge[j].adjvex = [k];
closedge[j].lowcost= [k][j].adj;
}
}
}
}
int Minimum(MGraph G,Closedge closedge) // 求 closedge 中权值最小的边,
并返回其顶点在