数据结构课程设计报告--实现求有向图强连通分量的算法

《数据结构课程设计报告--实现求有向图强连通分量的算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计报告课程设计名称：数据结构课程设计课程设计题目：实现求有向图强连通分量的算法院（系）：专业：班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告目录1系统分析11.1题目介绍11.2功能要求12概要设计22.1流程图22.2结构体说明23详细设计33.1遍历函数设计33.1.1Kosaraju算法基本思路：33.1.2伪代码43.2调试分析和测试结果63.2.1调试分析63.2.2测试结果6参考文献8附录（关键部分程序清单）913沈阳航空航天大学课程设计报告1系统分析1.1题目介绍在键盘上输入有向图，对任意给定的图（顶点数

2、和边数自定），建立它的邻接表并输出。然后判断该图是否强连通。如果是强连通图，求出该图的所有强连通分量并输出字符。1.2功能要求首先输入图的类型，有向图（因为遍历与权值无关，所以没有涉及带权图）。然后输入图的顶点数、边数和各条边，之后生成该图的邻接表并输出。再输入要遍历该图的起点，然后从所输入的点深度搜索该图的十字链表，并按遍历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的图亦或是结束程序。要求采取简单方便的输入方式。并且系统要求提供观察有向图图形结构和各强连通分量结构的功能。13沈阳航空航天大学课程设计报告2概要设计

3、2.1流程图根据程序要求，设计流程图如下：开始输入有向图图的类型确定有无权值的类型1（有权值）0（无权值）输入从哪个顶点开始遍历该图深度优先遍历该图对反图GT进行遍历，删除能够遍历到的顶点是否还有顶点结束是否结束图2.1——流程图2.2结构体说明//有向图十字链表存储表示typedefstructarcboxinttailvex,headvex;//该弧的尾和头顶点的位置13沈阳航空航天大学课程设计报告structarcbox*hlink,*tlink;//分别为弧头相同和弧尾相同的弧的链域infotype*info;//该弧相关信息

4、的指针}arcbox;typedefstructvexnode{vextypedata;arcbox*firstin,*firstout;//分别指向该顶点第一条入弧和出弧}vexnode;typedefstruct{vexnodexlist[max_vex_num];//表头向量intvexnum,arcnum;//有向图的当前顶点数和弧数}OLgraph;3详细设计3.1遍历函数设计3.1.1Kosaraju算法基本思路：这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。(步骤1)先用对原图G

5、进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT)，能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林，继续步骤2直到没有顶点为止。改进思路：13沈阳航空航天大学课程设计报告当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中)，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。想象一下，如果步骤2是从森林里选择树，那么哪

6、个树是不连通(对于GT来说)到其他树上的呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。那么，每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。隐藏性质:分析到这里，已经知道怎么求强连通分量了。但是，如果把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量

7、收缩成点后形成的有向无环图的拓扑序列。首先，应该明确搜索后的图一定是有向无环图，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗？这就是Kosaraju算法的一个隐藏性质。3.1.2伪代码Kosaraju_Algorithm:step1：对原

8、图G进行深度优先遍历，记录每个节点的离开时间。step2：选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。step3：如果还有顶点没有删除，继续step2，否则算法结束。