数据结构课设有向图强连通分量求解

连通图的割点、割边(桥)、块、缩点，有向图的强连通分量一、基本概念无向图割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。

块：没有割点的连通子图割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。

缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。

求块跟求缩点非常相似，很容易搞混，但本质上完全不同。

割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。

有割点的图不一定有割边，如：3是割点，分别与(1,2)和(4,5)形成两个无割点的块有割边的图也不定有割点,如：w(1,2)为割边，有向图强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。

dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。

low[i]=min(low[i],dfn[son[i]])设 v,u之间有边w(v,u)，从v->u：如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。

如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v 时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第二条新的路求割点的时候，维护一个栈st 每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v 形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS 到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可以方便理解。

南京邮电大学2000年硕士研究生入学考试数据结构试题一、完成下列各题（每小题6分，共18分）1.设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。

m:=0；FOR i:=1 TO n DOFOR j:=2*i TO n DOm：=m+1；2.已知字符串‘cddcdececd ea’,过算每介字符的next和nextval函数的值.3.给出冒泡排序和快速排序的最好情况,平均情况和最坏情况下的时间复杂度。

二、完成下列各题：（每小题8分，共24分）1、设有下图所示的有向图，给出其邻接矩阵和强连通分量。

2、设有3阶B-树如下图所示，（1)从该B-树上依次插入关键字33，97，画出两次插入后的B-树；（2)从（1）得到的B-树上依次删除66，43，画出两次删除后的B-树；（1）画出据此构造的败选择树（2）画出输出一个记录后的败方树三、阅读下列二叉树算法,每个结点三个域：lchild,element,rchild。

(10分)(1)X(p)对以p为根的二叉树执行什么功能?(2)以下图所示的二叉树调用此算法，则X（p）的执行结果是什么?(3)执行中，栈s中元素个数最多时为多少?给出该时栈中元素的情况。

void X(BinTree *t){struct Stack s;BinTnode *qPush(s,NUL1)While(*p){q=(*p)->lchild(*p)->1child=(*p)->rchild(*p)->rchild=qIf((*p)->lchild)Push(s,(*p)->1child);If((*p)->rchild)Push(s,(*p)->rchild)；else(*p)=Pop(s)}}四、阅读下列要求每对顶点之间的最短路径的Floyd算法。

(16分)（1)若对下图所示的有向图执行此算法，写出对k为1到n的各步中，二维数组a和path的值。

一、判断题 (每题1分,共131分)1. 线性表的逻辑顺序总是与其物理顺序一致。

（）【答案】错2. 线性表的顺序存储优于链式存储。

（）【答案】错3. 在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。

（）【答案】对4. 若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。

（）【答案】错5. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。

（）【答案】对6. 内部排序是指排序过程在内存中进行的排序。

（）【答案】对7. 当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。

（）【答案】错8. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。

( )【答案】对9. 任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。

（）【答案】对10. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。

( )【答案】错11. 如果采用如下方法定义一维字符数组：int maxSize = 30;char * a = new char[maxSize];则这种数组在程序执行过程中不能扩充。

（）【答案】错12. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

（）【答案】对13. 对稀疏矩阵进行压缩存储是为了节省存储空间。

（）【答案】对14. 当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。

( )【答案】对15. 哈希查找法中解决冲突问题的常用方法是除留余数法。

（）【答案】错16. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。

( )【答案】错17. 堆排序是一种稳定的排序算法。

( )【答案】错18. 如果有向图中各个顶点的度都大于2，则该图中必有回路。

( )【答案】错19. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。

求有向图的强连通分量的经典算法——Kosaraju算法一、Kosaraju算法步骤：Step1、对有向图G做dfs（深度优先遍历），记录每个结点结束访问的时间Step2、将图G逆置，即将G中所有弧反向。

Step3、按Step1中记录的结点结束访问时间从大到小对逆置后的图做dfs Step4、得到的遍历森林中每棵树对应一个强连通分量。

相关概念：在dfs(bfs)算法中，一个结点的开始访问时间指的是遍历时首次遇到该结点的时间，而该结点的结束访问时间则指的是将其所有邻接结点均访问完的时间。

二、Kosaraju算法求解过程实例下面结合实例说明Kosaraju算法的基本策略。

图1给出了一个有向图G。

图1 有向图GStep1：假设从DFS在遍历时按照字母顺序进行，根据Kosaraju算法，在步骤1中我们得到的遍历顺序可以表达为[A,[C,[B,[D,D],B],C],A][E,[F,[G,[H,H],G],F],E]在遍历序列中每一个结点出现了两次，其中第一次出现的时间为该结点的开始访问时间，第二次出现的时间为该结点的结束访问时间。

Step2：根据算法第2步，将图G逆置，得到对应的反向图G’如图2所示。

