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

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

1、沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：有向图强连通分量求解院（系）：计算机学院专业:班级:学号:姓名:指导教师:业：网络工程目录1算法分析21.1假设条件21.2算法描述21.2.1有向图的存储结构21.2.2深度优先遍历31.2.3求解强连通分量32系统设计42.1设计说明42.2数据结构描述42.3MAIN()函数52.4邻接表和逆邻接表的建立72.5邻接表的遍历82.6逆邻接表的遍历93系统实现123.1错误分析123.2实现结论12参考文献13附录(关键部分程序清单)141算法分析1.1假设条件有向图的强连通分量是有向图中的最大强连通子图。而对于一个

2、有向图G,如果对于每一对的Vi和Vjev，Vi^Vj,从Vi到Vj和Vj到Vi都存在路後，则称G是强连通图。有向图强连通分量求解的设置分为存储、输入以及输出三大部分。(1)算法的存储分为对有向图的顶点的存储，对有向图的弧的存储和对整个有向图的链式存储。(2)输入分为三大部分：第一，输入有向图的顶点数以及弧条数(均为整数);第二，输入各个顶点的信息(均为字符型)；第三，输入每一条弧的弧尾与弧头所对应的顶点信息，即对各顶点进行链式存储时的顶点信息，并以输出00为结束牛不志。(3)算法的输出为该有向图的所有强连通分量(以集合的形式表示)以及该有向图是否是强连通图。1.2算法描述该算法是为了实现输入

3、一有向图到适当的存储结构中，判断该有向图是否强连通，若不是强连通图则求出该图的所有强连通分量并输出。1.2.1有向图的存储结构对于输入的有向图，利用链式的存储结构进行存储即对有向图的顶点、弧以及有向图进行链式的存储。有向图顶点的存储中含邻接点域(adjvex)指示与顶点Vi邻接的点在图中的位置和链域(next)指示下一条弧的结点。有向图的弧的存储包含存储顶点Vi信息数据域(data)以及指向第一条依附该顶点的弧的指针(firstarc)指向链表中第一个结点。有向图的存储包含存储顶点的链表的最大长度，当前顶点数以及弧数。创建一个新的奋向图就要输入图所包含的顶点数，弧条数，各顶点信息以及每条弧的

4、弧尾和弧头所对应的顶点序号，并以输入00为结束的标志。1.2.2深度优先遍历假设初始状态为图屮所有顶点都未被访问即flaghn^O,则从图屮的某个顶点出发，访问此顶点，对有向图的邻接表和逆邻接表进行深度优先遍历，并令flag[m]=l表示该结点己经被访问。当该结点未被访问时利用递归再对其进行访问，直到图中所有顶点都被访问到为止。1.2.3求解强连通分量深度优先遍历是求解有向图的强连通分量的一个新的有效方法。(1)对于以链式存储的有向图G，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成的顺序将顶点排列起来。(2)再从最后完成搜索的顶点出发，沿着以该顶点为头的

5、弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有的顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先遍历，依此类推，直至有向图中所有顶点都被访问到为止。由此，每一次调用DFS作逆向深度优先遍历所访问到的顶点集便是有向图G中一个强连通分量的顶点集。例如，图1.2.2所示的有向图，假设从顶点VI出发作深度优先搜索遍历，得到finished数组中的顶点号为(2,4,3,1);则再从顶点VI出发作逆向的深度优先搜索遍历，得到顶点集｛VI,V3,V4｝和｛V2｝,这就是该有向图的两个强连通分量的顶点集。图1.2.1有向图G32系统设计2.1设计说明该算法设计共包含五大模块，

6、即：有向图的主函数模块，链式存储模块，建立有向图的原图的邻接表和逆邻接表模块，深度优先遍历原图的邻接表模块，深度优先遍历原图的逆邻接表模块。主函数模块调用原图的邻接表和逆邻接表两个深度优先遍历的函数。函数模块关系如图2.1.1所示：有向图强连通分量求解主函数模块图式向链储有的郁邻接表和逆邻接表的建力：邻接表的遍历逆表历接遍邻々图2.1.1有向图强连通分量求解算法模块2.2数据结构描述该函数毡含三个结构体，即存储弧、存储顶点和存储图的结构体。其结构体分别如下所示：存储弧的结构体，其中包含两个变量adjvex和指针next,adjvex指示与顶点Vi邻接的点在图屮的位置和next指示下一条弧的结

7、点：typedefstructArcNode{intadjvex;structArcNode相ext;}ArcNode;存储顶点的结构体，其屮包含两个变景data和指针firstarc,存储顶点Vi信息数据域(data)以及指向第一条依附该顶点的弧的指针(firstarc)指向链表中第一个结点：typedefstructVnode{chardata;ArcNode氺firstarc;}Vnode;存储图的结构