《数据结构》 第七章图 (重点)
《数据结构》 第七章 图 (重点)
第七章图 主要内容 图的概念 ·图的存储结构 数组表尔法——邻接矩阵 邻接表表尔法 十字链表表示法二 邻接多重表表示法 °图的遍历 深度优先搜索」 广度优先搜索 第2页
第七章 图 第2页 主要内容 • 图的概念 • 图的存储结构 数组表示法——邻接矩阵 邻接表表示法 十字链表表示法 邻接多重表表示法 • 图的遍历 深度优先搜索 广度优先搜索
第七章图 主要内容 ·图的连通性问题 无向图的连通分量和生成树 构造最小生成树的Pm算法 构造最小生成树的 Kruskal算法 有向无环图 拓卦扑排序 ·关健路径 最短路径 第3页
第七章 图 第3页 主要内容 • 图的连通性问题 无向图的连通分量和生成树 构造最小生成树的Prim算法 构造最小生成树的Kruskal算法 • 有向无环图 • 拓扑排序 • 关健路径 • 最短路径
第七章图 第七章图 内容和要求 图及其有关的基本概念、图的存储结构及其图的遍历, 最短路径、拓扑排序的关健路径,动态存储管理。要求获得 有关图结构及其应用方面的初步知识和经验。理解图及其有 关的基本概念,图的存储方法,熟悉遍历图的深度优先 DFS)和广度优先(BFS)的搜索算法,了解最短路径、拓扑 排序、关健路径的方法及算法的基本思想 重点 图的三种常用的存储表示,DFS法和BFS法。难点是图 的邻接多重存储表示,DFS法和BFS法,最短路径。 第4
第七章 图 第4页 第七章 图 内容和要求 图及其有关的基本概念、图的存储结构及其图的遍历， 最短路径、拓扑排序的关健路径，动态存储管理。要求获得 有关图结构及其应用方面的初步知识和经验。理解图及其有 关的基本概念，图的存储方法，熟悉遍历图的深度优先（ DFS）和广度优先（BFS）的搜索算法，了解最短路径、拓扑 排序、关健路径的方法及算法的基本思想。 重点 图的三种常用的存储表示，DFS法和BFS法。难点是图 的邻接多重存储表示，DFS法和BFS法，最短路径
图的概念 第七章图 什么是图 图形结构是一种较线性表结构和树形结构更为复杂 的非线性数据结构。在人工智能、工程、数学、物理、 化学、计算机科学等学科领域中,图形结构均有着广泛 一的应用 线性表结构:数据元素即结点之间仅有线性关系 树形结构:数据元素之间具有明显的层次关系。每 层中的结点可允许有若干个孩子结点,但仅允许有一个 双亲结点(前趋) 图形结构:数据元素之间的关系是任意的,图中任 意两个结点之间都可能相关 事实上,树形结构是图形结构的一种特殊情况。 第5页
第七章 图 第5页 什么是图 图形结构是一种较线性表结构和树形结构更为复杂 的非线性数据结构。在人工智能、工程、数学、物理、 化学、计算机科学等学科领域中，图形结构均有着广泛 的应用。 线性表结构：数据元素即结点之间仅有线性关系。 树形结构：数据元素之间具有明显的层次关系。每 层中的结点可允许有若干个孩子结点，但仅允许有一个 双亲结点（前趋）。 图形结构：数据元素之间的关系是任意的，图中任 意两个结点之间都可能相关。 事实上，树形结构是图形结构的一种特殊情况。 ⚫ 图的概念