数据结构课设有向图强连通分量求解
沈阳航空航天大学
课 程 设 计 报 告
课程设计名称：数据结构课程设计
课程设计题目：有向图强连通分量求解
院（系）：计算机学院
专 业： 网络工程
班 级：
学 号：
姓 名：
指导教师：
目 录
1 算法分析 .................................................................................................................... 2
1.1假设条件 . ................................................................................................................ 2
1.2算法描述 . ................................................................................................................ 2
1.2.1 有向图的存储结构 ....................................................................................... 2
1.2.2 深度优先遍历 ............................................................................................... 3
1.2.3 求解强连通分量 ............................................................................................. 3
2 系统设计 .................................................................................................................... 4
2.1设计说明 . ................................................................................................................ 4
2.2数据结构描述 . ........................................................................................................ 4
2.3 MAIN()函数 . ............................................................................................................. 5
2.4邻接表和逆邻接表的建立 . .................................................................................... 7
2.5邻接表的遍历 . ........................................................................................................ 8
2.6逆邻接表的遍历 . .................................................................................................... 9
3 系统实现 .................................................................................................................. 12
3.1错误分析 . .............................................................................................................. 12
3.2实现结论 . .............................................................................................................. 12
参考文献 ........................................................................................................................ 13
附 录（关键部分程序清单） .................................................................................. 14
1 算法分析
1.1假设条件
有向图的强连通分量是有向图中的最大强连通子图。而对于一个有向图G ，如果对于每一对的Vi 和V j ∈V ，Vi ≠V j ，从Vi 到V j 和V j 到Vi 都存在路径，则称G 是强连通图。
有向图强连通分量求解的设置分为存储、输入以及输出三大部分。
（1）算法的存储分为对有向图的顶点的存储，对有向图的弧的存储和对整个有向图的链式存储。
（2）输入分为三大部分：第一，输入有向图的顶点数以及弧条数（均为整数）；第二，输入各个顶点的信息（均为字符型）；第三，输入每一条弧的弧尾与弧头所对应的顶点信息，即对各顶点进行链式存储时的顶点信息，并以输出0 0 为结束标志。
（3）算法的输出为该有向图的所有强连通分量（以集合的形式表示）以及该有向图是否是强连通图。
1.2算法描述
该算法是为了实现输入一有向图到适当的存储结构中，判断该有向图是否强连通，若不是强连通图则求出该图的所有强连通分量并输出。
1.2.1 有向图的存储结构
对于输入的有向图，利用链式的存储结构进行存储即对有向图的顶点、弧以及有向图进行链式的存储。
有向图顶点的存储中包含邻接点域(adjvex)指示与顶点Vi 邻接的点在图中的位置和链域(next)指示下一条弧的结点。有向图的弧的存储包含存储顶点Vi 信息数据域(data)以及指向第一条依附该顶点的弧的指针(firstarc)指向链表中第一个结点。有向图的存储包含存储顶点的链表的最大长度，当前顶点数以及弧数。创建一个新的有向图就要输入图所包含的顶点数，弧条数，各顶点信息以及每条弧的弧尾和
弧头所对应的顶点序号，并以输入0 0 为结束的标志。
1.2.2 深度优先遍历
假设初始状态为图中所有顶点都未被访问即flag[m]=0,则从图中的某个顶点出发，访问此顶点，对有向图的邻接表和逆邻接表进行深度优先遍历，并令flag[m]=1表示该结点已经被访问。当该结点未被访问时利用递归再对其进行访问, 直到图中所有顶点都被访问到为止。
1.2.3 求解强连通分量
深度优先遍历是求解有向图的强连通分量的一个新的有效方法。
（1）对于以链式存储的有向图G ，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成的顺序将顶点排列起来。
（2）再从最后完成搜索的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历，若此次遍历不能访问到有向图中所有的顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先遍历，依此类推，直至有向图中所有顶点都被访问到为止。
由此，每一次调用DFS 作逆向深度优先遍历所访问到的顶点集便是有向图G 中一个强连通分量的顶点集。
例如，图1.2.2所示的有向图，假设从顶点V1出发作深度优先搜索遍历，得到finished 数组中的顶点号为（2,4,3,1）；则再从顶点V1出发作逆向的深度优先搜索遍历，得到顶点集{V1，V3，V4}和{V2}，这就是该有向图的两个强连通分量的顶点集。
2 系统设计
2.1设计说明
该算法设计共包含五大模块，即：有向图的主函数模块，链式存储模块，建立有向图的原图的邻接表和逆邻接表模块，深度优先遍历原图的邻接表模块，深度优先遍历原图的逆邻接表模块。主函数模块调用原图的邻接表和逆邻接表两个深度优先遍历的函数。函数模块关系如图2. 1.1所示：
2.2数据结构描述
该函数包含三个结构体，即存储弧、存储顶点和存储图的结构体。其结构体分别如下所示：
存储弧的结构体, 其中包含两个变量adjvex 和指针next ， adjvex 指示与顶点Vi 邻接的点在图中的位置和next 指示下一条弧的结点：
typedef struct ArcNode{
int adjvex;
struct ArcNode *next;
}ArcNode;
存储顶点的结构体, 其中包含两个变量data 和指针firstarc ，存储顶点Vi
信息数据域(data)以及指向第一条依附该顶点的弧的指针(firstarc)指向链表中第一个结点：
typedef struct Vnode{
char data;
ArcNode *firstarc;
} Vnode ;
存储图的结构体, 其中包含存储顶点表的最大长度值及变量顶点数和弧条数，存储顶点的链表的最大长度，当前顶点数vexnum 以及弧数arcnum ：
typedef struct ALGraph{
Vnode list[MAX];
int vexnum ,arcnum;
}ALGraph;
2.3 main()函数
创建一个有向图，对建立的有向图的邻接表及逆邻接表进行深度优先遍历。从而求解出该有向图的强连通分量，并判断该有向图是否为强连通图，输出该有向图的强连通分量的顶点集。主函数流程图如图2.3.1所示：
2.4邻接表和逆邻接表的建立
用函数creatgraph(&G1，&G2)建立有向图的邻接表G1和逆邻接表G2。输入该有向图的顶点数和弧条数，各顶点的信息及每条弧的弧尾和弧头所对应的顶点序号并以0 0作为其结束的标志。其流程图如图2.4.1所示：
2.5邻接表的遍历
利用DFSTraverse1（&G1，m ）函数和对有向图的邻接表进行深度优先遍历，并用flag[m]=1表示已经遍历过该结点，flag[m]=0表示该结点未被遍历。若该结点未被遍历即flag[m]=0，则利用递归调用DFS1（&G1,m）函数从该结点出发对有向图进行深度优先遍历，直到访问完该有向图中的所有顶点。该遍历流程图如图2.5.1和图2.5. 2所示：
2.6逆邻接表的遍历
利用DFSTraversel2（&G2，m ）函数对有向图的逆邻接表进行深度优先遍历，
并同2.5节中一样利用flag[m]=1标记已经遍历过的结点，flag[m]=0标记未被遍历的结点，再对该结点利用递归调用DFS2（&G2，m ）函数从该结点出发对有向图进行深度优先遍历。最后输出该有向图的强连通分量（顶点集形式）。这部分算法的流程图如图2.6.1和图2.6.2所示：
3 系统实现
3.1错误分析
（1）算法在执行过程中，输入结点的信息时，如果输入的结点格式不对称即输入时结点间间隔不一致，都将导致不能输入每条弧的弧头和弧尾信息而直接输出该有向图是否为有向图的结论和强连通分量的顶点集。例如输入顶点数为4，弧的条数为5，输入顶点信息为a b c d 时，若将输入的格式变为（a b c d ），则下一步将直接跳过对每一条弧的弧头和弧尾的输入而输出结果：{}{b}{}{}及“该图不是强连通图！”。而对于其他的一些实现时并无什么语法的错误。
（2）编写算法时，对函数DFS1(ALGraph &G,int m) 忘记声明，导致程序无法调用该函数，运行出现错误，经过改正后，运行成功。
（3）输入顶点数时，未考虑顶点的最大数目，从而导致数组越界，程序无法正常运行。改正时可将输入的顶点数目减小或者将MAX 值增大，消除数组越界，使程序正常运行。
（4）对于一直困扰自己的遍历邻接表的作用是什么的问题，经过查阅资料，和同学一起讨论和思考，只能得出自己的初步解释。因为，深度优先遍历邻接表是为了求出finished[m]数组中的所有值，从而为逆邻接表的深度优先遍历寻找到起始的数值，从而控制算法的运行。实验中，我将邻接表的遍历函数删除后得出结果只有该有向图是否为强连通图，而无法求出其强连通分量。对于其本质原因，只能进一步去学习或者向老师请教。
3.2实现结论
该算法实现了输入一个有向图到适当的存储结构中，判断出该有向图是否为强连通图，如果不是时则求出该有向图的所有的强连通分量并输出。而且对于任意一个按要求输入的有向图都能将该有向图的所有强连通分量以结点集的形式输出。该实验需要改进的地方时将输出变成以有向图的形式输出。但由于个人水平 有限，无法实现该功能。
参考文献
[1] 严蔚敏，吴伟民 . 数据结构（C 语言版）［M ］. 北京：清华大学出版社，2006
[2] 张千帆 . 数据结构与算法（C 语言实现）[M] . 北京：科学出版社，2009
[3] 吕国英 . 算法设计与分析 [M] . 北京：清华大学出版社，2006
[4] 徐宝文 李志 . C程序设计语言[M] . 北京：机械工业出版社，2004
附 录（关键部分程序清单）
#include #include
#define MAX 20 #define NULL 0
typedef struct ArcNode{ int adjvex; struct ArcNode *next;
}ArcNode;
typedef struct Vnode{ char data; ArcNode *firstarc;
}Vnode;
typedef struct ALGraph{ Vnode list[MAX]; int vexnum,arcnum;
}ALGraph;
int flag[MAX],finished[MAX],a[MAX];
int count=0;
void creatgraph(ALGraph &G1,ALGraph &G2)
{ int i,j,v,a; ArcNode *p1,*p2;
char ch;
printf("请输入顶点数和弧条数\n");
scanf("%d %d",&v,&a);
getchar();
G1.vexnum=G2.vexnum=v; G1.arcnum=G2.arcnum=a;
printf("请输入顶点信息\n");
for(i=1;i
getchar();
G1.list[i].data=G2.list[i].data=ch;
G1.list[i].firstarc=G2.list[i].firstarc=NULL; } printf("请输入每条弧的弧尾和弧头所对应的顶点序号, 以输入0 0作为结束标志\n");
scanf("%d %d",&i,&j);
while((i>0)&&(j>0)){ p1=(ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex=j;
p1->next=G1.list[i].firstarc;
G1.list[i].firstarc=p1;
p2=(ArcNode*)malloc(sizeof(ArcNode));
p2->adjvex=i;
p2->next=G2.list[j].firstarc;
G2.list[j].firstarc=p2;
scanf("%d %d",&i,&j);
} }
void DFS1(ALGraph &G,int m)
{ ArcNode *p; int i; flag[m]=1;
p=G.list[m].firstarc;
while(p!=NULL){
i=p->adjvex;
if(flag[i]==0)
DFS1(G,i);
p=p->next; }
finished[++count]=m; }
void DFStraverse1(ALGraph &G)
{ int i,v; v=G.vexnum;
for(i=1;i
flag[i]=0;
for(i=1;i
if(flag[i]==0)
DFS1(G,i); }
void DFS2(ALGraph &G,int m)
{ ArcNode *p; int i; flag[m]=1;
printf("%c",G.list[m].data);
p=G.list[m].firstarc;
while(p!=NULL){
i=p->adjvex;
if(flag[i]==0)
DFS2(G,i);
p=p->next; } }
void DFStraverse2(ALGraph &G)
{int i,v,n,j; v=G.vexnum;
for(i=1;i
flag[i]=0;
for(i=count;i>=1;i--){ n=finished[i];
if(flag[n]==0){ printf("{");
DFS2(G,n);
printf("}"); }
if(i==count)
for(j=count;j>=1;j--)
a[j]=flag[j]; }
void main( )
{int j,s; ALGraph G1,G2; creatgraph(G1,G2);
DFStraverse1(G1); DFStraverse2(G2); j=count; s=1;
while(j>=1){ if(a[j]==1)
j--;
else {s=0;break;} }
if(s==1)
printf("\n该图是强连通图!\n");
else
printf("\n该图不是强连通图!\n");
printf("\n");}
}