您的位置： 文档网所有分类高等教育工学 最小生成树问题课程设计报告

最小生成树问题课程设计报告

C++实现最小生成树。包括源程序及设计报告。

“最小生成树问题”课程设计

题目: 编制一个求出N个顶点图的最小生成树程序

一 需求分析:

(1)在n个城市间建设通信网络，只需要架设n-1条线路即可。以最低的代价建设这个通信网，即求图的最小生成树。

(2)利用克鲁斯卡尔算法求网的最小生成树。

(3)利用自定义的队列结构存放连通分量。

(4)以文本形式输出最小生成树中的各条边及它们的权值。输出格式为(int a,int b,int n),其中a，b为顶点序号,n为ab边的权；

(5)程序运行流程:

1)提示输入顶点数目；

2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树；

3)输出最小生成树并且退出；

(6)测试数据:9

二 概要设计:

1.表示边的类定义和接口:

class MyArc

{

public:

int m_beginVex;

int m_endVex;

int m_weight;

MyArc(int beginVex,int endVex,int weight);

MyArc(){}

//重载运算符

inline bool operator < (const MyArc& arc){ return m_weight<arc.m_weight;} inline bool operator == (const MyArc& arc){ return m_weight==arc.m_weight;} inline bool operator > (const MyArc& arc){ return m_weight>arc.m_weight; } };

2. 用邻接矩阵表示的图类的定义和接口:

class Graph

{

private:

int m_vexnum;

int m_arcnum;

int *m_pmatrix;

public:

~Graph();

Graph(int vexnum);

Graph(int vexnum,int *pmatrix);

第1页

你可能喜欢

  • 数据结构课程设计最小生成树
  • 最小生成树算法
  • 算法合集
  • 克鲁斯卡尔算法
  • 最小生成树算法实现
  • 校园导航系统
  • 重言式判别
  • 宿舍管理查询软件

最小生成树问题课程设计报告的相关文档搜索

最小生成树问题课程设计报告相关文档

最新文档

返回顶部