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

课 程 设 计 报 告 课程设计名称数据结构课程设计 课程设计题目实现求有向图强连通重量的算法 院（系） 专 业 班 级 学 号 姓 名 指导老师 沈阳航空航天高校课程设计报告 目 录 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 参考文献8 附 录（关键部分程序清单）9 13 沈阳航空航天高校课程设计报告 1 系统分析 1.1 题目介绍 在键盘上输入有向图，对随意给定的图（顶点数和边数自定），建立它的邻接表并输出。然后推断该图是否强连通。假如是强连通图，求出该图的全部强连通重量并输出字符。 1.2 功能要求 首先输入图的类型，有向图（因为遍历与权值无关，所以没有涉及带权图）。然后输入图的顶点数、边数和各条边，之后生成该图的邻接表并输出。 再输入要遍历该图的起点，然后从所输入的点深度搜寻该图的十字链表，并按遍历依次输出顶点内容。之后确定是否接着遍历该图或输入另一个须要遍历的图亦或是结束程序。 要求实行简洁便利的输入方式。并且系统要求供应视察有向图图形结构和各强连通重量结构的功能。 沈阳航空航天高校课程设计报告 2 概要设计 2.1 流程图 依据程序要求，设计流程图如下 起先 输入有向图图的类型 确定有无权值的类型 1（有权值） 0（无权值） 输入从哪个顶点起先遍历该图 深度优先遍历该图 对反图GT进行遍历，删除能够遍历到的顶点 是否还有顶点结束 是 否 结束 图2.1流程图 2.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 xlist[max_vex_num];//表头向量 int vexnum,arcnum;//有向图的当前顶点数和弧数 }OLgraph; 3 具体设计 3.1 遍历函数设计 3.1.1 Kosaraju算法基本思路 这个算法可以说是最简洁理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。步骤1先用对原图G进行深搜形成森林树，（步骤2）然后任选一棵树对其进行深搜留意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT，能遍历到的顶点就是一个强连通重量。余下部分和原来的森林一起组成一个新的森林，接着步骤2直到没有顶点为止。 改进思路 当然，基本思路实现起来是比较麻烦的因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通重量只能存在单棵树中，我们当然不这么做，我们可以奇妙的选择其次深搜选择的树的依次，使其不行能深搜到其他树上去。想象一下，假如步骤2是从森林里选择树，那么哪个树是不连通对于GT来说到其他树上的呢就是最终遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们供应了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]j。那么，每次只需找到没有找过的顶点中具有最晚离开时间的顶点干脆深搜对于GT来说就可以了。每次深搜都得到一个强连通重量。 隐藏性质 分析到这里，已经知道怎么求强连通重量了。但是，假如把求出来的每个强连通重量收缩成一个点，并且用求出每个强连通重量的依次来标记收缩后的节点，那么这个依次其实就是强连通重量收缩成点后形成的有向无环图的拓扑序列。首先，应当明确搜寻后的图肯定是有向无环图，假如还有环，那么环上的顶点对应的全部原来图上的顶点构成一个强连通重量，而不是构成环上那么多点对应的独自的强连通重量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通重量收缩的点只能指向后出现的强连通重量收缩的点。那么拓扑序列不是天经地义的吗这就是Kosaraju算法的一个隐藏性质。 3.1.2伪代码 Kosaraju_Algorithm step1对原图G进行深度优先遍历，记录每个节点的离开时间。 step2选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通重量。 step3假如还有顶点没有删除，接着step2，否则算法结束。 3.1.3. 实现代码 include iostream using namespace std; const int MAXN 110; typedef int AdjTable[MAXN]; //邻接表类型 int n; bool flag[MAXN]; //访问标记数组 int belg[MAXN]; //存储强连通重量,其中belg[i]表示顶点i属于第belg[i]个强连通重量 int numb[MAXN]; //结束时间标记,其中numb[i]表示离开时间为i的顶点 AdjTable adj[MAXN], radj[MAXN]; //邻接表,逆邻接表 //用于第一次深搜,求得numb[1..n]的值 void VisitOneint cur, int sig { flag[cur] true; for int i1; iadj[cur][0]; i { if falseflag[adj[cur][i]] { VisitOneadj[cur][