《数据结构》 第七章图 (重点)
《数据结构》 第七章 图 (重点)
第七章图 主要内容 图的概念 ·图的存储结构 数组表尔法——邻接矩阵 邻接表表尔法 十字链表表示法二 邻接多重表表示法 °图的遍历 深度优先搜索」 广度优先搜索 第2页
第七章 图 第2页 主要内容 • 图的概念 • 图的存储结构 数组表示法——邻接矩阵 邻接表表示法 十字链表表示法 邻接多重表表示法 • 图的遍历 深度优先搜索 广度优先搜索
第七章图 主要内容 ·图的连通性问题 无向图的连通分量和生成树 构造最小生成树的Pm算法 构造最小生成树的 Kruskal算法 有向无环图 拓卦扑排序 ·关健路径 最短路径 第3页
第七章 图 第3页 主要内容 • 图的连通性问题 无向图的连通分量和生成树 构造最小生成树的Prim算法 构造最小生成树的Kruskal算法 • 有向无环图 • 拓扑排序 • 关健路径 • 最短路径
第七章图 第七章图 内容和要求 图及其有关的基本概念、图的存储结构及其图的遍历, 最短路径、拓扑排序的关健路径,动态存储管理。要求获得 有关图结构及其应用方面的初步知识和经验。理解图及其有 关的基本概念,图的存储方法,熟悉遍历图的深度优先 DFS)和广度优先(BFS)的搜索算法,了解最短路径、拓扑 排序、关健路径的方法及算法的基本思想 重点 图的三种常用的存储表示,DFS法和BFS法。难点是图 的邻接多重存储表示,DFS法和BFS法,最短路径。 第4
第七章 图 第4页 第七章 图 内容和要求 图及其有关的基本概念、图的存储结构及其图的遍历， 最短路径、拓扑排序的关健路径，动态存储管理。要求获得 有关图结构及其应用方面的初步知识和经验。理解图及其有 关的基本概念，图的存储方法，熟悉遍历图的深度优先（ DFS）和广度优先（BFS）的搜索算法，了解最短路径、拓扑 排序、关健路径的方法及算法的基本思想。 重点 图的三种常用的存储表示，DFS法和BFS法。难点是图 的邻接多重存储表示，DFS法和BFS法，最短路径
图的概念 第七章图 什么是图 图形结构是一种较线性表结构和树形结构更为复杂 的非线性数据结构。在人工智能、工程、数学、物理、 化学、计算机科学等学科领域中,图形结构均有着广泛 一的应用 线性表结构:数据元素即结点之间仅有线性关系 树形结构:数据元素之间具有明显的层次关系。每 层中的结点可允许有若干个孩子结点,但仅允许有一个 双亲结点(前趋) 图形结构:数据元素之间的关系是任意的,图中任 意两个结点之间都可能相关 事实上,树形结构是图形结构的一种特殊情况。 第5页
第七章 图 第5页 什么是图 图形结构是一种较线性表结构和树形结构更为复杂 的非线性数据结构。在人工智能、工程、数学、物理、 化学、计算机科学等学科领域中，图形结构均有着广泛 的应用。 线性表结构：数据元素即结点之间仅有线性关系。 树形结构：数据元素之间具有明显的层次关系。每 层中的结点可允许有若干个孩子结点，但仅允许有一个 双亲结点（前趋）。 图形结构：数据元素之间的关系是任意的，图中任 意两个结点之间都可能相关。 事实上，树形结构是图形结构的一种特殊情况。 ⚫ 图的概念
图的概念 第七章图 图常用来解决的九类主要问题 1.模拟计算机与通信网络的联接 2表示一张地图的一组坐标以及坐标之间的距离,以 一求得最短路径; 3.模拟交通网络的流量 4寻找从开始状态到目标状态的路径,如人工智能间 题求解; 5.模拟计算机算法,显示程序状态的变化; 6.为复杂活动各子任务的完成寻找顺序,如大型建筑 的建造; 第6页
第七章 图 第6页 图常用来解决的几类主要问题 1. 模拟计算机与通信网络的联接； 2. 表示一张地图的一组坐标以及坐标之间的距离，以 求得最短路径； 3. 模拟交通网络的流量； 4. 寻找从开始状态到目标状态的路径，如人工智能问 题求解； 5. 模拟计算机算法，显示程序状态的变化； 6. 为复杂活动各子任务的完成寻找顺序，如大型建筑 的建造； … … … … ⚫ 图的概念
0图的定义 第七章图 定义:图是一种数据结构,它的形式化定义为 Graph=(V,R 其中 V={xx∈ dataobject} RVR VR={<xyxP(xy)∧(x,y∈V)} 可以简记为 G=(V, E 其中V是顶点的有穷非空集合,E是中顶点的偶 对(称为边)的有穷集。 通常亦可将图G的顶点集和边集分别记作V(G)和 E(G)。 若E(G)为空集,则表示图G仅有顶点而没有边 第7页
第七章 图 第7页 定义： 图是一种数据结构，它的形式化定义为 Graph=(V,R) 其中 V={x|x∈dataobject} R={VR} VR={＜x,y＞| P(x,y)∧(x,y ∈V)} 可以简记为 G=（V，E） 其中V是顶点的有穷非空集合，E是V中顶点的偶 对（称为边）的有穷集。 通常亦可将图G的顶点集和边集分别记作V(G)和 E(G)。 若E(G)为空集，则表示图G仅有顶点而没有边。 ⚫ 图的定义
图的定义 第七章图 示例1有向图G1和无向图G2 V2 V( G1)={v12V2V32V4} G EG1)={ 3>,V3,Y4>V4,V1 V(G2)={v1,v2V3,V42v5} E(G2)={(V1V2)v1,V4)2(V2V3),(V2vs)(v3V4)、(v3,V3)} 第8页
第七章 图 第8页 示例1 有向图G1和无向图G2 G1 G2 ⚫ 图的定义 V(G1 )={v1 ,v2 ,v3 ,v4} E(G1 )={,, ,} V(G2 )={v1 ,v2 ,v3 ,v4 ,v5} E(G2 )={(v1 ,v2 ),(v1 ,v4 ), (v2 ,v3 ),(v2 ,v5 ),(v3 ,v4 ),(v3 ,v5 )} V1 V2 V3 V4 V1 V2 V4 V5 V3
图的术语 第七章图 顶点:图中的数据元素。 弧:有向边,用以尖括号括起来的有序对表示 弧尾:有向边vy>的始点v 弧头:有向边的终点v 有向图:图G中每条边都是有向边(弧) 无向图:图G中每条边都是没有方向的,这些边用以二 vY)形式的无序对表示 第9页
第七章 图 第9页 顶点：图中的数据元素。 弧：有向边，用以尖括号括起来的有序对表示。 弧尾：有向边的始点vi。 弧头：有向边的终点vj。 有向图：图G中每条边都是有向边（弧）。 无向图：图G中每条边都是没有方向的，这些边用以 (vi ,vj )形式的无序对表示。 ⚫ 图的术语 V1 V2 V3 V4 V1 V2 V4 V5 V3
图的术语 第七章图 图的顶点数n和边数e的关系:对有向图,0≤e≤m(n-1);对无 向图,0≤c5mm 有向完全图:恰有n(n-1)条有向边(即弧)的有向图 无向完全图:恰有2mn-1)条无向边的无向图 稀疏图:图中边或弧的数目e<<n?2 稠密图:图中边或弧的数目e~n2(准确地说,无向图的e接近 于2(m-1)有向图的e接近于n(m-1) 第10页
第七章 图 第10页 图的顶点数n和边数e的关系：对有向图，0≤e≤n(n-1)；对无 向图， 。 有向完全图：恰有n(n-1)条有向边（即弧）的有向图。 无向完全图：恰有 条无向边的无向图。 稀疏图：图中边或弧的数目e<<n2 。 稠密图：图中边或弧的数目e≈n2（准确地说，无向图的e 接近 于 ，有向图的e接近于n(n-1)。 ( 1) 2 1 0 e n n − ( 1) 2 1 n n − ( 1) 2 1 n n − ⚫ 图的术语 V1 V2 V3 V4 V1 V2 V4 V5 V3