敦案 第七章图 程序设计—数据结构 图的遍历算法及其应用 目录 第7章图. 1 7.1图的定义和基本术语 7.2图的存储和创建. 2 7.2.1图的存储表示 7.2.2图的创建 _5 7.3图的遍历… 5 7.3.1深度优先搜索 5 7.3.2广度优先搜索 7.4遍历算法的应用.… 6 8 7.4.1应用问题概述 8 7.4.2求一条包含图中所有顶点的简单路径. 8 7.4.3求距v0的各顶点中最短路径长度最长的一个顶点 9 7.5图的连通性问题.… ,。。。2-。-。。。。，。。。。。。。。。,。。。,。。。,。，。，。,。。,。。。，.。。。,。 7.5.1无向图的连通分量和生成树10 7.5.2最小生成树.… 2 7.6有向无环图及其应用 12 文档编号引 完成时间 完成人张昱 修改时间20026-6 第0页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 0 页 目 录 第7章 图...............................................................................................................................1 7.1 图的定义和基本术语.................................................................................................1 7.2 图的存储和创建........................................................................................................2 7.2.1 图的存储表示..................................................................................................2 7.2.2 图的创建.........................................................................................................5 7.3 图的遍历..................................................................................................................5 7.3.1 深度优先搜索..................................................................................................5 7.3.2 广度优先搜索..................................................................................................6 7.4 遍历算法的应用........................................................................................................8 7.4.1 应用问题概述..................................................................................................8 7.4.2 求一条包含图中所有顶点的简单路径...............................................................8 7.4.3 求距v0的各顶点中最短路径长度最长的一个顶点.............................................9 7.5 图的连通性问题......................................................................................................10 7.5.1 无向图的连通分量和生成树...........................................................................10 7.5.2 最小生成树...................................................................................................12 7.6 有向无环图及其应用...............................................................................................12