深度优先搜索遍历是求有向图的强连通分量的一个新的有效的方法。
描述：
1）在有向图G上，从某个顶点出发沿该顶点为尾的弧进行深度优先搜索遍历，并按其所有的邻接点的搜索的完成顺序将顶点排序起来。
2）在有向图G上，从最后完成搜索的顶点出发，沿着以该顶点为头的弧作逆向的深度优先搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历，一次类推，直至有向图中所有的顶点都被访问到为止。
实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154#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;
}