基于C++的交通咨询系统开发设计 毕业论文+项目源码

---

目录一、实验目的及要求二、算法原理概述1、图的基本概念2、最短路径(Prim算法和Dijkstra算法)3、拓扑排序三、软件开发环境及工具四、实验内容1、问题提出2、解决思路3、算法步骤4、结果分析5、实验核心代码五、实验总结六、参考文献附录 完整源代码一、实验目的及要求（1）图的存储表示及其基本操作实现。（2）最短路径算法。（3）系统功能：要求设计一个简易的交通咨询系统，可让用户咨询任意两个城市之间的最短距离、最低花费或最少时间等问题。（4）对于不同的咨询要求，输入咨询的内容。（5）用户界面的友好性：程序能提供菜单供用户选择以及相应的交互信息。二、算法原理概述1.图的基本结构（1）有向图。若E是有向边（弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为，其中v，w是顶点，v称为弧尾，w称为弧头，称为从顶点v到顶点w的弧。（2）无向图。若E是无向边（边）的有限集合时，则图G为无向图。边是顶点的无序对，记为（v，w）或（w，v），因为两者相等，其中v，w是顶点，顶点V，w互为邻接点。边（v，w）依附于顶点v，w，或者边（v，W）和顶点v，w相关联。（3）简单图。一个图G若满足：①不存在重复边；②不存在顶点到自身的边，则称图G为简单图。（4）多重图。若图G中某两个结点之间的边数多于一条，又允许顶点通过一条边和自己关联，则图G为多重图。（5）完全图（筒单完全图）。对于无向图，任意两个顶点之间都存在边。对于有向图，任意两个顶点之间都存在方向相反的两条弧。（6）子图。设有两个图G=（V，E）和G'=（V，E），若”是V的子集，且E'是E的子集，则称G'是G的子图。若有满足V（G）=V（G）的子图G，则称其为G的生成子图。（7）连通、连通图。在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G是连通图。极小连通子图是既要保持图连通又要使得边数最少的子图。（8）生成树。连通图的生成树是包含图中全部顶点的一个极小连通子图。（9）顶点的度、入度和出度。对于无向图，顶点v是依附于该顶点的边的条数。无向图的全部顶点的度的和等于边数的两倍。对于有向图，入度是以顶点v为终点的有向边的数目。出度是以顶点v为起点的有向边的数目。顶点的度等于入度和出度之和。有向图的全部顶点的入度之和与出度之和相等，并且等于边数。（10）边的权和网。在一个图中，每条边都可以标上具有某种意义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。2.图的存储结构图的存储结构有四种：邻接矩阵法、邻接表法、十字链表法、邻接多重表法。（11）路径、路径长度和回路。顶点v。到顶点v，之间的一条路径是指顶点序列Ve，V1，Ve…，Vm，Ve。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。