人民邮政出版社：《数据结构》课程教学资源（PPT课件）第8章 图

第8章图 >图的基本概念 >图的基本运算 >图的基本存储结构 >图的遍历 >生成树与最小生成树 >最短路径 >拓扑排序 >关键路径

第８章 图 ➢图的基本概念 ➢ 图的基本运算 ➢生成树与最小生成树 ➢拓扑排序 ➢ 图的基本存储结构 ➢最短路径 ➢关键路径 ➢ 图的遍历

8.1图的基本概念 图的定义 图是由一个非空的顶点集合和一个描述顶点之间 多对多关系的边(或弧)集合组成的一种数据结构, 它可以形式化地表示为 图=(V,E) 其中v=∈某个数据对象集},它是顶点的有穷 非空集合;E={(X,y)X,yeⅤ或E={|X yV且P(x,y)},它是顶点之间关系的有穷集合 也叫做边集合,P(x,y)表示从x到y的一条单向 通路

8.1 图的基本概念 一、图的定义 图是由一个非空的顶点集合和一个描述顶点之间 多对多关系的边（或弧）集合组成的一种数据结构， 它可以形式化地表示为： 图＝（V，E） 其中V={x|x某个数据对象集}，它是顶点的有穷 非空集合；E={（x，y）|x，yV}或E={|x， yV且P（x，y）}，它是顶点之间关系的有穷集合， 也叫做边集合，P（x，y）表示从x到y的一条单向 通路

图的应用举例 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 vo 边:连接元件之间的线路 例3通讯线路图 V4 顶点:地点 边:地点间的连线 VO 例4各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系

图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； V0 V3 V4 V1 V2 V0 V1 V2 V3 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系

通常,也将图G的顶点集和边集分别记为V(G) 和E(G)。E(G)可以是空集,若E(G)为空 则图G只有顶点而没有边。 若图G中的每条边都是有方向的,则称G为有向 图。在有向图中,一条有向边是由两个顶点组成的有 序对,有序对通常用尖括号表示。例如,有序对表示条由v到v的有向边。有向边又称为弧,弧 的始点称为弧尾,弧的终点称为弧头。若图G中的每 条边都是没有方向的,则称G为无向图。无向图中的 边均是顶点的无序对,无序对通常用圆括号表示

通常，也将图G的顶点集和边集分别记为V（G） 和E（G）。E（G）可以是空集，若E（G）为空， 则图G只有顶点而没有边。 若图G中的每条边都是有方向的，则称G为有向 图。在有向图中，一条有向边是由两个顶点组成的有 序对，有序对通常用尖括号表示。例如，有序对表示一条由vi到vj的有向边。有向边又称为弧，弧 的始点称为弧尾，弧的终点称为弧头。若图G中的每 条边都是没有方向的，则称G为无向图。无向图中的 边均是顶点的无序对，无序对通常用圆括号表示

例图8 有序对 用以为V起点、以v为终点 的有向线段表示,称为有向 V4) 边或弧 VE (a)有向图G1(b)无向图 图81(a)表示的是有向图G1,该图的顶点集和 边集分别为 V(G1)={V1,V2,V3,W4 E(G1)={,,,<v3,V2

图8-1 v1 v2 v3 v4 v1 v2 v4 v5 v3 （a）有向图G1（b）无向图 G2 图8.1（a）表示的是有向图G1，该图的顶点集和 边集分别为： V（G1）={v1，v2，v3，v4 } E（G1）={，，，} 例 有序对 ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧；

例:图8-1 无序对(v): 用连接顶点v、V的线段 表示,称为无向边; (a)有向图G1(b)无向图 图81(b)表示的是无向图G2,该图的顶点集和 边集分别为 V(G2)={1,V2,v3,V4,V5 E(G2)={(Ⅵ,V2),(v1,v3),(v1,V4), (v2,v3),(v2,v5),(v4,v5)

例：图8-1 v1 v2 v3 v4 v1 v2 v4 v5 v3 （a）有向图G1（b）无向图 G2图8.1（b）表示的是无向图G2，该图的顶点集和 边集分别为： V（G2）={v1，v2，v3，v4，v5 } E（G2）={（vl，v2），（v1，v3），（v1，v4）， （v2，v3），（v2，v5），（v4，v5）} 无序对(vi ,vj )： 用连接顶点vi、vj的线段 表示，称为无向边；

在以后的讨论中,我们约定 (1)一条边中涉及的两个顶点必须不相同,即: 若(v;,V)或是E(G)中的一条边,则要 求v; (2)一对顶点间不能有相同方向的两条有向边; (3)一对顶点间不能有两条无向边,即只讨论简 单的图

在以后的讨论中，我们约定： （1）一条边中涉及的两个顶点必须不相同，即： 若（vi，vj）或是E（G）中的一条边，则要 求vi≠vj； （2）一对顶点间不能有相同方向的两条有向边； （3）一对顶点间不能有两条无向边，即只讨论简 单的图

完全图 若用n表示图中顶点的数目,用e表示图中边的 数目,按照上述规定,容易得到下述结论:对于 个具有n个顶点的无向图,其边数e小于等于n(n1) /2,边数恰好等于n(n-1)/2的无向图称为无向完 全图;对于一个具有n个顶点的有向图,其边数e小 于等于n(n-1),边数恰好等于n(n-1)的有向图 称为有向完全图。也就是说完全图具有最多的边数, 任意一对顶点间均有边相连

若用n表示图中顶点的数目，用e表示图中边的 数目，按照上述规定，容易得到下述结论：对于一 个具有n个顶点的无向图，其边数e小于等于n（n-1） /2，边数恰好等于n（n-1）/2的无向图称为无向完 全图；对于一个具有n个顶点的有向图，其边数e小 于等于n（n-1），边数恰好等于n（n-1）的有向图 称为有向完全图。也就是说完全图具有最多的边数， 任意一对顶点间均有边相连。 二、完全图

例:图8-2 (a)无向完全图G3(b)有向完全图G4 图8所示的G3与G分别是具有4个顶点的无向 完全图和有向完全图。图3共有4个顶点6条边;图 G共有4个顶点12条边。 若(w,)是一条无向边,则称顶点v和v互为 邻接点

例：图8-2 v1 v2 v3 v4 v1 v2 v3 v4 （a）无向完全图G3（b）有向完全图G4 图8.2所示的G3与G4分别是具有4个顶点的无向 完全图和有向完全图。图G3共有4个顶点6条边；图 G4共有4个顶点12条边。 若（vi，vj）是一条无向边，则称顶点vi和vj互为 邻接点

若是一条有向边,则称v邻接到v,V邻 接于,并称有向边V,>关联于与v,或称有向 边,y>与顶点v和v相关联。 度、入度、出度 在图中,一个顶点的度就是与该顶点相关联的 边的数目,顶点v的度记为D(v)。例如在图82 (a)所示的无向图G3中,各顶点的度均为3 若G为有向图,则把以页点V终点的边的数目 称为顶点v的入度,记为D(ⅴ);把以顶点v为始 点的边的数目称为v的出度,记为OD(v),有向 图中顶点的度数等于顶点的入度与出度之和,即D (ⅴ)=|D(v)+OD(v)

若是一条有向边，则称vi邻接到vj，vj邻 接于vi，并称有向边关联于vi与vj，或称有向 边与顶点vi和vj相关联。 三、度、入度、出度 在图中，一个顶点的度就是与该顶点相关联的 边的数目，顶点v的度记为D（v）。例如在图8.2 （a）所示的无向图G3中，各顶点的度均为3。 若G为有向图，则把以顶点v为终点的边的数目 称为顶点v的入度，记为ID（v）；把以顶点v为始 点的边的数目称为v的出度，记为OD（v），有向 图中顶点的度数等于顶点的入度与出度之和，即D （v）=ID（v）+OD（v）