求有向图的强连通分量(c语言版)
有向图G：
1.选用何种结构存储有向图？
选用十字链表的结构来存储图
2.选用何种遍历方式？
选用深度优先搜索
3.思路
3.1 首先从图G上某个顶点出发沿以该顶点为尾的弧深度优先搜索，在顶点深度优先搜索结束之时把该顶点存放到辅助数组finished中(程序中实际存放的是该顶点在图中的位置，当然顶点的位置是人为定的，a的位置是0，b的位置是1，c的位置是2，d的位置是3，顶点在图的结构体中用数组存起来)。
解释：假如从a顶点开始深度遍历，过程是a->c->d，那么finished数组的值是 {3,2,0}，深度遍历完后，a顶点的访问才结束，所以a最后退出这次遍历，a存放到finished数组最后。
3.2 然后从最后搜索完成的顶点(即finished数组中最后一个元素)出发，沿着以该顶点为头的弧作逆向的深度优先搜索遍历，若以该顶点的这次深度遍历不能访问到图中所有的顶点，就从数组finished中最后完成搜索的顶点(还未被访问的)再次深度优先搜索遍历，以此类推，直到图中所有的顶点都被访问过。
解释：假如finished数组中的值是{1,3,2,0}，从0开始逆向的深度优先搜索，能访问到2，3，但是1访问不到，假如1前面还有4，5顶点({4,5,1})，因为数组finished是按退出深度优先搜索的顺序存进去的，所以1就是当前最后完成深度优先搜索的顶点（相比4，5顶点），因此再从1顶点开始逆向深度优先遍历，以此类推，直到所有顶点都访问到。
3.3 打印出来的结果就是各强连通分量的顶点集。
4.原理
强连通分量的意思是 有向图G=(V,{A})，(V代表顶点集，A代表弧)，如果对于每一对vi,vj属于V，vi不等于vj，从vi到vj和从vj到vi都存储路径，称G是强连通图，而有向图中的极大连通子图叫有向图的强连通分量（如vi到vj有路径，vj到vi也要有路径，才叫强连通）。根据图，从a顶点根据以弧尾是a的弧能访问到d，那么从a顶点根据以弧头是a的弧也能访问到d，说明a到d有路径，d到a也有路径，即是通的。
------------------------------------------------------------------------------------------------------------
源码地址：[email protected]:hglspace/OlGraph.git
-------------------------------------------------------------------------------------------------------------
myhead.c
#define MAX_VERTEX_NUM 4//人为设置顶点数为4
typedef int Bool;//自定义布尔型变量
#define True 1//以访问状态
#define False 0//未访问状态
//十字链表存储有向图
struct ArcBox{//弧结点
int tailvex;//尾结点在图中的位置
int headvex;//头结点在图中的位置
struct ArcBox * hlink;//弧头相同的下一条弧
struct ArcBox * tlink;//弧尾相同的下一条弧
Bool mark;//访问的标志 True代表访问过，False代表没有访问过
};
struct VexNode{//顶点结点
char data;//顶点信息
struct ArcBox * firstin;//以该顶点为弧头的第一条弧
struct ArcBox * firstout;//以该顶点为弧尾的第一条弧
};
struct OlGraph{
struct VexNode xlist[MAX_VERTEX_NUM];//顶点结点数组
int vexnum;//当前顶点数量
int arcnum;//当前弧的数量
};
//自定义头文件
-----------------------------------------------------------operateGraph.c
#include <stdio.h>
#include "myhead.h"
#include <stdlib.h>
Bool visits[MAX_VERTEX_NUM];//定义顶点辅助数组，记录顶点是否访问过
int count=0;//定义全局变量，辅助数组finished使用
struct ArcBox * edg[MAX_VERTEX_NUM];//定义全局弧指针数组，记录弧地址，方便把弧的是否访问过的状态重置
/*
初始化有向图
*/
struct OlGraph init(void){
int i,j,k,m;
char data1,data2;//用来接受顶点的信息，根据信息查找顶点的位置
struct OlGraph g;
int locateVex(struct OlGraph g,char data);//声明查找顶点位置的函数
printf("请输入图的顶点数:");
scanf("%d",&g.vexnum);
printf("请输入图的边数:");
scanf("%d",&g.arcnum);
//开始初始化顶点和弧
for(i=0;i<g.vexnum;i++){//初始化顶点
printf("请输入第%d个顶点:",i+1);
scanf(" %c",&g.xlist[i].data);
g.xlist[i].firstin=NULL;
g.xlist[i].firstout=NULL;
visits[i]=False;
}
for(j=0;j<g.arcnum;j++){//初始化弧
struct ArcBox * p = malloc(sizeof(struct ArcBox));//开辟存储弧的空间
if(p==NULL){//如果开辟失败，程序终止
exit(-1);
}
printf("请输入第%d条边的起点:",j+1);
scanf(" %c",&data1);
printf("请输入第%d条边的终点:",j+1);
scanf(" %c",&data2);
k=locateVex(g,data1);
m=locateVex(g,data2);
p->headvex=m;//对弧的头结点赋值
p->tailvex=k;//对弧的尾结点赋值
p->hlink=NULL;
p->tlink=NULL;
p->mark=False;//弧的状态置为未访问状态
if(g.xlist[m].firstin==NULL){//m结点是头结点，需要动态改变该结点第一个以该结点为头结点的弧
g.xlist[m].firstin=p;
}else{
p->hlink=g.xlist[m].firstin;
g.xlist[m].firstin=p;
}
if(g.xlist[k].firstout==NULL){//k结点是尾结点，需要动态改变该结点第一个以该结点为尾结点的弧
g.xlist[k].firstout=p;
}else{
p->tlink=g.xlist[k].firstout;
g.xlist[k].firstout=p;
}
edg[j]=p;//把弧的指针存储到 弧指针数组中
}
return g;
}
/*
根据顶点的信息查找顶点在图中的位置
*/
int locateVex(struct OlGraph g,char data){
int i;
for(i=0;data!=g.xlist[i].data;i++);
return i;
}
/*
生成有向图的强连通分量的顶点集
*/
void DFSTraverse(struct OlGraph g){
int i,k,s;
int finished[MAX_VERTEX_NUM];//该数组存储退出DFS函数的顶点（按照退出的顺序，先退出来的顶点先记录。记录的是顶点的位置）,作用是：方便反向深度遍历顶点
void DFS(struct OlGraph g,int i,int finished[]);//声明深度遍历顶点的函数
void DFSRever(struct OlGraph g,int i,int finished[]);//声明按照数组finished中存储的顶点，从finished[n-1]元素中存储的顶点开始深度遍历的函数 (n是存储的顶点个数)
for(i=0;i<g.vexnum;i++){//开始遍历顶点
if(visits[i]==True){//如果访问过，就跳过
continue;
}
DFS(g,i,finished);//调用函数
//finished[count++]=i;
}
for(k=0;k<g.vexnum;k++){//把顶点访问的标志重置到开始状态
visits[k]=False;
}
for(s=0;s<g.arcnum;s++){//把弧的访问标志重置到开始状态
edg[s]->mark=False;
}
while(count>=1){//按照finished数组中存放的顶点，开始深度遍历
if(visits[finished[count-1]]==True){//如果该顶点访问过就跳过
continue;
}
visits[finished[count-1]]=True;//置该顶点的访问状态为已访问
printf("%c",g.xlist[finished[count-1]].data);//打印该顶点的信息，其实就是对该顶点进行操作，访问
DFSRever(g,finished[count-1],finished);//调用函数遍历
printf("\n.........\n");
count--;//访问下一顶点
}
}
void DFSRever(struct OlGraph g,int i,int finished[]){
int j;
int getTailAdjVex(struct OlGraph g,int i);//声明查找以该顶点为头的弧的尾顶点的函数
for(j=getTailAdjVex(g, i);j>=0;j=getTailAdjVex(g, i)){
if(visits[j]==True){
continue;
}
visits[j]=True;
DFSRever(g,j,finished);//递归调用，查找i结点的邻接点的邻接点
printf("%c",g.xlist[j].data);//访问i结点的邻接点
}
}
void DFS(struct OlGraph g,int i,int finished[]){
visits[i]=True;
int w;
int getHeadAdjVex(struct OlGraph g,int i);//声明以该结点为尾的弧的头结点的函数
for(w=getHeadAdjVex(g,i);w>=0;w=getHeadAdjVex(g,i)){
if(visits[w]==True){
continue;
}
DFS(g,w,finished);//递归调用，其实就是深度遍历
}
finished[count++]=i;//退出函数时把该结点存储到finished数组中
}
/*
查找以该结点为尾的弧的头结点
*/
int getHeadAdjVex(struct OlGraph g,int i){
struct ArcBox * p=g.xlist[i].firstout;
if(p==NULL){
return -1;
}
//for(p=g.xlist[i].firstout;p->mark==True;p=p->tlink);
while(p->mark==True){
p=p->tlink;
if(p==NULL){
return -1;
}
}
p->mark=True;
return p->headvex;
}
/*
查找以该顶点为头的弧的尾顶点
*/
int getTailAdjVex(struct OlGraph g,int i){
struct ArcBox * p=g.xlist[i].firstin;
if(p==NULL){
return -1;
}
//for(;p->mark==True;p=p->hlink);
while(p->mark==True){
p=p->hlink;
if(p==NULL){
return -1;
}
}
p->mark=True;
return p->tailvex;
}
main.c
#include <stdio.h>
#include "myhead.h"
int main(int argc, const char * argv[]){
//printf("你好");
struct OlGraph init(void);
void DFSTraverse(struct OlGraph g);
struct OlGraph g=init();
DFSTraverse(g);
return 0;
}
（结语：我主要是做java开发的，为什么用c语言来写关于有向图的操作呢？主要是大学里学过c，懂一点基础，为了能更深入了解c语言，业余时间就用c写点程序练习练习。个人感觉学好c语言有助于理解更高级的如java语言，java的虚拟机就是有用c语言写的。第二次记录点东西到****，如有不妥的地方，请帮忙指出。计算机的世界真的很精彩，我还需要努力的探索！加油，各位）