第8章图 图的基本概念 >图的基本运算 >图的基本存储结构 图的遍历 >生成树与最小生成树 >最短路径 >拓扑排序 >关键路径
第８章 图 ➢图的基本概念 ➢ 图的基本运算 ➢生成树与最小生成树 ➢拓扑排序 ➢ 图的基本存储结构 ➢最短路径 ➢关键路径 ➢ 图的遍历
8.1图的基本概 图的定义 图是由一个非空的顶点集合和一个描述顶点之间 多对多关系的边(或弧)集合组成的一种数据结构 它可以形式化地表示为 图=(V,E) 其中v=X∈某个数据对象集},它是顶点的有穷 非空集合;E={(x,y)X,yeV或E={X,y>|X yeV且P(x,y)},它是顶点之间关系的有穷集合 也叫做边集合,P(x,y)表示从x到y的一条单向 通路
8.1 图的基本概念 一、图的定义 图是由一个非空的顶点集合和一个描述顶点之间 多对多关系的边（或弧）集合组成的一种数据结构， 它可以形式化地表示为： 图＝（V，E） 其中V={x|x某个数据对象集}，它是顶点的有穷 非空集合；E={（x，y）|x，yV}或E={|x， yV且P（x，y）}，它是顶点之间关系的有穷集合， 也叫做边集合，P（x，y）表示从x到y的一条单向 通路
图的应用举例 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 边:连接元件之间的线路 例3通讯线路图 V3 V4) 顶点:地点 边:地点间的连线 例4各种流程图 如产品的生产流程图 顶点:工序 V2 V3 边:各道工序之间的顺序关系
图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； V0 V3 V4 V1 V2 V0 V1 V2 V3 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系
通常,也将图G的顶点集和边集分别记为∨(G) 和E(G)。E(G)可以是空集,若E(G)为空 则图G只有顶点而没有边。 若图G中的每条边都是有方向的,则称G为有向 图。在有向图中,一条有向边是由两个顶点组成的有 序对,有序对通常用尖括号表示。例如,有序对表示一条由到v的有向边。有向边又称为弧,弧 的始点称为弧尾,弧的终点称为弧头。若图G中的每 条边都是没有方向的,则称G为无向图。无向图中的 边均是顶点的无序对,无序对通常用圆括号表示
通常，也将图G的顶点集和边集分别记为V（G） 和E（G）。E（G）可以是空集，若E（G）为空， 则图G只有顶点而没有边。 若图G中的每条边都是有方向的，则称G为有向 图。在有向图中，一条有向边是由两个顶点组成的有 序对，有序对通常用尖括号表示。例如，有序对表示一条由vi到vj的有向边。有向边又称为弧，弧 的始点称为弧尾，弧的终点称为弧头。若图G中的每 条边都是没有方向的，则称G为无向图。无向图中的 边均是顶点的无序对，无序对通常用圆括号表示
例图8-1 有序对<vv 用以为v起点、以v为终点 的有向线段表示,称为有向 边或弧; (a)有向图G1(b)无向图 图81(a)表示的是有向图G1,该图的顶点集和 边集分别为 V(G1)={1,v2,V3,V4 E(G1)=
图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 无序对y) 用连接顶点v、的线段 表示,称为无向边; (a)有向图G1(b)无向图 图81(b)表示的是无向图G2,该图的顶点集和 边集分别为 V(G2)={1,v2,v3,V4,V5 E(G2)={(Ⅵ,v2),(v1,v3),( (V2,Y3),(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,)或M,y是E(G)中的一条边,则要 求v1; (2)一对顶点间不能有相同方向的两条有向边; (3)—对顶点间不能有两条无向边,即只讨论简 单的图
在以后的讨论中，我们约定： （1）一条边中涉及的两个顶点必须不相同，即： 若（vi，vj）或是E（G）中的一条边，则要 求vi≠vj； （2）一对顶点间不能有相同方向的两条有向边； （3）一对顶点间不能有两条无向边，即只讨论简 单的图
二、完全图 若用n表示图中顶点的数目,用e表示图中边的 数目,按照上述规定,容易得到下述结论:对于 具有n个顶点的无向图,其边数e小于等于n(n-1) 2,边数恰好等于n(n1)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 图82所示的G3与G4分别是具有4个顶点的无向 完全图和有向完全图。图G3共有4个顶点6条边;图 G4共有4个顶点12条边。 若(M,y)是条无向边,则称顶点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相关联。 度、入度、出度 在图中,一个顶点的度就是与该顶点相关联的 边的数目,顶点的度记为D()。例如在图82 (a)所示的无向图G3中,各顶点的度均为3。 若G为有向图,则把以顶页点V终点的边的数目 称为顶点v的入度,记为D(ⅴ);把以顶点v为始 点的边的数目称为v的出度,记为OD(v),有向 图中顶点的度数等于顶点的入度与出度之和,即D (V)=D(y)+OD()
若是一条有向边，则称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）