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

主要内容 数据结构与算法 令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)〔着 对有向图,则使得 va>, 和构成环 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)（若 对有向图，则使得， ，…， ）都在E中 „ 简单路径（simple path） „ 路径长度（length） Vp Vq 北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 回路（cycle，也称为环） „ 无向图中，如果两个结点之间有平行边， 容易让人误看作“环”） „ 路径长度大于等于3 „ 有向图两条边可以构成环，例如 和 构成环 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)(或) 是图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 ）（或） 是图G的边； A[i,j]=0，若（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 有向图邻接多重表 „ 在顶点表中设计两个指针 „ 第一个指向以此顶点为始点的第一条边 „ 第二个指向以此顶点为终点的第一条边 „ 边表 „ 第一个指针指向始点与本边始点相同的下一 条边 „ 第二个指针指向终点与本边终点相同的下一 条边 „ 故仅用表中第一个链便得到有向图的出边 表，仅用第二个链便得到有向图的入边表

有向图G7的邻接多重表 N2边w,v 邻接多重表不太常用 N[2NN边(w,v 在以处理图的边为主,要求每条 N[2边v,v 边处理一次的实际应用中可能有 N[4L边v,v 用 N[边(.vs N□22xL边v NT4边wv 64图的周游 森林的周游 ◇6.4.1深度优先搜索 ■按深度方向周游 64.2广度优先搜索 先根次序 643拓扑排序 后根次序 ■按广度方向周游 宽度优先周游 层次周游 亡 权新有,轴彩光 64图的周游( graph traversaL) 图周游的考虑 给出一个图G和其中任意一个顶 ■从一个顶点出发,试探性访问其余 点v 顶点,同时必须考虑到下列情况: ■从v出发系统地访问G中所有的 从一顶点出发,可能不能到达所有其 顶点,每个顶点访问一次 它的顶点,如非连通图; ■也有可能会陷入死循环,如存在回路 的图。 值惠单 6

6 北京大学信息学院 ©版权所有，转载或翻印必究 Page 31 有向图G7的邻接多重表 北京大学信息学院 ©版权所有，转载或翻印必究 Page 32 „ 邻接多重表不太常用 „ 在以处理图的边为主，要求每条 边处理一次的实际应用中可能有 用 北京大学信息学院 ©版权所有，转载或翻印必究 Page 33 6.4 图的周游 „ 6.4.1 深度优先搜索 „ 6.4.2 广度优先搜索 „ 6.4.3 拓扑排序 北京大学信息学院 ©版权所有，转载或翻印必究 Page 34 森林的周游 „ 按深度方向周游 „ 先根次序 „ 后根次序 „ 按广度方向周游 „ 宽度优先周游 „ 层次周游 北京大学信息学院 ©版权所有，转载或翻印必究 Page 35 6.4 图的周游（graph traversal） „ 给出一个图G和其中任意一个顶 点V0 „ 从V0出发系统地访问G中所有的 顶点，每个顶点访问一次 北京大学信息学院 ©版权所有，转载或翻印必究 Page 36 图周游的考虑 „ 从一个顶点出发，试探性访问其余 顶点，同时必须考虑到下列情况： „ 从一顶点出发，可能不能到达所有其 它的顶点，如非连通图； „ 也有可能会陷入死循环，如存在回路 的图

士 图的周游算法框架 解决办法 //图的周游算法的实现 Graph& G ■为图的每个顶点保留一个标志位 //对图所有顶点的标志位进行初始化 (mark bit)i ■算法开始时,所有顶点的标志位置 /检查图的所有项点是否被标记过,如果未被标记, 则从该未被标记的顶点开始继续周游 在周游的过程中,当某个顶点被访问 / do traverse函数用湅度优先或者广度优先 for(int i=O;i<G. VerticesNum(; i++) 时,其标志位就被标记为已访问。 if(G. Mark[O]== UNVISITED) o_traverse(G, i); 盟hm 图的生成树 641深度优先搜索 图的所有顶点加上周游过程中经 浮度y签慈想 pth-first searc,向称 过的边所构成的子图称作图的生 莴的卖应V,然后访间该顶点邻热到的未被访 成树 再从v出发递归地按照深度优先的方式周游 图的生成森林 通,百楚牌帮蔑言闻 再从W出发遵归地按照深度优先的方式周游 项着舒何蔑譆的顶点都没有本被访间的 深度优先搜家树( depth- first search tree) 亡 权新有,轴量 从一个顶点出发的深度优先搜索 void dfs( Graph& G, int V)∥/深度优先搜索算法实现 G. Mark[v= VISITED;//访问顶点v,并标记其标志位 /访问V邻接到的未被访问过的顶点,并递归地按照 G. Mark[G. ToVerticese)]== UNVISITED DFS(G, G. ToVertices(e)); Postvisit(G, V //访问 深度优先搜索的顺序是a,b,c,f,d,e,g

7 北京大学信息学院 ©版权所有，转载或翻印必究 Page 37 „ 解决办法 „ 为图的每个顶点保留一个标志位 （mark bit）； „ 算法开始时，所有顶点的标志位置 零； „ 在周游的过程中，当某个顶点被访问 时，其标志位就被标记为已访问。 北京大学信息学院 ©版权所有，转载或翻印必究 Page 38 图的周游算法框架 //图的周游算法的实现 void graph_traverse(Graph& G){ //对图所有顶点的标志位进行初始化 for(int i=0;i<G.VerticesNum();i++) G.Mark[i]=UNVISITED; //检查图的所有顶点是否被标记过，如果未被标记， //则从该未被标记的顶点开始继续周游 //do_traverse函数用深度优先或者广度优先 for(int i=0;i<G.VerticesNum();i++) if(G.Mark[i]== UNVISITED) do_traverse(G, i); } 北京大学信息学院 ©版权所有，转载或翻印必究 Page 39 图的生成树 „ 图的所有顶点加上周游过程中经 过的边所构成的子图称作图的生 成树 „ 图的生成森林 北京大学信息学院 ©版权所有，转载或翻印必究 Page 40 6.4.1 深度优先搜索 „ 深度优先搜索（depth-first search，简称 DFS）基本思想 „ 访问一个顶点V，然后访问该顶点邻接到的未被访 问过的顶点V’ „ 再从V’出发递归地按照深度优先的方式周游 „ 当遇到一个所有邻接于它的顶点都被访问过了的顶 点U时，则回到已访问顶点序列中最后一个拥有未 被访问的相邻顶点的顶点W „ 再从W出发递归地按照深度优先的方式周游 „ 最后，当任何已被访问过的顶点都没有未被访问的 相邻顶点时，则周游结束 „ 深度优先搜索树（depth-first search tree） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 41 深度优先搜索的顺序是a，b，c，f，d，e，g 北京大学信息学院 ©版权所有，转载或翻印必究 Page 42 从一个顶点出发的深度优先搜索 void DFS(Graph& G, int V){ //深度优先搜索算法实现 G.Mark[V]= VISITED; //访问顶点V，并标记其标志位 PreVisit(G, V); //访问V for(Edge e=G. FirstEdge(V); G.IsEdge(e); e=G. NextEdge(e)) //访问V邻接到的未被访问过的顶点，并递归地按照 //深度优先的方式进行周游 if(G.Mark[G. ToVertices(e)]== UNVISITED) DFS(G, G. ToVertices(e)); PostVisit(G, V); //访问V }

64.2广度优先搜索 度先嚮紊g5本想 访问顶点v 然后访问v邻接到的所有未被访问过的顶点 袋剧;,Ya邻款到的所有 如此进行下去,直到访问遍所有的项点。 度优先搜索树( breadth- first earch tree) 广度优先搜索的顺序是a,b,d,e,f,c,g Void Bfs( Graph& G, intRO厂度优先囊 //初始化广度优先周游要用到的 sit(G, V: Qpush(V) 图搜索的时间复杂度 y()认/如果队列仍然有元素 pop(;//顶部元 DFS对每一条边处理一次(无向图的每条 //将与该点相邻的每一个未访问点都入队 for(Edge e=G. FirstEdge(v) 边从两个方向处理),每个顶点访问一次 G. IsEdge(e);e=G. NextEdge(e)) 采用邻接表表示时,有向图总代价为 if (G. Mark[G. ToVertex(e)] e(V|+|El),无向图为e(|V|+2|E|) UNVISITED)t G. Mark[G. ToVertex(e)]=VISITED; 采用相邻矩阵表示时,处理所有的边需要 sit(G, G. ToVertex(e)); e(|V|2)的时间,所以总代价为 Q- push(G. ToVertex(e)}//入队 e(|V|+|V|2)=e(|V|2) }∥/ End of if 1// End of while ■BFs与DF⑤的时间复杂度相同 E】// End of Bfs 亡 宜大息单 权新有,轴彩光 643拓扑排序(引子) 拓扑排序图例 课程名称 先修课程 程序设计 生 高散数学 课 程 的 d)安 计算机原理 排 值惠单

8 北京大学信息学院 ©版权所有，转载或翻印必究 Page 43 6.4.2 广度优先搜索 „ 广度优先搜索（breadth-first search，简称BFS）的基本思想 „ 访问顶点V0， „ 然后访问V0邻接到的所有未被访问过的顶点 V01，V02，…V0i， „ 再依次访问V01，V02，…V0i邻接到的所有 未被访问的顶点， „ 如此进行下去，直到访问遍所有的顶点。 „ 广度优先搜索树（breadth-first search tree） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 44 广度优先搜索的顺序是a，b，d，e，f，c，g 北京大学信息学院 ©版权所有，转载或翻印必究 Page 45 void BFS(Graph& G, int V){ //广度优先搜索 //初始化广度优先周游要用到的队列 using std::queue; queue Q; //访问顶点V，并标记其标志位， V入队 G.Mark[V]= VISITED; Visit(G, V); Q.push(V); while(!Q.empty()) {//如果队列仍然有元素 int V=Q.front(); Q.pop(); //顶部元素 出队 //将与该点相邻的每一个未访问点都入队 for(Edge e=G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e)) if (G.Mark[G.ToVertex(e)] == UNVISITED) { G.Mark[G.ToVertex(e)]=VISITED; Visit(G, G.ToVertex(e)); Q.push(G.ToVertex(e)); //入队 } // End of if } // End of while } // End of BFS 北京大学信息学院 ©版权所有，转载或翻印必究 Page 46 图搜索的时间复杂度 „ DFS对每一条边处理一次（无向图的每条 边从两个方向处理），每个顶点访问一次 „ 采用邻接表表示时，有向图总代价为 Θ(|V|+|E|)，无向图为Θ(|V|+2|E|) „ 采用相邻矩阵表示时，处理所有的边需要 Θ(|V|2)的时间 ，所以总代价为 Θ(|V|+|V|2)= Θ(|V|2) „ BFS与DFS的时间复杂度相同 北京大学信息学院 ©版权所有，转载或翻印必究 Page 47 6.4.3 拓扑排序（引子） 课程代号 课程名称 先修课程 C1 高等数学 C2 程序设计 C3 离散数学 C1，C2 C4 数据结构 C2，C3 C5 算法语言 C2 C6 编译技术 C4，C5 C7 操作系统 C4，C9 C8 普通物理 C1 C9 计算机原理 C8 北京大学信息学院 ©版权所有，转载或翻印必究 Page 48 拓扑排序图例 学 生 课 程 的 安 排 图

拓扑排序问题描述 拓扑序列定义 先决条件问题 拓扑序列 ■拓扑排序( topological sort) 对于有向无环图G=(v,E),v 将一个有向无环图中所有顶点在 里顶点的线性序列称作一个拓扑 不违反先决条件关系的前提下排 序列,如果该顶点序列满足: 成线性序列的过程称为拓扑排序 若在有向无环图G中从顶点V到有 条路径,则在序列中顶点v必在顶 点V之前 643拓扑排序方法 队列方式实现的拓扑排序 任何无环有向图(DAG),其顶点都 oid Topsortby Queue( Graph&G)t 可以排在一个拓扑序列里,其拓扑排 for(int i=O;i Q /初始化队列 点且输出之 for(i=O; i<G. VerticesNum(; i++) (2)从图中删掉此顶点及其所有的出边 Q- push() //图中入度为0的项点入队 (3)回到第(1)步继续执行 亡 宜大息单 权新有,轴彩光 while(! Q empty){//如果队列中还有图顶点 int V=Q. fronto //顶部元亲 个顶点出队 //访问该顶点 G. MarkMV]=VISITED: for(i=0; i<G.VerticesNum O; i++) //边e的终点的入度值减1 f(G. Mark[]==UNVISITED) for( Edge e= G. FirstEdge(v) IsEdge(e);e=G. NextEdge(e)) cout<<“图有环;//图有环 GIndegree[G.ToVertex(e f(G Indegree[G. ToVertex(e)]==0) f / End of Topsortby Queued Q- push( G. ToVertex(e);//入度为0的点入队

9 北京大学信息学院 ©版权所有，转载或翻印必究 Page 49 拓扑排序问题描述 „ 先决条件问题 „ 拓扑排序（topological sort） „ 将一个有向无环图中所有顶点在 不违反先决条件关系的前提下排 成线性序列的过程称为拓扑排序 北京大学信息学院 ©版权所有，转载或翻印必究 Page 50 拓扑序列定义 „ 拓扑序列 „ 对于有向无环图G=（V，E），V 里顶点的线性序列称作一个拓扑 序列，如果该顶点序列满足： „ 若在有向无环图G中从顶点Vi 到Vj 有 一条路径，则在序列中顶点Vi 必在顶 点Vj 之前 北京大学信息学院 ©版权所有，转载或翻印必究 Page 51 6.4.3 拓扑排序方法 „ 任何无环有向图（DAG），其顶点都 可以排在一个拓扑序列里，其拓扑排 序的方法是： „ （1）从图中选择任意一个入度为0的顶 点且输出之 „ （2）从图中删掉此顶点及其所有的出边 „ （3）回到第（1）步继续执行 北京大学信息学院 ©版权所有，转载或翻印必究 Page 52 队列方式实现的拓扑排序 void TopsortbyQueue(Graph& G) { for(int i=0;i Q; //初始化队列 for(i=0; i<G.VerticesNum(); i++) { if (G.Indegree[i]==0) Q.push(i); //图中入度为0的顶点入队 } 北京大学信息学院 ©版权所有，转载或翻印必究 Page 53 while (!Q.empty()) { //如果队列中还有图顶点 int V=Q.front(); //顶部元素 Q.pop(); //一个顶点出队 Visit(G, V); //访问该顶点 G.Mark[V]=VISITED; //边e的终点的入度值减1 for (Edge e= G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e)) { G.Indegree[G.ToVertex(e)]--; if(G.Indegree[G.ToVertex(e)]==0) Q.push(G.ToVertex(e)); //入度为0的点入队 } } 北京大学信息学院 ©版权所有，转载或翻印必究 Page 54 for(i=0; i<G.VerticesNum(); i++) if(G.Mark[i]==UNVISITED) { cout << “图有环”; //图有环 break; } } // End of TopsortbyQueue()

深度优先搜索实现的拓扑排序 int* Topsortby DFS( Graph&G)【/结果是顺倒的 for(inti=0;i=0;-)//逆序输出 置逆,拓扑序列为 Visit(G, result[]) eturn result; C2,C5c1,c3C4,c6C8,C9,C7 //深度优先搜索方式实现拓扑排序 拓扑排序递归函数 ISITED)t /图有环 psort( Graph& G, int V, int *result, int& tag CIRCLED; return; G. MarkMV= VISITED; G. Mark[V]=VISITED; G SeDge(e);e=G. NextEdge(e))t /访问V邻接到的所有未被访问过的顶 //访问V部接到的所有未被访问过的 if(. Mark[G. ToVertex(e)]== UNVISITED) if((.Mark[G. ToVertex(e)]l= PUSHED) F-topsort(G, G.ToVertex(e), result, index); Do topsort Circle(G, G.ToVertex(e), res 相当于后处理 lex, tag) sult[index++]=V; G. Mark[V= PL 亡 权新有,轴彩光 //深度优先搜索方式实现的拓扑排序结果是颠倒的 void Topsortby DFs_ Circle(Graph&G) /对图所有顶点的标志位进行初始化 拓扑排序的时间复杂度 ntIEo;K =0;-)∥/逆序輪出 隻理染看金穀鍍還出,从而可能 Visit(G, result[D; 值惠单 10

10 从左到右观察后处理型深度 优先拓扑排序演示动画. c1 c2 c8 c9 c c5 3 c7 c4 c6 置逆，拓扑序列为： C2,C5,C1,C3,C4,C6,C8,C9,C7 北京大学信息学院 ©版权所有，转载或翻印必究 Page 56 深度优先搜索实现的拓扑排序 int *TopsortbyDFS(Graph& G) { //结果是颠倒的 for(int i=0; i=0;i--) //逆序输出 Visit(G, result[i]); return result; } 北京大学信息学院 ©版权所有，转载或翻印必究 Page 57 void Do_topsort(Graph& G, int V, int *result, int& index) { G.Mark[V] = VISITED; for (Edge e = G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e)) { //访问V邻接到的所有未被访问过的顶点 if(G.Mark[G.ToVertex(e)]== UNVISITED) Do_topsort(G, G.ToVertex(e), result, index); } // 相当于后处理 result[index++]=V; } 拓扑排序递归函数 北京大学信息学院 ©版权所有，转载或翻印必究 Page 58 //深度优先搜索方式实现拓扑排序 void Do_topsort_Circle(Graph& G, int V,int *result,int &index, int& tag) { if(G.Mark[V]== VISITED) { cout=0;i--) //逆序输出 Visit(G, result[i]); } 北京大学信息学院 ©版权所有，转载或翻印必究 Page 60 拓扑排序的时间复杂度 „ 与图的深度优先搜索方式周游相同 „ 图的每条边处理一次 „ 图的每个顶点访问一次 „ 采用邻接表表示时，为Θ(|V|+|E|) „ 采用相邻矩阵表示时，为Θ(|V|2) „ 在有环的情况下会提前退出，从而可能 没处理完所有的边和顶点