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

1、课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：实现求有向图强连通分量的算法实现求有向图强连通分量的算法 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师： 目目 录录 1 系统分析系统分析.1 1.1 题目介绍 .1 1.2 功能要求 .1 2 概要设计概要设计.2 2.1 流程图 .2 2.2 结构体说明 .2 3 详细设计详细设计.3 3.1 遍历函数设计 .3 3.1.1 Kosaraju 算法基本思路：.3 3.1.2 伪代码.4 3.2 调试分析和测试结果 .6 3.2.1 调试分析.6 3.2.2 测试结果.6 参考文

2、献参考文献.8 附附 录（关键部分程序清单）录（关键部分程序清单）.9 1 系统分析 1.1 题目介绍题目介绍 在键盘上输入有向图，对任意给定的图（顶点数和边数自定），建立它的邻 接表并输出。然后判断该图是否强连通。如果是强连通图，求出该图的所有强连 通分量并输出字符。 1.2 功能要求功能要求 首先输入图的类型，有向图（因为遍历与权值无关，所以没有涉及带权图）。 然后输入图的顶点数、边数和各条边，之后生成该图的邻接表并输出。 再输入要遍历该图的起点，然后从所输入的点深度搜索该图的十字链表，并 按遍历顺序输出顶点内容。之后决定是否继续遍历该图或输入另一个需要遍历的 图亦或是结束程序。 要求采取

3、简单方便的输入方式。并且系统要求提供观察有向图图形结构和各 强连通分量结构的功能。 2 概要设计 2.1 流程图流程图 根据程序要求，设计流程图如下： 是 否 图 2.1流程图 2.2 结构体说明结构体说明 /有向图十字链表存储表示 typedef struct arcbox int tailvex,headvex;/该弧的尾和头顶点的位置 开始 输入有向图 图的类型 确定有无权值 的类型 1（有权值）0（无权值） 深度优先遍历该图 输入从哪个顶点开始遍历该图 结束 是否还有顶点结束 对反图 GT 进行遍历，删除能够遍历到的顶点 struct arcbox *hlink,*tlink;/分别为

4、弧头相同和弧尾相同的弧的链域 infotype * info;/该弧相关信息的指针 arcbox; typedef struct vexnode vextype data; arcbox *firstin,*firstout;/分别指向该顶点第一条入弧和出弧 vexnode; typedef struct vexnode xlistmax_vex_num;/表头向量 int vexnum,arcnum;/有向图的当前顶点数和弧数 OLgraph; 3 详细设计 3.1 遍历函数设计遍历函数设计 3.1.1 Kosaraju 算法基本思路算法基本思路： 这个算法可以说是最容易理解，最通用的算法，

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

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

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

8、历，记录每个节点的离开时间。 step2：选择具有最晚离开时间的顶点，对反图 GT 进行遍历，删除能够遍历到的 顶点，这些顶点构成一个强连通分量。 step3：如果还有顶点没有删除，继续 step2，否则算法结束。 3.1.3. 实现代码： #include using namespace std; const int MAXN = 110; typedef int AdjTableMAXN; /邻接表类型 int n; bool flagMAXN; /访问标志数组 int belgMAXN; /存储强连通分量,其中 belgi表示顶点 i 属于第 belgi个 强连通分量 int numbM

