前言

为什么要使用C语言

因为c语言中基本没有数据结构, 所有的数据结构都需要自己来定义, 看一个人有没有真正的理解这个算法, 那么用C语言能写出来就算是真正的明白了这个算法的过程, 所以c语言是检验技术的一个有力的方法

为什么要弄明白这些算法

我的一个老师说过, 会底层的才是人才, 应用都是最基础的, 都是小儿科 核心思想在别人那里想给你用就给你用, 不给你用你也没有办法.

简要说明

BFS和DFS是数据结构中图的遍历中使用的算法, 跟二叉树的遍历有着异曲同工之妙.

BFS

BFS, Breadth First Search, 广度优先遍历, 遍历思路为: 从最开始遍历的结点开始, 按顺序一次找到所有的距离当前结点最近的结点, 知道所有的结点都被遍历完成.

这样的话我们可以用一个队列的数据结构来实现这个BFS遍历方法

队列 -> BFS

  1. 将开始访问的结点放入队头中
  2. 将队头的临接结点放入队列中
  3. 开始的结点pop弹出
  4. 重复2, 3直到队列为空
  5. 注意: 每次只pop弹出一个元素, 放入所有的邻接结点, 队列中的元素不重复(逻辑)

DFS

DFS, Deepth First Search, 深度优先遍历, 遍历思路为: 从最开始遍历的结点, 一条路走到黑, 知道五路可走, 再返回一个有路的结点, 最新的路(也就是访问未访问的结点), 直到所有的结点都被访问/(遍历)过

与BFS相似, 我们可以用一个栈的数据结构来实现这个DFS算法

栈 -> DFS

  1. 将开始访问的结点的放入栈中
  2. 将栈中的一个元素pop弹出,
  3. 当前弹出的元素的邻接结点全部放入栈中
  4. 重复2, 3, 直到栈为空
  5. 注意: 每次在栈中只pop一个元素, 放入的不一定是一个, 栈中的元素不重复(逻辑).

代码实现

测试图

在这里插入图片描述

代码+测试主方法

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
/*
***********************************************************************
******************** Breadth First Search and *************************
******************** Deepth First Search ******************************
******************** Author : Lutong99 ********************************
***********************************************************************
*/

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

// set length of stack or queue
#define MAX_SIZE 32

// Stack data structure
typedef struct stack {
	int length;
	char datas[MAX_SIZE];
} Stack;

// Queue data structure
typedef struct queue {
	int front;
	int rear;
	char datas[MAX_SIZE];
} Queue;

// Graph node data structure
typedef struct node {
	char data;
	struct node* next;
} Node; 

// Graph data structure
typedef struct graph {
	int numNodes;
	// adjacency list
	Node* adjLists[128];
	int visited[128];
} Graph;

/**
 * Create a stack with no element
 */
Stack* create_stack() {
	return malloc(sizeof(Stack));
}

/**
 * Create a queue with no elment
 */
Queue* create_queue() {
	return malloc(sizeof(Queue));
}

/**
 * Create an node with a element
 */
Node* create_node(char value) {
	Node* node = malloc(sizeof(Node));
	node -> data = value;
	node -> next = NULL;
	return node;
}

/**
 * Create Graph with number of vertices
 * @param n number of vertices
 */
Graph* create_graph(int n) {
	Graph* graph = malloc(sizeof(Graph));
	graph -> numNodes = n;
/*
	It is not necessary
	graph -> adjLists = malloc(n * sizeof(Node));
	graph -> visited = malloc(n * sizeof(Node));

	int i;
	for (i = 0; i < n; i++) {
		// No Nodes, no visiting
		graph -> adjLists[i] = NULL;
		graph -> visited[i] = 0;
	}
*/	
	return graph;
}

/**
 * Add edges to a graph
 * @param graph the specified graph to add
 * @param start start node in an edge
 * @param end end node in an edge
 */
