4.系统运行时窗口截图：（VC6.0下的运行结果）
订
票系统菜单窗口 0.输入航班的信息 1.列出航班的信息
2.按航班号查询航
班信息
3.按城市来查
询航班 4.订票程序
5.退票系统 6.
修改飞机航班的信
息
7.保存文件 8.读取文件 、下载文件
图的遍历过程演
示
一． 需求分析：
设计程序完成如下功能：对给定的图的结构和起点，产生深度优先遍历和广度优先遍历，并列出求解的过程动态演示。
二． 主要设计思路：
设计思想：简而言之，深度优先，就是先遍历它的一个邻接点，这个邻接点的邻接点……然后才遍历其他的邻接点。广度优先，就是先把它所有的邻接点都遍历完以后，再遍历它每个邻接点的邻接点 。存储结构为图的邻接多重表，它是无向图的一种链式存储结构。
深度优先遍历：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
广度优先遍历：设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，…，xs和y1，y2，…，yt。
为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，…，xs和y1，y2，…，yt，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，故保证了每个顶点至多只有一次入队。
A. 图的算法构造思想：
1．CreateALGraph()
初始条件:V是图的顶点集,VR是图中弧的集合. 操作结果:按V和VR是定义构造图G. 2. DestroyGraph(&G) 初始条件:图G存在 操作结果:销毁图G 3．LocateVex(G,u)
初始条件: 图G存在,u和G中顶点有相同的特征
操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他
信息
4. GetVex(G,v)
初始条件: 图G存在,v是G中顶点 操作结果:返回v的值 5. FirstAjvex(G,v)
初始条件: 图G存在,v是G中顶点
相关推荐：
loading