学海网

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