Step3：根据步骤1得到的遍历序列，按照结点结束访问时间递减排序后的结果为EFGHACBD下面，按照该结点序列顺序对逆置图G ’所深度优先遍历，得到的深度优先遍历森林如图3所示。

森林中共有4棵树，其中(a)和(d)只有一个结点，这里认为单结点也是一个强联通分量（在实际应用中可以根据实际需要将这种情况过滤掉）。

三、算法讨论问题1：以上图为例，第一遍搜索得到以A 为根的子序列（设为S1）和以E 为根的子树序列（设为S2），图反向后，再从E 开始搜索，能搜到的元素肯定不会包含S1的元素，为什么？答：因为S1中的点都不能到达E ，而第二遍搜索就是看哪些点能到达E ，所以搜不到S1中的点。

问题2：图反向后对A 进行深搜，尽管E 能到达A ，为什么搜不到E ？因为第一遍深搜时，A 不能达到E ，所以E 肯定位于A 的右边，而第二遍深搜是按照结束时间进行搜索的，在搜索A 之前，已经搜完E ，对E 设置了已经遍历标志，所以不会把E 并入A 的强联通分量。

《数据结构》课程设计指导书课程设计名称：数据结构课程设计09102版服务课程名称：数据结构课程设计适用班级：BX0805、BX0806 课程设计周数：1-2周指导老师：王中华（wangzh@）指导方式：集体辅导与个别答疑相结合课程设计授课单位：上海电机学院电子信息学院计算机基础教学部课程设计教材及主要参考资料：陈元春等编著的《实用数据结构基础》，中国铁道出版社严蔚敏，吴伟民编著的《数据结构》，清华大学出版社一、课程设计教学目的及基本要求1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

5．设计的题目要求达到一定工作量，并具有一定的深度和难度。

6．编写出课程设计报告，报告正文不得少于10页（其中正文文字部分不得少于七页，代码不算页数）。

二、课程设计内容及安排1．问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？2．逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。

逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；3．详细设计：定义相应的存储结构并写出各函数的伪码算法。

在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。

详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4．程序编码：把详细设计的结果进一步求精为程序设计语言程序。

求有向图的强连通分量个数（kosaraju算法）求有向图的强连通分量个数（kosaraju算法）1. 定义连通分量：在⽆向图中，即为连通⼦图。

上图中，总共有四个连通分量。

顶点A、B、C、D构成了⼀个连通分量，顶点E构成了⼀个连通分量，顶点F，G和H，I分别构成了两个连通分量。

强连通分量：有向图中，尽可能多的若⼲顶点组成的⼦图中，这些顶点都是相互可到达的，则这些顶点成为⼀个强连通分量。

上图中有三个强连通分量，分别是a、b、e以及f、g和c、d、h。

2. 连通分量的求解⽅法对于⼀个⽆向图的连通分量，从连通分量的任意⼀个顶点开始，进⾏⼀次DFS，⼀定能遍历这个连通分量的所有顶点。

所以，整个图的连通分量数应该等价于遍历整个图进⾏了⼏次（最外层的）DFS。

⼀次DFS中遍历的所有顶点属于同⼀个连通分量。

下⾯我们将介绍有向图的强连通分量的求解⽅法。

3. Kosaraju算法的基本原理我们⽤⼀个最简单的例⼦讲解Kosaraju算法显然上图中有两个强连通分量，即强连通分量A和强连通分量B，分别由顶点A0-A1-A2和顶点B3-B4-B5构成。

每个连通分量中有若⼲个可以相互访问的顶点（这⾥都是3个），强连通分量与强连通分量之间不会形成环，否则应该将这些连通分量看成⼀个整体，即看成同⼀个强连通分量。

我们现在试想能否按照⽆向图中求连通分量的思路求解有向图的强连通分量。

我们假设，DFS从强连通分量B的任意⼀个顶点开始，那么恰好遍历整个图需要2次DFS，和连通分量的数量相等，⽽且每次DFS遍历的顶点恰好属于同⼀个连通分量。

但是，我们若从连通分量A中任意⼀个顶点开始DFS，就不能得到正确的结果，因为此时我们只需要⼀次DFS就访问了所有的顶点。

所以，我们不应该按照顶点编号的⾃然顺序（0,1,2，……）或者任意其它顺序进⾏DFS，⽽是应该按照被指向的强连通分量的顶点排在前⾯的顺序进⾏DFS。

上图中由强连通分量A指向了强连通分量B。

一、单选题C01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A)1/2 B)1 C)2 D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A)1/2 B)1 C)2 D)4B03、有8个结点的无向图最多有条边。

A)14 B)28 C)56 D)112C04、有8个结点的无向连通图最少有条边。

A)5 B)6 C)7 D)8C05、有8个结点的有向完全图有条边。

A)14 B)28 C)56 D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A)O(n) B)O(e) C)O(n+e) D)O(n2)C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、图的深度优先遍历类似于二叉树的。

A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历D14、图的广度优先遍历类似于二叉树的。