图--有向图的强连通分量实现

深度优先搜索遍历是求有向图的强连通分量的一个新的有效的方法。
描述：
1）在有向图G上，从某个顶点出发沿该顶点为尾的弧进行深度优先搜索遍历，并按其所有的邻接点的搜索的完成顺序将顶点排序起来。
2）在有向图G上，从最后完成搜索的顶点出发，沿着以该顶点为头的弧作逆向的深度优先搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历，一次类推，直至有向图中所有的顶点都被访问到为止。

实现：

#include <stdio.h>
#include <stdlib.h>

//图的邻接表存储表示
#define MAX_VERTEX_NUM 20
#define INF INT_MAX
typedef int InfoType;
typedef int VertexType;
typedef struct ArcNode{
	int adjvex; //邻接点序号
	int value; //表示边的权值
	struct ArcNode* nexttarc; //下一条边的顶点
	InfoType *info;
};
typedef struct VNode{  
	VertexType data;    //顶点信息 
	ArcNode *firsttarc;  //指向第一条边节点
}VNode, AdjList[MAX_VERTEX_NUM];  //单链表的头结点类型

typedef struct{
	AdjList Vertices;   //单链表头结点数组
	int vexnum, arcnum;  //实际的顶点数vexnum 边数arcnum
	int kind;
}ALGraph;

int visited[MAX_VERTEX_NUM];
int finished[MAX_VERTEX_NUM];
int count;
#define LENGTH 4
#define ARCLENGTH 5

int graph[LENGTH][LENGTH] = {
	INF, 1, 1, INF,
	INF, INF, INF, INF,
	1, INF, INF, INF,
	1, INF, 1, INF
};
/*深度优先搜索遍历DFS*/
void DFS(ALGraph G, int v){
	visited[v] = true;
	printf("v%d-->", v);
	ArcNode * p = G.Vertices[v].firsttarc;
	while(p!=NULL){
		if (!visited[p->adjvex]){
			DFS(G, p->adjvex);
		}
		p = p->nexttarc;
	}
	printf("^\n");
}
void DFSTraverse(ALGraph G){
	for (int v = 0; v < G.vexnum; v++){
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; v++){
		if (!visited[v]){
			DFS(G, v);
		}
	}
}


//求解强连通分量
/*DFS finished记录深度优先搜索的路径*/
void FORST_DFS(ALGraph G, int v){
	visited[v] = true;
	printf("v%d", v);
	ArcNode * p = G.Vertices[v].firsttarc;
	while (p != NULL){
		if (!visited[p->adjvex]){
			FORST_DFS(G, p->adjvex);
		}
		p = p->nexttarc;
	}
	finished[count] = v; 
	count++;	
}
void FORST_DFSTraverse(ALGraph G){
	count = 0;
	for (int v = 0; v < G.vexnum; v++){
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; v++){
		if (!visited[v]){
			FORST_DFS(G, v);
		}
	}
}
//有向图强连通分量
void Director_FORST(ALGraph G){
	//首先正向遍历图，然后用finished数组标记访问顺序。
	FORST_DFSTraverse(G);
	printf("\n");
	for (int i = 0; i < G.vexnum; i++){
		printf("%d ", finished[i]);
	}
	//求解强连通分量，逆向遍历图
	for (int v = 0; v < G.vexnum; v++){
		visited[v] = false;
	}
	for (int v = finished[G.vexnum - 1]; v >= 0; v--){
		if (!visited[v]){
			printf("\n");
			DFS(G, v);
		}
	}
}

void CreateGraph(ALGraph &G){
	G.vexnum = LENGTH;
	G.arcnum = ARCLENGTH;
	//初始化顶点的信息
	for (int i = 0; i < G.vexnum; i++){
		G.Vertices[i].data = i;
		G.Vertices[i].firsttarc = NULL;
	}
	for (int i = 0; i < LENGTH; i++){
		for (int j = LENGTH-1; j >= 0; j--){
			if (graph[i][j] != INF){
				ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = j ;
				p->value = graph[i][j];
				p->nexttarc = G.Vertices[i].firsttarc;
				G.Vertices[i].firsttarc = p;
			}
		}
	}
}
void DisplayerGraph(ALGraph &G){
	int i = 0;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++){
		printf("顶点[V%d]的邻接边 ",G.Vertices[i].data);
		p = G.Vertices[i].firsttarc;
		while (p){
			printf("-->(%d,%d)", p->adjvex, p->value);
			p = p->nexttarc;
		}
		printf("-->(^)\n");
	}
}

int main(){
	ALGraph  *G;
	G = (ALGraph*)malloc(sizeof(ALGraph));
	CreateGraph(*G);
	DisplayerGraph(*G);	
	printf("深度优先搜索：\n");
	DFSTraverse(*G);
	printf("^\n强连通分量求解\n");
	Director_FORST(*G);

	return 1;
}