北京大学：《数据结构与算法》课程教学资源（实验班讲义）第六章 图

主要内容 数据结构与算法 令61图的基本概念 第六章图 62图的抽象数据类型 任课教员:张铭 ◇63图的存储结构 http:db.pku.edu.cn/mzhang/ds/ 令64图的周游(深度、广度、拓扑) nang@db.pku.edu.cn 北京大学信息科学与技术学院 ◇65最短路径问题 络与信息系统研究所 66最小支撑树 ⊙版权所有,转载或翻印必究 61图的基本概念 无向图 G=(v,E)表示 V是顶点( vertex)集合 边涉及顶点的偶 E是边(edge)的集合 对无序 边的终点 实际上是双通 稀疏图( sparse graph) 密集图( dense graph) 完全图( complete graph) 点叔新有,躺成舒鬼 京大息 有向图 有向图( directed graph或 ■标号图( abeled graph) digraph) 带权图( weighted graph) 边涉及顶点的偶对是有序的 15

1 数据结构与算法 第六章 图 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 6.1 图的基本概念 „ 6.2 图的抽象数据类型 „ 6.3 图的存储结构 „ 6.4 图的周游（深度、广度、拓扑） „ 6.5 最短路径问题 „ 6.6 最小支撑树 北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 6.1 图的基本概念 „ G=（V，E）表示 „ V是顶点（vertex）集合 „ E是边（edge）的集合 „ 边的始点 „ 边的终点 „ 稀疏图（sparse graph） „ 密集图（dense graph） „ 完全图（complete graph） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 无向图 „ 边涉及顶点的偶 对无序 „ 实际上是双通 北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 有向图 „ 有向图（directed graph或 digraph） „ 边涉及顶点的偶对是有序的 北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 „ 标号图（labeled graph） „ 带权图（weighted graph）