void add_edge(Graph* graph, char start, char end) {
	// Add edge from start to end 
	Node* node = create_node(end);
	node -> next = graph -> adjLists[start];
	graph -> adjLists[start] = node;

	// Add edge from end to start
	node = create_node(start);
	node -> next = graph -> adjLists[end];
	graph -> adjLists[end] = node;
}

/**
 * insert a value into a Stack
 * @param stack which stack you will insert into
 * @param value what you want to insert
 */
void push_s(Stack* stack, char value) {
	if (stack -> length != MAX_SIZE) {
		stack -> datas[stack -> length++] = value;
	} else {
		printf("stack overflow!!");
	}
}

/**
 * decide if a queue is full
 * @return {@code 1} is full <br>
 * 		   {@code 0} is not full
 */
int is_full_q(Queue* queue) {
	if (queue -> rear == MAX_SIZE - 1) {
		return 1;
	} 
	else {
		return 0;
	}
}

/**
 * decide if a queue is empty
 * @return {@code 1} is empty
 *         {@code 0} is not empty
 */
int is_empty_q(Queue* queue) {
	if (queue -> front == queue -> rear) {
		return 1;
	}
	else {
		return 0;
	}
}

/**
 * decide if a stack is empty
 * @return {@code 1} is empty
 *         {@code 0} is not empty
 */
int is_empty_s(Stack* stack) {
	if (stack -> length == 0) {
		return 1;
	}
	else {
		return 0;
	}
}

/**
 * insert a value into a Queue
 * @param queue which queue you will insert into
 * @param value what you will insert
 */
void push_q(Queue* queue, char value) {
	if (!is_full_q(queue)) {
		queue -> datas[queue -> rear++] = value;
	} else {
		printf("Queue is full");
	}
}

/**
 * pop element from first
 * @param queue where you will pop
 * @return the first element 
 */
char pop_q(Queue* queue) {
	if (queue -> front != queue -> rear) {
		return queue -> datas[queue -> front++];
	} else {
		return -1;
	}
}

/**
 * pop the end element of a Stack
 * @param stack you will get its last element
 * @return the last element of {@code stakc}
 */
char pop_s(Stack* stack) {
	if (stack -> length != 0) {
		return stack -> datas[--stack -> length];
	} else {
		return -1;
	}
}

/** 
 * Breadth first search
 * @param graph specified graph made bfs
 * @param start start vertex in bfs
 */
void bfs(Graph* graph, char start) {
	Queue* queue = create_queue();
	graph -> visited[start] = 1;
	push_q(queue, start);

	while(!is_empty_q(queue)) {
		char current = pop_q(queue);
		printf("%c\n", current);
		Node* temp = graph -> adjLists[current];

		while (temp != NULL) {
			// Traverse the whole graph
			char adjD = temp -> data;
			if (graph -> visited[adjD] == 0) {
				graph -> visited[adjD] = 1;
				push_q(queue, adjD);
			}
			temp = temp -> next;
		}
	}
}

/** 
 * Deepth first search
 * @param graph specified graph made bfs
 * @param start start vertex in bfs
 */
void dfs(Graph* graph, char start) {
	// Queue* queue = create_queue();
	Stack* stack = create_stack();
	graph -> visited[start] = 1;
	push_s(stack, start);

	while(!is_empty_s(stack)) {
		char current = pop_s(stack);
		printf("%c\n", current);
		Node* temp = graph -> adjLists[current];

		while (temp != NULL) {
			// Traverse the whole graph
			int adjD = temp -> data;
			if (graph -> visited[adjD] == 0) {
				graph -> visited[adjD] = 1;
				push_s(stack, adjD);
			}
			temp = temp -> next;
		}
	}
}

/*
	
*/
int main() {
	Graph* graph = create_graph(5);
	add_edge(graph, 'A', 'B');
	add_edge(graph, 'A', 'C');
	add_edge(graph, 'B', 'C');
	add_edge(graph, 'B', 'D');
	add_edge(graph, 'C', 'D');
	add_edge(graph, 'C', 'E');
	add_edge(graph, 'D', 'E');
	add_edge(graph, 'D', 'F');
	bfs(graph, 'B');
	return 0;
}