1、 课程设计报告课程设计报告 课程名称课程名称 数据结构数据结构 课题名称课题名称 最小生成树问题最小生成树问题 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 1010 计本计本 2 2 班班 “最小生成树问题最小生成树问题”课程设计课程设计 题目: 编制一个求出 N 个顶点图的最小生成树程序 一一 需求分析需求分析: (1)在 n 个城市间建设通信网络， 只需要架设 n-1 条线路即可。 以最低的代价建设这个通信网， 即求图的最小生成树。 (2)利用克鲁斯卡尔算法求网的最小生成树。 (3)利用自定义的队列结构存放连通分量。 (4)以文本形式输出最小生成树中的各条边及它们的权值。 输
2、出格式为(int a,int b,int n),其中a， b 为顶点序号,n 为 ab 边的权； (5)程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； (6)测试数据:9 二二 概要设计概要设计: 1.表示边的类定义和接口: class MyArc public: int m_beginV ex; int m_endV ex; int m_weight; MyArc(int beginV ex,int endV ex,int weight); MyArc() /重载运算符 inline bool ope
3、rator arc) break; else +pos; m_list.insert(pos,arc); /将图的连通分量插入队列 void MyQueues:InsertGraph(const Graph ii; int vex=i-0; int *matrix=new intvex*vex; coutendl; SetMatrix(vex,matrix); Graph graph(vex,matrix),smtree(vex); kruskal(graph,smtree); SmallestTreeOutput(smtree); delete matrix; /用随机数组初始化 matri
4、x 数组并且打印 void SetMatrix(int vexnum,int *pmatrix) srand(unsigned)time(NULL); for(int i=0;ivexnum;+i)/产生随机权值矩阵 for(int j=i;jvexnum;+j) if(j=i) pmatrixi*vexnum+j=0; continue; int rnum=rand();rnum%=99;rnum+;/产生 199 的随机整数作为边的权值 pmatrixi*vexnum+j=rnum; pmatrixj*vexnum+i=rnum; cout“*随机产生的各边权值矩阵 顶点数为 “vexnu
5、m“ *n“; for( i=0;ivexnum;+i)/输出随机权值矩阵 for(int j=0;jvexnum;+j) coutpmatrixi*vexnum+j“t“; coutendl; /判断连通边 arc 后 图 graph 是否存在回路 bool IsCycle(Graph mylist.push_back(arc.m_beginV ex); int *ps=new intgraph.m_vexnum; for(int i=0;igraph.m_vexnum;+i) psi=0; while(!mylist.empty() int x=mylist.front(); psx=1;
6、 mylist.pop_front(); for(int i=0;igraph.m_vexnum;+i) if(graph.m_pmatrixi+x*graph.m_vexnum!=0) if(i=arc.m_endV ex) return true; if(psi!=1) mylist.push_back(i); delete ps; return false; /克鲁斯卡尔算法 void kruskal(const Graph/保存从小到大排列的边 arcqueues.InsertGraph(graph); MyArc myarc;/Arc 表示边的类型 int arcnum=0; /边的个数 while(arcnum
