DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法。分享给大家供大家参考。具体方法如下：
|
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
|
#include <iostream>#include <algorithm>#include <iterator>using namespace std; #define MAX_VERTEX_NUM 10struct Node{ int adjvex; struct Node *next; int info;};typedef struct VNode{ char data; Node *first;}VNode, AdjList[MAX_VERTEX_NUM];struct Graph { AdjList vertices; int vexnum, arcnum;};int visited[MAX_VERTEX_NUM];int locateVex(Graph G, char u){ int i; for (i = 0; i < G.vexnum; i++) { if (u == G.vertices[i].data) return i; } if (i == G.vexnum) { printf("Error u!\n"); exit(1); } return 0;}void createGraph(Graph &G){ int i, j, k, w; char v1, v2, enter; Node *p; printf("input vexnum & arcnum:\n"); scanf("%d", &G.vexnum); scanf("%d", &G.arcnum); printf("input vertices:\n"); for (i = 0; i < G.vexnum; i++) { scanf("%c%c", &enter, &G.vertices[i].data); G.vertices[i].first = NULL; } printf("input Arcs(v1, v2, w):\n"); for (k = 0; k < G.arcnum; k++) { scanf("%c%c", &enter, &v1); scanf("%c%c", &enter, &v2); scanf("%d", &w); i = locateVex(G, v1); j = locateVex(G, v2); p = (Node *)malloc(sizeof(Node)); p->adjvex = j; p->info = w; p->next = G.vertices[i].first; G.vertices[i].first = p; }}void DFS(Graph &G, int v){ Node *p; printf("%c", G.vertices[v].data); visited[v] = 1; p = G.vertices[v].first; while (p) { if (!visited[p->adjvex]) DFS(G, p->adjvex); p = p->next; }}void DFSTranverse(Graph &G){ for (int v = 0; v < G.vexnum; v++) visited[v] = 0; for (int v = 0; v < G.vexnum; v++) { if (!visited[v]) DFS(G, v); }}int main(){ Graph G; createGraph(G); DFSTranverse(G);} |
再换一种方式来写DFS。具体代码如下：
|
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
|
#include <iostream>#include <string>using namespace std;#define MAXLEN 10struct Node{ int data; Node *next;};struct Link{ int count; string name; Node *head;};struct Graph{ Link link[MAXLEN]; int vexnum; int arcnum;};int findIndex(Graph &G, string name){ int index = -1; for (int i = 0; i < G.vexnum; i++) { if (G.link[i].name == name) { index = i; break; } } if (index == -1) cout << "error" << endl; return index;}void constructGraph(Graph &G){ cout << "construct graph yooo" << endl; cout << "enter vexnum" << endl; cin >> G.vexnum; string array[] = {"v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"}; const int size = sizeof array / sizeof *array; for (int i = 0; i < G.vexnum; i++) { G.link[i].name = array[i]; G.link[i].head = NULL; } string leftName; string rightName; cout << "enter a pair" << endl; cin >> leftName >> rightName; while (leftName != "end" && rightName != "end") { int leftIndex = findIndex(G, leftName); int rightIndex = findIndex(G, rightName); Node *node = new Node; node->data = rightIndex; node->next = NULL; node->next = G.link[leftIndex].head; G.link[leftIndex].head = node; cout << "enter a pair" << endl; cin >> leftName >> rightName; }}bool flag[MAXLEN];void DFSTranverse(Graph &G, int num){ cout << G.link[num].name << " "; flag[num] = true; Node *head = G.link[num].head; while (head != NULL) { int index = head->data; if (!flag[index]) DFSTranverse(G, index); head = head->next; }}void main(){ Graph G; constructGraph(G); for (int i = 0; i < MAXLEN; i++) flag[i] = false; DFSTranverse(G, 0);} |
DFS的迭代遍历算法如下：
|
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
|
void DFS(Graph &G){ stack<int> istack; istack.push(0); cout << G.link[0].name << " "; flag[0] = true; while (!istack.empty()) { int index = istack.top(); Node *head = G.link[index].head; while (head != NULL && flag[head->data] == true) head = head->next; if (head != NULL) { index = head->data; if (!flag[index]) { cout << G.link[index].name << " "; flag[index] = true; istack.push(index); } } else istack.pop(); }} |
感性的朋友可以测试运行一下本文实例代码以加深印象，相信本文所述对大家C程序算法设计的有一定的借鉴价值。