顶点的度( degree) 子图( subgraph) 与该顶点相关联的边的数目 图G=(v,E),G=(V,E)中,若v≤V, 入度( in degree) E≤E,并且E中的边所关联的顶点都在v 出度( out degree) 中,则称图G是图G的子图 路径(path) 回路( cycle,也称为环) 从顶点v到顶点v的路径 ■无向图中,如果两个结点之间有平行边, 顶点序列vV,V2 容易让人误看作“环”) v,v使得(v,v1) 路径长度大于等于3 v)〔着 对有向图,则使得<v ■有向图两条边可以构成环,例如<V,V1> va>,<va;Ⅵa> 和<V,V>构成环 Va,v>)都在E中 简单路径( simple path) 路径长度( ength) 点叔新有,躺成舒鬼 权新有,轴彩光 有根图 ■简单回路( simple cycle) 个有向图中,若存在一个顶点 ■无环图( acyclic graph) v。,从此顶点有路径可以到达图 有向无环图( directed acyclic 中其它所有顶点,则称此有向图 graph,简写为DAG 为有根的图,V称作图的根 ■树、森林 值惠单 曰 权新有轴

2 北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 顶点的度（degree） „ 与该顶点相关联的边的数目 „ 入度(in degree) „ 出度(out degree) 北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 子图（subgraph） „ 图G=(V，E)，G’=(V’，E’)中，若V’≤V， E’≤E，并且E’中的边所关联的顶点都在V’ 中，则称图G’是图G的子图 北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 路径（path） „ 从顶点Vp到顶点Vq的路径 „ 顶点序列Vp，Vi1，Vi2，…， Vin，Vq，使得（Vp，Vi1）， (Vi1，Vi2) ，…，(Vin，Vq)（若 对有向图，则使得<Vp， Vi1>，<Vi1，Vi2> ，…， <Vin，Vq>）都在E中 „ 简单路径（simple path） „ 路径长度（length） Vp Vq 北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 回路（cycle，也称为环） „ 无向图中，如果两个结点之间有平行边， 容易让人误看作“环”） „ 路径长度大于等于3 „ 有向图两条边可以构成环，例如<V0，V1> 和<V1，V0> 构成环 V0 ╳ √ √ V1 √ 北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 „ 简单回路（simple cycle） „ 无环图（acyclic graph） „ 有向无环图（directed acyclic graph，简写为DAG） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 有根图 „ 一个有向图中，若存在一个顶点 V0，从此顶点有路径可以到达图 中其它所有顶点，则称此有向图 为有根的图，V0称作图的根 „ 树、森林

连通图 连通分支或者连通分量 对无向图G=(v,E)而言,如 无向图的最大连通子图 果从V1到V2有一条路径(从V2 ■强连通分支(强连通分量) 到V1也一定有一条路径),则称 V1和v2是连通的 (connected) ■强连通 网络 自由树( free tree) 带权的连通图 ■不带有简单回路的无向图,它是 连通的,并且具有V|-1条边 15 亡 权新有,轴彩光 回 62图的抽象数据类型 结点、边怎么表示? class Graph /图的ADT public ■结点:增?、删、查?、改 int VerticesNumo;∥/返回图的顶点个数 int EdgesNum();//返回图的边教 ■边:增、删、查?、改 /返回与顶点 onevertex相关联的第一条边 Edge FirstEdge(int onevertex); /返回与边 PreEdge有相同关联顶点 one vertex的 /下一条边 Edge NextEdge(Edge preEdge); 值惠单

3 北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 连通图 „ 对无向图G=（V，E）而言，如 果从V1到V2有一条路径（从V2 到V1也一定有一条路径），则称 V1和V2是连通的 （connected） „ 强连通 北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 连通分支或者连通分量 „ 无向图的最大连通子图 „ 强连通分支（强连通分量） v0 v5 北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 网络 „ 带权的连通图 北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 自由树（free tree） „ 不带有简单回路的无向图，它是 连通的，并且具有|V|-1条边 北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 6.2 图的抽象数据类型 „ 结点、边怎么表示？ „ 结点：增？、删、查?、改 „ 边：增、删、查?、改 北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 class Graph{ //图的ADT public: int VerticesNum(); //返回图的顶点个数 int EdgesNum(); //返回图的边数 //返回与顶点oneVertex相关联的第一条边 Edge FirstEdge(int oneVertex); //返回与边PreEdge有相同关联顶点oneVertex的 //下一条边 Edge NextEdge(Edge preEdge);

/添加一条边 bool setEdge(int from Vertex, int toVertex, int 63图的存储结构 bool delEdge(int fromVertex, int toVertex); 返回TRUE,否则返回 FALSE 令631图的相邻矩阵 bool IsEdge(Edge oneEdge); //返回边 one Edgel的始点 ( adjacency matrix)表示法 /返回边 one Edge的终点 令632图的邻接表( adjacency vErtex(Edge oneEdge); //返回边 oneEdge的权 list)表示法 int Weight(Edge oneEdge); 邻接多重表( adjacency multilist) 相邻矩阵 01000 表示顶点间相邻关系的矩阵。 若G是一个具有n个顶点的图,则G的 10001 相邻矩阵是如下定义的nxn矩阵 A7=01010 A[ij=1,若(V,V)(或<V,v>) 是图G的边 10000 ^ 00010 图G的边 相邻矩阵的空间代价为e(n2) 亡 宜大息单 权新有,轴彩光 632图的邻接表 ( adjacency list)表示法 3040 15 = 0406 15060 值惠单

4 北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 //添加一条边 bool setEdge(int fromVertex,int toVertex,int weight); //删一条边 bool delEdge(int fromVertex,int toVertex); //如果oneEdge是边则返回TRUE，否则返回FALSE bool IsEdge(Edge oneEdge); //返回边oneEdge的始点 int FromVertex(Edge oneEdge); //返回边oneEdge的终点 int ToVertex(Edge oneEdge); //返回边oneEdge的权 int Weight(Edge oneEdge); }; 北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 6.3 图的存储结构 „ 6.3.1 图的相邻矩阵 （adjacency matrix）表示法 „ 6.3.2 图的邻接表（adjacency list）表示法 „ 邻接多重表(adjacency multilist) 表示法 北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 „ 相邻矩阵 „ 表示顶点间相邻关系的矩阵。 „ 若G是一个具有n个顶点的图，则G的 相邻矩阵是如下定义的n×n矩阵： A[i,j]=1，若（Vi ，Vj ）（或<Vi ，Vj>） 是图G的边； A[i,j]=0，若（Vi ，Vj ）（或<Vi ，Vj >） 不是图G的边。 „ 相邻矩阵的空间代价为Θ(n2) 北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 A7= 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ 北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 A4= 3 15 3 4 4 0 0 0 0 0 0 0 0 6 15 6 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ 北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 6.3.2 图的邻接表 （adjacency list）表示法 G6 G7

无向图G6邻接表表示 有向图的邻接表 →4 →6 回|G的出边表 G的入边表 邻接多重表( adjacency 图的邻接表空间代价 multilist) n个顶点m条边的无向图 把鉍替表素示中尖春同一条边的两 需用(n+2m)个存储单元 ■图的每条边只用一个多重表表目表 n个顶点m条边的有向图 需用(n+m)个存储单元 包括此边的两个顶点的序号 与器 项点希笑联下个禁 无向图G6的邻接多重表 有向图邻接多重表 在顶点表中设计两个指针 2NN边(v2) 个指向以此顶点为始点的第一条边 指向以此项点为终点的第一条边 边表 3w个为[4N边,v 个指针指向始点与本边始点相同的 第二个指针指向终点与本边终点相同的下 23N边(2.V N24边(:,v 穀仅很聋棗墨个韃得猾碧商閣装 5

5 北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 无向图G6邻接表表示 北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 有向图的邻接表 G7的出边表 G7的入边表 北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 图的邻接表空间代价 „ n个顶点m条边的无向图 „ 需用(n+2m)个存储单元 „ n个顶点m条边的有向图 „ 需用(n+m)个存储单元 北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 邻接多重表(adjacency multilist) „ 把邻接表表示中代表同一条边的两 个表目合为一个表目 „ 图的每条边只用一个多重表表目表 示 „ 包括此边的两个顶点的序号 „ 两个指针（一个指针指向与第一个顶 点相关联的下一条边，另一个指针指 向与第二个顶点相关联的下一条边） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 无向图G6的邻接多重表 北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 有向图邻接多重表 „ 在顶点表中设计两个指针 „ 第一个指向以此顶点为始点的第一条边 „ 第二个指向以此顶点为终点的第一条边 „ 边表 „ 第一个指针指向始点与本边始点相同的下一 条边 „ 第二个指针指向终点与本边终点相同的下一 条边 „ 故仅用表中第一个链便得到有向图的出边 表，仅用第二个链便得到有向图的入边表