第八章图 教学内容:8.1图的基本概念 8.2图的存储表示 8.3图的遍历 8.4图的连通性 8.5最小生成树 8.6最短路径 8.7有向无环图及其应用 2教学目的:(理解图的基本概念及术语 2)掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法 (3)熟练掌握图的两种遍历的算法思想、步骤 (4)理解最小生成树的概念,能按Prim算法构造最小生成树 ⑤5领会并掌握拓扑排序、关键路径、最短路径的算法思想。 3教学重点:(1理解图的定义、术语及其含义: (2)掌握各种图的邻接矩阵表示法及其类型说明 ③3理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法 4领会生成树和最小生成树的概念 (5)掌握由Pim算法思想构造最小生成树按Pim算法思想 (6)领会拓扑序列和拓扑排序的概念 (7)理解并掌握拓扑排序的算法思想 ⑧)理解并掌握关键路径的算法思想: (9)理解并掌握最短路径的算法思想 4.教学难点:(正确理解与区别图的常用术语 (2)区别图的两种存储结构的不同点及其应用场合 (3)关键路径的算法思想 (4)最短路径的算法思想 5学时安排:12学时 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 1 第八章 图 ⒈教学内容：8.1 图的基本概念 8.2 图的存储表示 8.3 图的遍历 8.4 图的连通性 8.5 最小生成树 8.6 最短路径 8.7 有向无环图及其应用 ⒉教学目的：⑴理解图的基本概念及术语； ⑵掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法； ⑶熟练掌握图的两种遍历的算法思想、步骤； ⑷理解最小生成树的概念，能按Prim算法构造最小生成树； ⑸领会并掌握拓扑排序、关键路径、最短路径的算法思想。 ⒊教学重点：⑴理解图的定义、术语及其含义； ⑵掌握各种图的邻接矩阵表示法及其类型说明； ⑶理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法； ⑷领会生成树和最小生成树的概念； ⑸掌握由Prim算法思想构造最小生成树按Prim算法思想； ⑹领会拓扑序列和拓扑排序的概念； ⑺理解并掌握拓扑排序的算法思想； ⑻理解并掌握关键路径的算法思想； ⑼理解并掌握最短路径的算法思想。 ⒋教学难点：⑴正确理解与区别图的常用术语； ⑵区别图的两种存储结构的不同点及其应用场合； ⑶关键路径的算法思想； ⑷最短路径的算法思想。 ⒌学时安排： 12学时
81图的基本概念 ◆图的定义和术语 ◆图的基本操作 ☆ ☆ 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 8.1 图的基本概念 图的定义和术语 图的基本操作
8.1.1图的定义和术语 4.图的定义 图( Graph)是由非空的顶点集合和一个描述顶点之间关 系一边(或者弧)的集合组成,其形式化定义为 G=(V, E V={ilv∈ dataobject},E={(ⅵi)ⅵ,ⅵ∈V∧P(ⅵ,)} 其中,G表示一个图,V是图G中顶点的集合,E是图G中边 的集合,集合E中P(V)表示顶点ⅵ和顶点v之间有一条直接 连线,即偶对(V)表示一条边 2 2021年1月21日 无向图G1
2021年1月21日 数据结构讲义 3 8.1.1 图的定义和术语 1．图的定义 图(Graph)是由非空的顶点集合和一个描述顶点之间关 系——边（或者弧）的集合组成，其形式化定义为： G＝（V，E） V＝{vi| vi∈dataobject}，E＝{( vi,vj)| vi, vj ∈V ∧P(vi, vj)} 其中，G表示一个图，V是图G中顶点的集合，E是图G中边 的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接 连线，即偶对(vi,vj)表示一条边
2图的相关术语 (1)无向图。在一个图中,如果任意两个顶点构成的偶对 中(v)∈E是无序的,即顶点之间的连线没有方向,则 称该图为无向图。如前图所示是一个无向图G1 2有向图。在一个图中,如果任意两个顶点构成的偶对 (v,v)∈E是有序的,即顶点之间的连线是有方向的, 则称该图为有向图。如下图所示是一个有向图G2:G2 (V2,E2) 有向图G2 2021年1月21日
2021年1月21日 数据结构讲义 4 2.图的相关术语 ⑴无向图。在一个图中，如果任意两个顶点构成的偶对 （vi, vj）∈E是无序的，即顶点之间的连线没有方向，则 称该图为无向图。如前图所示是一个无向图G1。 ⑵有向图。在一个图中，如果任意两个顶点构成的偶对 （vi, vj）∈E是有序的，即顶点之间的连线是有方向的， 则称该图为有向图。如下图所示是一个有向图G2：G2= (V2,E2)
(3)顶点、边、弧、弧头、弧尾。图中,数据元素ⅵ称为顶」 点 (vertex);P(vi,y)表示在顶点v和顶点v之间有一条直接连 线。如果是在无向图中,则称这条连线为边;如果是在有向 图中,一般称这条连线为弧。边用顶点的无序偶对(ⅵy) 来表示,称顶点ⅵ和顶点y互为邻接点,边(ⅵ,v)依附于 顶点v与顶点v;弧用顶点的有序偶对<vy来表示,有序 偶对的第一个结点v被称为始点(或弧尾),在图中就是不 带箭头的一端;有序偶对的第二个结点ⅵ被称为终点(或弧 头),在图中就是带箭头的一端。 (4)无向完全图。在一个无向图中,如果任意两顶点都有一 条直接边相连接,则称该图为无向完全图。可以证明,在 个含有n个顶点的无向完全图中,有n(n1)2条边 (5)有向完全图。在一个有向图中,如果任意两顶点之间都 有方向互为相反的两条弧相连接,则称该图为有向完全图 在一个含有n个顶点的有向完全图中,有n(n-1)条边 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 5 ⑶顶点、边、弧、弧头、弧尾。图中，数据元素vi称为顶 点(vertex )；P(vi, vj)表示在顶点vi和顶点vj之间有一条直接连 线。如果是在无向图中，则称这条连线为边；如果是在有向 图中，一般称这条连线为弧。边用顶点的无序偶对（vi, vj） 来表示，称顶点vi和顶点vj互为邻接点，边（vi, vj）依附于 顶点vi与顶点vj；弧用顶点的有序偶对来表示，有序 偶对的第一个结点vi被称为始点（或弧尾），在图中就是不 带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧 头），在图中就是带箭头的一端。 ⑷无向完全图。在一个无向图中，如果任意两顶点都有一 条直接边相连接，则称该图为无向完全图。可以证明，在一 个含有n个顶点的无向完全图中，有n(n-1)/2条边。 ⑸有向完全图。在一个有向图中，如果任意两顶点之间都 有方向互为相反的两条弧相连接，则称该图为有向完全图。 在一个含有n个顶点的有向完全图中，有n(n-1)条边
(6)稠密图、稀疏图。若一个图接近完全图,称为稠密图; 4称边数很少的图为稀疏图。 (7)顶点的度、入度、出度。顶点的度( degree)是指依附 于某顶点v的边数,通常记为TD(V)。在有向图中,要区别 顶点的入度与出度的概念。顶点v的入度是指以顶点为终点 的弧的数目。记为D(y;顶点v出度是指以顶点v为始点的 弧的数目,记为OD()。有TD(yD(y)+OD(V) 可以证明,对于具有n个顶点、e条边的图,顶点ⅵ的度TD (ⅵ)与顶点的个数以及边的数目满足关系: 2e= 2 tD(vi) 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 ⑹稠密图、稀疏图。若一个图接近完全图，称为稠密图； 称边数很少的图为稀疏图。 ⑺顶点的度、入度、出度。顶点的度（degree）是指依附 于某顶点v的边数，通常记为TD (v)。在有向图中，要区别 顶点的入度与出度的概念。顶点v的入度是指以顶点 为终点 的弧的数目。记为ID (v)；顶点v出度是指以顶点v为始点的 弧的数目，记为OD (v)。有TD (v)=ID (v)＋OD (v)。 • 可以证明，对于具有n个顶点、e条边的图，顶点vi的度TD (vi)与顶点的个数以及边的数目满足关系： 2e =
(8)边的权、网图。与边有关的数据信息称为权( weight )。在实际应用中,权值可以有某种含义。比如,在一个 反映城市交通线路的图中,边上的权值可以表示该条线路 的长度或者等级;对于一个电子线路图,边上的权值可以 表示两个端点之间的电阻、电流或电压值:对于反映工程 进度的图而言,边上的权值可以表示从前一个工程到后 个工程所需要的时间等等。边上带权的图称为网图或网络 ( network)。如果边是有方向的带权图,则就是一个有向 网图。 (⑨路径、路径长度。顶点v到顶点v之间的路径(path) 是指顶点序列vnV1V2, 。其中,(vnv1), (V12V2),…,yvmn)分别为图中的边。路径上边的数目称为 路径长度。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 ⑻边的权、网图。与边有关的数据信息称为权（weight ）。在实际应用中，权值可以有某种含义。比如，在一个 反映城市交通线路的图中，边上的权值可以表示该条线路 的长度或者等级；对于一个电子线路图，边上的权值可以 表示两个端点之间的电阻、电流或电压值；对于反映工程 进度的图而言，边上的权值可以表示从前一个工程到后一 个工程所需要的时间等等。边上带权的图称为网图或网络 （network）。如果边是有方向的带权图，则就是一个有向 网图。 ⑼路径、路径长度。顶点vp到顶点vq之间的路径（path） 是指顶点序列vp ,vi1,vi2, …, vim,vq。其中，（vp ,vi1）， (vi1,vi2)，…,(vim,vq )分别为图中的边。路径上边的数目称为 路径长度
⑩回路、简单路径、简单回路。称ⅵ的路径为回路或 者环( cycle)。序列中顶点不重复出现的路径称为简单 「路径。除第一个顶点与最后一个顶点之外,其他顶点不 重复出现的回路称为简单回路,或者简单环。 D子图。对于图G=(V,E),G=(V,E),若存 在V是V的子集,E是E的子集,则称图G是G的一个子 图。下图示出了G2和G1的两个子图G和G”。 (a)G (b)G 图G2和G1的两个子图示意 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 ⑽回路、简单路径、简单回路。称vi的路径为回路或 者环（cycle）。序列中顶点不重复出现的路径称为简单 路径。除第一个顶点与最后一个顶点之外，其他顶点不 重复出现的回路称为简单回路，或者简单环。 ⑾子图。对于图G=（V，E），G’=（V’，E’），若存 在V’是V的子集 ，E’是E的子集 ，则称图G’是G的一个子 图。下图示出了G2和G1的两个子图G’和G’’
①②连通的、连通图、连通分量。在无向图中,如果从 十个顶点v到另一个顶点ⅶ有)有路径,则称顶点ⅵ和是连 通的。如果图中任意两顶点都是连通的,则称该图是连通 图。无向图的极大连通子图称为连通分量。下图(a)中有 两个连通分量,如图(b)所示。 A B③(B (a)无向图G3 (b)G3的两个连通分量 无向图及连通分量示意 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 ⑿连通的、连通图、连通分量。在无向图中，如果从一 个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连 通的。如果图中任意两顶点都是连通的，则称该图是连通 图。无向图的极大连通子图称为连通分量。下图 (a)中有 两个连通分量，如图 (b)所示
3强连通图、强连通分量。对于有向图来说,若图中任意 对顶点ⅵ和v()均有从一个顶点v到另一个顶点y有路 径,也有从ⅵ到ⅵ的路径,则称该有向图是强连通图。有向 图的极大强连通子图称为强连通分量。 左下图中有两个强连通分量,分别是{ 是{V12 2v3}和{4}, 如右下图所示。 ] v34 有向图G2 有向图G2的两个强连通分量示意 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 ⒀强连通图、强连通分量。对于有向图来说，若图中任意 一对顶点vi 和vj(i≠j)均有从一个顶点vi到另一个顶点vj有路 径，也有从vj到vi的路径，则称该有向图是强连通图。有向 图的极大强连通子图称为强连通分量。 左下图中有两个强连通分量，分别是{v1,v2,v3}和{v4}， 如右下图所示