9、AXN; /结束时间标记,其中 numbi表示离开时间为 i 的顶点 AdjTable adjMAXN, radjMAXN; /邻接表,逆邻接表 /用于第一次深搜,求得 numb1.n的值 void VisitOne(int cur, int for ( int i=1; i=adjcur0; +i ) if ( false=flagadjcuri ) VisitOne(adjcuri,sig); numb+sig = cur; /用于第二次深搜,求得 belg1.n的值 void VisitTwo(int cur, int sig) flagcur = true; belgcur = sig

10、; for ( int i=1; i=radjcur0; +i ) if ( false=flagradjcuri ) VisitTwo(radjcuri,sig); /Kosaraju 算法,返回为强连通分量个数 int Kosaraju_StronglyConnectedComponent() int i, sig; /第一次深搜 memset(flag+1,0,sizeof(bool)*n); for ( sig=0,i=1; i0; -i ) if ( false=flagnumbi ) VisitTwo(numbi,+sig); return sig; 3.2 调试分析和测试结果调试

11、分析和测试结果 编译、运行及调试环境: Microsoft Visual C+ 3.2.1 调试分析调试分析 一在输入图信息的时候，若输入非法字符，程序会异常终止。例如程序要求输 入一个整型，用户却输入了一个字母，这时候会出现异常。只是程序是否健壮性 的一个体现。 先用字符串接收字符，转换成整型后再判断是否符合要求。如果不符合便提示用 户按要求重新输入。还有其他一些类似的输入异常，都是采用类似的处理方法。 二作为一个完整的程序，友好的界面是必须的。因次程序中适当地采用人性化 的提示命令，使得界面更加简洁，明了。 3.2.2 测试结果测试结果 测试案例： 3 1 4 2 6 5 图 3.2.2案

12、例结构图 图 1程序运行 图 2程序结果 参考文献 1 王为青，张圣亮 . C 语言实战 105 例. 人民邮电出版社，2007.3 2 严蔚敏，吴伟民 . 数据结构（C 语言版）.清华大学出版社，1997.4 3 袁平波.数据结构实验指导,合肥 .中国科学技术大学出版社，2010.7 4 杨克昌，刘志辉 . 趣味 C 程序设计集锦，北京 . 中国水利水电出版社， 2010.1 附 录（关键部分程序清单） # include # include typedef int vextype; typedef int infotype; typedef int status; # define max

13、_vex_num 15 # define FALSE 0 # define TRUE 1 # define OVERFLOW -2 /有向图十字链表存储表示 typedef struct arcbox int tailvex,headvex; struct arcbox *hlink,*tlink; infotype * info; arcbox; typedef struct vexnode vextype data; arcbox *firstin,*firstout; vexnode; typedef struct vexnode xlistmax_vex_num; int vexnum

14、,arcnum; OLgraph; int Locatevex(OLgraph G,int d) int k; for(k=0;kG.vexnum;+k) if(G.xlistk.data=d) return k; status creat_DG(OLgraph vextype tailnum,headnum; arcbox *p; printf(输入结点个数:); scanf(%d, printf(输入弧的条数:); scanf(%d, printf(输入有无权值判定符(0 表示没有,1 表示有):); scanf(%d, printf(输入所有弧结点数据:); for(a=0;aG.vex

15、num;+a) scanf(%d, G.xlista.firstin=NULL; G.xlista.firstout=NULL; for(k=0;ktailvex=i; p-headvex=j; p-hlink=G.xlistj.firstin; p-tlink=G.xlisti.firstout; /p-info=NULL; G.xlistj.firstin=G.xlisti.firstout=p; if(incinfo) printf(输入权值:); scanf(%d,p-info); return TRUE; /creat_DG typedef int boolen; boolen vi

16、sitedmax_vex_num ; int finishedmax_vex_num ; int number; void DFS_1(OLgraph G,int v) arcbox *p; visitedv=TRUE; p=G.xlistv.firstout; while(p) if(!visitedp-headvex) DFS_1(G,p-headvex); p=p-tlink; finishednumber=v; number=number+1; void DFStraverse_1(OLgraph G) int v; for(v=0;vG.vexnum;+v) visitedv=FALSE; for(v=0;vtailvex) DFS_2(G,p-tailvex); p=p-hlink; void DFStraverse_2(OLgraph G) int v,m=1; for(v=0;v=0;v-) if(!visitedfinishedv) printf(n); printf(n); printf(第%d 个连通分量的顶点集:,m); m=m+1; DFS_2(G,finishedv);