浅谈强连通分量与拓扑排序的应用
浅谈强连通分量与拓扑排序的应用
浙江唐文斌摘要
强连通分量与拓扑排序是图论中最基础的算法之一。本文选取了两个简单但富有代表性的例子，说明这两个算法在一类图论问题中的应用。
[例一]Going from u to v or from v to u?1
给定一个有向图，问是否对于图中的任意两点u、v，总是存在u到v可达或者v到u （下文中将以a→b表示a到b可达）可达。图中点数不超过1000，边数不超过6000。
算法分析
题目描述很简单，我们最直观的想法就是求一个传递闭包，然后对于任意两点a、b判断是否a→b或者b→a。然而在本题中点数多达1000，传统的求传递闭包方法Floyd是行不通的。题目中的规模很小，似乎我们可以枚举起点s，并且从s开始对图进行一次宽度优先搜索，这样我们可以在O（N*（N+M））时间内求得传递闭包。似乎这个办法可行，但事实上，在本题中虽然规模小，但是数据组数高达200组，所以这个方法也是必然超时的。
我们抛开传递闭包，重新来看问题。题目中问是否对于任意两点都在至少一个方向上可达。那么如果两个点u、v，u→v且v→u，它们当然是符合要求的。所以我们第一个想法就是找到一个点集，该点集内所有点两两可达。由于其内部两两可达，所以我们可以将其缩成一个点，仅保留连向外界的边，并不会影响问题的本质。这个点集，就是强连通分量。所以我们的第一步操作就是：求图中所有的极大强连通分量，将每一个强连通分量缩成一个点，保留不同分量间的连边信息，得到一个新图。
我们对原图进行强连通分量缩点得到新图有什么好处呢？在这个过程中，我们将一些冗余信息进行了处理，得到的新图具有一个很重要的性质：无环（拓扑有序）。因为如果有环存在，那么这些环上的点都是互相可达的，所以它们应该同属于一个极大强连通分量，将被缩成一个点。所以我们现在的问题就是对于新图——一个拓扑有序的图，判断图中是否任意两点是否在至少一个方向上可达。
如果一个拓扑有序的图满足要求，那么它将拥有一些什么性质呢？我们先来看一些小规模的情况：
（1）如果图只有一个点，则必然满足条件
（2）如果图中包含两个点，那么必须从一个点到另一个点有边相连。不妨设为a→b （显然b到a不可达）。
（3）如果图中包含3个点，不妨设第三个为c。那么必须满足c→a或者b→c。
通过上面3个情况的观察，我们大致就有了一个猜想：
1Poj Monthly Special – Jiajia&Wind’s story , problem G (POJ2762)
[猜想]：拓扑图G若满足对于图中任意两点u、v均有u→v或者v→u，则必然存在一条通过所有点的链。
[证明]：设图中的节点数目为n。
当n=1时，图满足要求且包含长度为1的链。
当n=k > 1时，假设n=k-1时猜想成立，即任何满足条件的图都存在一条通过所有点的链。由于图G是拓扑有序的，所以我们总可以找到一个没有入度的点x，将点x删除之后不会影响图中其它点对之间的连通性。由于图G是满足要求的，而将x删除后其它点对间的连通性并没有被影响，则在G中删除点x后得到的图G'也满足要求。由假设知，G'中存在一条长度为n-1的链，不妨设这条链的起点为v。由于图G满足要求且x没有入度，所以x必须存在一条路径到达v。若x通过点y到达v，而v是一条长度为n-1的有向链的起点，则链上的v→y部分加上y→v部分就形成了一个圈，与题设G是拓扑有序的矛盾。故x到v直接有边相连，那么将x连到v的这条边加入原有路径中就得到了一条长度为n的链。
由归纳可知，对于任何一个满足条件的拓扑图G，均存在一条通过所有点的链。
问题至此，已经基本解决了。我们只需要对当前的新图寻找是否存在通过所有点的路。这个过程只需要DFS即可解决。求极大强连通分量的复杂度为O(N+M)，判断是否存在通过所有点的路的复杂度也为O(N+M)。所以总时间复杂度也是O(N+M)。至此问题被完美的解决。
[例二]Pipes in factory2
给定一个有向图G(V,E)，问最多能从G图中删去多少条边，且删了边之后图G的连通性不变。
规模：点数不超过1000，边数不超过10000。
注：关于题目
在附录中有原题的英文描述，而原题经过抽象就是上面所提到的一个图论问题。但我认为出题者想考察的并不是这个问题，而是一个另外的类似问题的解法。
如果上面提到的问题可以在多项式时间内解决，那么哈密顿回路问题可以也多项式时间内解决。试想一个有向图存在一个哈密顿回路，它的充要条件为图中任意两点都互相可达且可以删掉|E|-|V|条边且图的连通性不变。也就是说我们可以利用上述问题的解在多项式时间判定一个有向图是否存在哈密顿回路，更进一步，我们也可以利用上述问题的解构造出这条哈密顿回路。而众所周知，哈密顿回路目前仍然找不到确定性的多项式时间算法，所以上述问题也是不可解的。
所以我猜测，出题者想考察的问题应该是这样的：
给定一个有向图G(V,E)，我们可以改造这个图G中的连边得到新图G’，问图G’中至少要含有多少边，才能满足G’的连通性与图G一致。
2International Online Programming Contest 2006 , problem 2
算法分析
仍然是类似于上面一题的想法，我们先来看图G 中的每一个强连通分量123,,...k C C C C 。对于一个强连通分量i C ，我们如何对其进行改造，用最少的边得到相同的连通性呢？由于
一个强连通分量内的点之间是两两可达的，所以最优的方法就是让这个分量内的点构成一个环，即使用i C 条边（若i C =1，则不需要连边）。类似的，由于强连通分量内的点之间都
互相可达，所以我们可以把它们压缩成一个点，仅保留于外界的连边信息，问题本质不变。我们不妨设压缩之后的新图为G 0。所以现在的问题就是如何改造一个这个拓扑有序的图G 0，用最少的边得到相同的连通性。
由于图G 0是拓扑有序的，所以我们所要做的就是删除尽量多的无效边，使得仍然保留原有的拓扑序。
而一个拓扑有序的图中哪些边是没有必要的呢？如下图：
图中的红色边即为无效边，我们的目标就是找到所有这种无效边并且加以删除。 所谓的无效边，就是说对于现有的一条边u →v ，我们可以找到另一条通路不经过这条边从u 到v 。
那么我们就有一个很直观的想法就是不断尝试删无效边，随便找一条边，看看是否能删，如果能删就将其删除。这个方法看起来有点玄乎，但其实是正确的，我们来看下面一个性质：
[性质一] 假设有当前有两条可以删除的边，不妨设a →b 和u →v 。我们任意删一条边，不会导致另一条边变得不能删除。
证明：上述性质在普通有向图中显然是不成立的，看下面这个例子：
显然上图中的两条红色边可以一起被删除。但是如果我先删了蓝色边，则两条红边
都不能删了。
但是请注意，我们现在面对的图并不是一般的有向图，而是一个拓扑有序的图。删
了一条边a →b 之后导致另一条边u →v 不能删，意味着什么呢？
由于删去a →b 之后使得u →v 不能删，而原本u 到v 存在着第二条通路现在不存在
了，所以说a →b 这条边是u 到v 第二条通路上的一部分。因为a →b 可以被删除，所以
a到b也存在着另一条通路，那么两部分相接不就可以保证u到v仍然存在第二条通路了么？除非如上图所示，即u→v也是a到b的另一条通路上的一部分。而这么一来，a 可以到达u，u可以到达a，这就与我们的题设——图拓扑有序矛盾了。
所以我们删除任何一条边，都不会影响到另一条本来可以本删除的边。
有了性质一，我们就可以直接用上面提到的朴素算法求得解答。但是上面的方法依次枚举每一条边，然后检查去掉这条边是否仍然连通，时间复杂度较大，为2
O M。
()为了优化这个算法，我们不妨来规定一个检查边的顺序。我们将图G0进行拓扑排序。建立一个空图G’，按照逆拓扑序，每次加入一个点u和从u出发的所有有向边。然后检查当前加入的边集。对于当前一条边u→v，看看是否可以将其删除，如果可以删除那就删。显然这样做仍然是2
O M的，尽管因为检查的边变少常系数有些变化，但并没有影响算法
()
的时间复杂度。不过按照这个顺序处理，我们就可以进行一些优化。
我们是按照逆拓扑序加点和边，也就是说当前G’中的两个点a、b的连通情况，不可能与尚未添加的点c有关系。所以我们可以维护一个局部的传递闭包，记录每两个点之间的连通信息。每次我们加了点u之后，判断一条边u→v是否可以被删除只需要检查是否存在一个点x，满足u到x有边存在且x可以到达v。对于每一条边的检查，最多是()
O N的。检查所有边之后，我们可以从u开始遍历一次，最多()
的时间就能得到从u出发到
O N M
达其他点的连通信息了。所以总时间复杂度不超过()
O NM。比上面的方法优了很多。
到这里，问题已经基本解决。不过大家也可以发现，本题中不能被删的那些边与我们熟知的“桥”很类似，所以我们也许可以通过类似求桥的方法来进行求解，从而得到更优的算法。限于篇幅，这里就不再赘述。
总结
求有向图的强连通分量是一种非常常用的手段，在一个强连通分量内的点之间都是互相可达的，所以我们往往可以把它们看作一个点进行处理。而这样的一种变换，就把一些冗余信息压缩掉了，从而使得问题变得更加清晰明了，也更容易分析其本质。而经过压缩后的新图都是拓扑有序的，再对这个图的求拓扑顺序，就能方便地解决很多问题。
附录
p2.pdf
图的连通性总结
图的连通性总结 boboo 目录 1.图的遍历及应用 1.1.DFS遍历 1.2.DFS树的边分类 1.3.DFS树的性质 1.4.拓补排序 1.5.欧拉回路 2.无向图相关 2.1求割顶 2.2求图的桥 2.3求图的块 3.有向图相关 3.1求强连通分量（SCC划分） 3.2求传递闭包 4.最小环问题
一、图的遍历及应用 1.1 DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。 DFS对图进行染色， 白色：未访问； 灰色：访问中（正在访问它的后代）； 黑色：访问完毕 一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。 -发现时间D[v]:变灰的时间 -结束时间f[v]:变黑的时间 -1<=d[v] 拓扑排序 摘要 拓扑排序是求解网络问题所需的主要算法。管理技术如计划评审技术和关键路径法都应用这一算法。通常，软件开发、施工过程、生产流程、程序流程等都可作为一个工程。一个工程可分成若干子工程，子工程常称为活动。活动的执行常常伴随着某些先决条件，一些活动必须先于另一活动被完成。利用有向图可以把这种领先关系清楚地表示出来。而有向图的存储可以用邻接表和逆邻接表做存储结构来实现。最后用拓扑排序表示出来就可以了。拓扑排序有两种，一种是无前趋的顶点优先算法，一种是无后继的顶点优先算法，后一种的排序也就是逆拓扑排序。 关键词：拓扑排序；逆拓扑排序；有向图；邻接表；逆邻接表 THE OPERATOR ORDERING PROBLEM IN QUANTUM HAMITONIAN FOR SOME CONSTRAINT SYSTEMS ABSTRACT Topological sort is the main method to solve network problems. Management techniques such as PERT and critical path method is the application of this algorithm. Typically, software development, the construction process, production processes, procedures, processes, etc. can be used as a project. A project can be divided into several sub-projects, often referred to as sub-project activities. The implementation of activities often associated with certain preconditions, some of the activities must be completed before another activity. Use has lead to the relationship of this figure can be expressed clearly. While storage can be used to map the inverse adjacency list and adjacency table to do storage structures. Finally, topological sort that out on it. Topological sort, there are two, one is the predecessor of the vertex without first algorithm, a successor of the vertex is no priority algorithm, the latter sort is the inverse topological sort. Key words:topological sort; inverse topological; have to figure; adjlink; inverse adjlink 第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。 A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 拓扑排序 [基本要求] 用邻接表建立一个有向图的存储结构。利用拓扑排序算法输出该图的拓扑排序序列。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意有向是不需要对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，几乎和图的创建一样，图的顶点定义时加入int indegree，关键在于indegree 的计算，而最好的就是在创建的时候就算出入度，（没有采用书上的indegree【】数组的方法，那样会增加一个indegree算法，而是在创建的时候假如一句计数的代码(G.vertices[j].indegree)++;）最后调用拓扑排序的算法，得出拓扑序列。 [程序代码] 头文件： #define MAX_VERTEX_NUM 30 #define STACKSIZE 30 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; typedef int InfoType; typedef int Status; typedef int SElemType; /* 定义弧的结构*/ typedef struct ArcNode{ int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边的指针*/ InfoType info; /*该弧相关信息的指针*/ 实验报告 课程名称数据结构 实验项目名称有向图的强连通分量 班级与班级代码14计算机实验班 实验室名称（或课室）实验楼803 专业计算机科学与技术 任课教师 学号： 姓名： 实验日期：2015年12 月03 日 广东财经大学教务处制 姓名实验报告成绩 评语： 指导教师（签名） 年月日说明：指导教师评分后，实验报告交院（系）办公室保存。 一、实验目的与要求 采用邻接表存储的有向图。 二、实验内容 （1）创建N个节点的空图 DiGraph CreateGraph(int NumVertex)//创建一个N个节点的空图 { DiGraph G; G = malloc( sizeof( struct Graph ) ); if( G == NULL ) FatalError( "Out of space!!!" ); G->Table = malloc( sizeof( struct TableEntry ) * NumVertex ); if( G->Table == NULL ) FatalError( "Out of space!!!" ); G->NumVertex = NumVertex; G->NumEdge = 0; int i; for (i=0;i 7.4.1无向图的连通分量和生成树。 void DFSForest(Graph G,CSTree &T) //建立无向图G的深度优先生成森林的 //（最左）孩子（右）兄弟链表T。 { T=NULL; for(v=0;v 数据结构课程设计 设计说明书 有向图拓扑排序算法的实现 学生姓名 学号 班级 成绩 指导教师魏佳 计算机科学与技术系 2010年2月22日 数据结构课程设计评阅书 注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。 课程设计任务书 2010—2011学年第二学期 专业：信息管理与信息系统学号：姓名： 课程设计名称：数据结构课程设计 设计题目：有向图拓扑排序算法的实现 完成期限：自2011 年 2 月22 日至2011 年 3 月 4 日共 2 周 设计内容： 用C/C++编写一个程序实现有向图的建立和排序。要求建立有向图的存储结构，从键盘输入一个有向图，程序能够自动进行拓扑排序。 设计要求: 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架； 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚； 5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析； 7）编写课程设计报告； 以上要求中前三个阶段的任务完成后，先将设计说明数的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。 指导教师（签字）：教研室主任（签字）： 批准日期：2011年2月21 日 《数据结构》实验报告 实验内容：（一）判断一个图有无回路 （二）求一个无向图G的连通分量的个数 一、目的和要求（需求分析）： 1、了解图的定义和图的存储结构。 2、熟悉掌握图的邻接矩阵和邻接表。 3、理解图的遍历算法---深度优先搜索和广度优先搜索。 4、学会编程处理图的连通性问题。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 判断一个图有无回路： 在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。 在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的顶点。如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。 无向图则可以转化为： 如果存在回路，则必然存在一个子图，是一个回路。因此回路中所有定点的度>=2。 第一步：删除所有度<=1的顶点及相关边，并将另外与这些边相关的其它顶点的度减1。 第二步：将度数变为1的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。 如果最后还有未删除的顶点，则存在回路，否则没有。 求一个无向图G的连通分量的个数： 用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraph G)调用DFS次数进行统计，其结果便为无向图中连通分量个数。 三、调试和运行程序过程中产生的问题及采取的措施： 在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块 void DFSTraverse(ALGraph G)先于void DFS(ALGraph G,int v)， 而void DFSTraverse(ALGraph G)内调用了DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。 四、源程序及注释： 求强连通分量的Kosaraju算法和Tarjan算法的比较 一、定义 在有向图中，如果两个顶点vi,vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图的每两个顶点都强连通，则称该有向图是一个强连通图。非强连通的有向图的极大强连通子图，称为强连通分量(strongly connected components)。 而对于一个无向图，讨论强连通没有意义，因为在无向图中连通就相当于强连通。 由一个强连通分量内的所有点所组成的集合称为缩点。在有向图中的所有缩点和所有缩点之间的边所组成的集合称为该有向图的缩图。 例子： 原图： 缩图： 上面的缩图中的 缩点1包含：1、2,；缩点2包含：3； 缩点3包含：4；缩点4包含：5、6、7。 二、求强连通分量的作用 把有向图中具有相同性质的点找出来，形成一个集合（缩点），建立缩图，能够方便地进行其它操作，而且时间效率会大大地提高，原先对多个点的操作可以简化为对它们所属的缩点的操作。 求强连通分量常常用于求拓扑排序之前，因为原图往往有环，无法进行拓扑排序，而求强连通分量后所建立的缩图则是有向无环图，方便进行拓扑排序。 三、Kosaraju算法 时间复杂度：O（M+N）注：M代表边数，N代表顶点数。 所需的数据结构：原图、反向图（若在原图中存在vi到vj的有向边，在反向图中就变成为vj到vi的有向边）、标记数组（标记是否遍历过）、一个栈（或记录顶点离开时间的数组）。 算法描叙： 步骤1：对原图进行深度优先遍历，记录每个顶点的离开时间。 步骤2：选择具有最晚离开时间的顶点，对反向图进行深度优先遍历，并标记能够遍历到的顶点，这些顶点构成一个强连通分量。 步骤3：如果还有顶点没有遍历过，则继续进行步骤2，否则算法结束。 hdu1269（Kosaraju算法）代码： #include 有向图的强连通分量 分类：C/C++程序设计2009-04-15 16:50 2341人阅读评论(1) 收藏举报最关键通用部分：强连通分量一定是图的深搜树的一个子树。 一、Kosaraju算法 1.算法思路 基本思路： 这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图G T。(步骤1)先用对原图G进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是E AB存在于反图G T)，能遍历到的顶点就是一个强连通分量。余下部分和 原来的森林一起组成一个新的森林，继续步骤2直到没有顶点为止。7 改进思路： 当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于G T来说)到其他树上的 呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于G T来说)就可以了。每次深搜都得到一个强连通分量。 隐藏性质: 分析到这里，我们已经知道怎么求强连通分量了。但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗？这就是Kosaraju算法的一个隐藏性质。 求强连通分量的tarjan算法 强连通分量：是有向图中的概念，在一个图的子图中，任意两个点相互可达，也就是存在互通的路径，那么这个子图就是强连通分量。（如果一个有向图的任意两个点相互可达，那么这个图就称为强连通图）。 如果u是某个强连通分量的根，那么： （1）u不存在路径可以返回到它的祖先。 （2）u的子树也不存在路径可以返回到u的祖先。 ?例如： ?强连通分量。在一个非强连通图中极大的强连通子图就是该图的强连通分量。比如图中子图{1,2,3,5}是一个强连通分量，子图{4}是一个强连通分量。 tarjan算法的基础是深度优先搜索，用两个数组low和dfn，和一个栈。low数组是一个标记数组，记录该点所在的强连通子图所在搜索子树的根节点的dfn值，dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。根据以下几条规则，经过搜索遍历该图和对栈的操作，我们就可以得到该有向图的强连通分量。 算法规则： ?数组的初始化：当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。 ?堆栈：每搜索到一个点，将它压入栈顶。 ?当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’不在栈中，p 的low值为两点的low值中较小的一个。 ?当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个。 ?每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low 值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。 ?继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。 算法伪代码： tarjan(u) { DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (！dfn[v]) // 如果节点v未被访问过 { tarjan(v) // 继续向下找 Low[u] = min(Low[u], Low[v]) } else if (v in S) // 如果节点v还在栈内 Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 do{ v = S.pop // 将v退栈，为该强连通分量中一个顶点}while(u == v); } 演示算法流程； 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 拓扑排序 一问题描述 本次课程设计题目是：编写函数实现图的拓扑排序 二概要设计 1.算法中用到的所有各种数据类型的定义 在该程序中用邻接表作为图的存储结构。首先，定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。 拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。 2.各程序模块之间的层次调用关系 第一部分，void CreatGraph(ALGraph *G)函数构建图，用邻接表存储。这个函数没有调用函数。 第二部分，void TopologicalSort(ALGraph *G)输出拓扑排序函数，这个函数首先调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1];然后设置了一个辅助栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不为空时，调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegree[k]--,当输出某一入度为0的顶点时，便将它从栈中删除。 第三部分，主函数，先后调用void CreatGraph(ALGraph *G)函数构建图、void TopologicalSort(ALGraph *G)函数输出拓扑排序实现整个程序。 3.设计的主程序流程 图的拓扑排序操作 一、实验内容 题目：实现下图的拓扑排序。 5 二、目的与要求 （一）目的 1、了解拓扑排序的方法及其在工程建设中的实际意义。 2、掌握拓扑排序的算法，了解拓扑排序的有向图的数据结构。 （二）要求 用C语言编写程序，实现图的拓扑排序操作。 三、设计思想 首先对有向图，我们采取邻接表作为数据结构。且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结点即没有前趋。 在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX（入度）为零，指针域NXET为空，每输入一条弧< J, K > 建立链表的一个结点，同时令k 的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。 在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。 （1）、查邻接表中入度为零的顶点，并进栈。 （2）、当栈为空时，进行拓扑排序。 （a）、退栈，输出栈顶元素V。 （b）、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。 （3）、若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。 四、具体算法设计 #include 拓扑排序 一、问题描述 在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。 二、基本要求 1、选择合适的存储结构，建立有向无环图，并输出该图； 2、实现拓扑排序算法； 3、运用拓扑排序实现对教学计划安排的检验。 三、算法思想 1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。 2、拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现。考虑到教学计划安排的实际情况，一般先学基础课（入度为零），再学专业课（入度不为零），与队列先进先出的特点相符，故采用队列实现。 3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入队列； 2)队列非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入队列； 4)重复2)、3)，直到队列为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。 4、要对教学计划安排进行检验，因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G)，大体思想为： 1)用户输入待检测的课程序列，将其存入数组； 2)检查课程序列下一个元素是否是图中的顶点（课程），是则执行3)，否则输出“课程XX不存在”并跳出； 3)判断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出； 4)该顶点的所有邻接点入度减一； 5)重复2)、3)、4)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。 《数据结构》实验报告 ◎实验题目:无向图的存储和遍历 ◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法； 2、掌握图的邻接表存储结构和深度优先遍历的非递归算法。 3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。 ◎实验内容：建立有10个顶点的无向图的邻接表存储结构，然后对其进行深度优先遍历，该无向图可以是无向连通图或无向非连通图。 一、需求分析 1、输入的形式和输入值的范围：根据提示，首先输入图的所有边建立邻接表存储结构，然后输入遍历的起始顶点对图或非连通图的某一连通分量进行遍历。 2、输出的形式：输出对该图是连通图或非连通图的判断结果，若是非连通图则输出各连通分量的顶点，之后输出队连通图或非连通图的某一连通分量的遍历结果。 3、程序所能达到的功能：输入图的所有边后，建立图的邻接表存储结构，判断该图是连通图或非连通图，最后对图进行遍历。 4、测试数据： 输入10个顶点（空格分隔）:A B C D E F G H I J 输入边的信息（格式为x y）:AB AC AF CE BD DC HG GI IJ HJ EH 该图为连通图,请输入遍历的起始顶点:A 遍历结果为:A F C D B E H J I G 是否继续？（是,输入1;否,输入0）:1 输入10个顶点（空格分隔）:A B C D E F G H I J 输入边的信息（格式为xy）:AB AC CE CA AF HG HJ IJ IG 该图为非连通图,各连通分量中的顶点为: < A F C E B > < D > < G I J H > 输入第1个连通分量起始顶点:F 第1个连通分量的遍历结果为:F A C E B 输入第2个连通分量起始顶点:I 第2个连通分量的遍历结果为:I G H J 输入第3个连通分量起始顶点:D 第3个连通分量的遍历结果为:D 是否继续？（是,输入1;否,输入0）:0 谢谢使用! Press any key to continue 二概要设计 1、邻接表是图的一种顺序存储与链式存储结构结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对图G中的每个顶点Vi，将所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表，再将所有邻接表的表头放到数组中，就构成了图的邻接表，邻接表表示中的两种结点结构如下所示。 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：拓扑排序算法 院（系）：计算机学院 专业：计算机科学与技术（嵌入式系统方向） 班级：14010105班 学号：2011040101221 姓名：王芃然 指导教师：丁一军 目录 1 课程设计介绍 (1) 1.1课程设计内容 (1) 1.2课程设计要求 (1) 2 课程设计原理 (2) 2.1课设题目粗略分析 (2) 2.2原理图介绍 (2) 2.2.1 功能模块图 (2) 2.2.2 流程图分析 (3) 3 数据结构分析 (7) 3.1存储结构 (7) 3.2算法描述 (7) 4 调试与分析 (12) 4.1调试过程 (12) 4.2程序执行过程 (12) 参考文献 (14) 附录（关键部分程序清单） (15) 1 课程设计介绍 1.1 课程设计内容 由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。若在图一的有向图上人为的加一个表示V2<=V3的弧(“<=”表示V2领先于V3)则图一表示的亦为全序且这个全序称为拓扑有序,而由偏序定义得到拓扑有序的操作便是拓扑排序。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。编写算法建立有向无环图，主要功能如下： 1.能够求解该有向无环图的拓扑排序并输出出来； 2.拓扑排序应该能处理出现环的情况； 3.顶点信息要有几种情况可以选择。 1.2 课程设计要求 1.输出拓扑排序数据外，还要输出邻接表数据； 2.参考相应的资料，独立完成课程设计任务； 3.交规范课程设计报告和软件代码。 强联通分量与模拟链表 作者：逸水之寒 1.强连通分量 强连通分量的定义是：在有向图中，u可以到达v，但是v不一定能到达u，如果u,v 到达，则他们就属于一个强连通分量。 求强连通分量最长用的方法就是Kosaraju算法，比较容易理解而且效率很高，本文对强连通分量的求法均采用Kosaraju算法。 其主要思想：首先对原图G进行深搜形成森林（树），然后选择一棵树进行第二次深搜，注意第一次是要判断节点A能不能通向节点B，而第二次要判断的是节点B能不能通向A，能遍历到的就是一个强连通分量。（附录给出伪代码） Kosaraju算法如果采用了合适的数据结构，它的时间复杂度是O(n)的。相关题目有很多，例如USACO 5.3.3，2009NOIP Senior No.3。下面将以USACO 5.3.3 schlnet 举例说明。 Preblem 1. Network of Schools (USACO 5.3.3 schlnet\IOI96 No.3) A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the "receiving schools"). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B. You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school. 14信计2015-2016（一） 数据结构课程设计 设计题目拓扑排序 设计时间2016.1.11——2016.1.15 学生姓名冯佳君 学生学号20140401105 所在班级14信计1 指导教师刘风华 徐州工程学院数学与物理科学学院 一、需求分析 1.问题描述 本次课程设计题目是：用邻接表构造图然后进行拓扑排序，输出拓扑排序序列。 拓扑排序的基本思想为： 1)从有向图中选一个无前驱的顶点输出； 2)将此顶点和以它为起点的弧删除； 3) 重复1)、 2)直到不存在无前驱的顶点； 4) 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。 2.拓扑排序有向图拓朴排序算法的基本步骤如下： 1）从图中选择一个入度为0的顶点，输出该顶点； 2）从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度-1）； 3）重复执行1）、2）直到所有顶点均被输出，拓朴排序完成或者图中再也没有入度为0的顶点（此种情况说明原有向图含有环）。 3．基本要求 (1)输入的形式和输入值的范围； 首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。 (2)输出的形式； 首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。 (3) 程序所能达到的功能； 因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。 二、概要设计拓扑排序
数据结构图习题分解
数据结构拓扑排序实验报告
有向图的强连通分量
7.4.1无向图的连通分量和生成树
有向图拓扑排序算法的实现
求一个无向图G的连通分量的个数
求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq
有向图的强连通分量算法
求强连通分量tarjan算法讲解
数据结构 第六章 图 练习题及答案详细解析(精华版)
拓扑排序课程设计报告
拓扑排序算法
拓扑排序(算法与数据结构课程设计)
数据结构 无向图的存储和遍历
拓扑排序课程设计报告
强连通分量与模拟链表
数据结构-拓扑排序