课程设计 图的遍历与存储 共19页,4457字 [摘要] 图是应用最广泛的数学结构。图的遍历和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。对于广度优先遍历应利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实现。首先建立一空队列,从初始点出发进行访问,当被访问时入队,访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。常用的三种图的存储表示方式:邻接矩阵、邻接表和邻接多重表。 关键词:图 邻接表 周游算法 图的遍历与存储 图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。 图的存储结构除了要存储图中各个顶点的本身的信息外,同时还要存储顶点与顶点之间的所有关系(边的信息),常用的图的存储结构有邻接矩阵、邻接表和邻接多重表。 ...... |
- 上一篇:北京理工大学Java课程设计报告 火柴游戏
- 下一篇:数据库原理网上授课平台
查看评论
已有0位网友发表了看法