热门标签
当前位置: article > 正文
【经典算法实现 31】图的遍历 --- 深度优先遍历算法
作者：IT小白 | 2024-04-29 20:46:52
赞
踩
深度优先遍历算法
【经典算法实现 31】图的遍历 --- 深度优先遍历算法
本文接着《【经典算法实现 30】图的创建 — 十字链表法》，
在它的基础上来实现 深度优先算法 与 广度优先算法。
先上图
一、深度优先遍历算法
1.1 实现思路
- 假设提供的第一个节点就是A.
- 通过
A找到B，将A放入栈，此时栈内容为：A - 通过
B找到D，将B放入栈，此时栈内容为：BA - 通过
D找到E，将D放入栈，此时栈内容为：DBA - 通过
E找到G，将E放入栈，此时栈内容为：EDBA G找不到其他的节点了，G不用入栈，此时开始弹出数据。- 弹出
E，E也找不到其他的节点了， - 弹出
D，D找到F，将D再次入栈，此时栈内容为：DBA - 通过
F找到C，将F 放入栈，此时栈内容为：FDBA - 通过
C发现其他几个节点都已经在栈中，说明都找过了，找不到其他结点，此时开始弹栈 - 弹出
F，找不到其他未走过的节点 - 弹出
D，找不到其他未走过的节点 - 弹出
B，找不到其他未走过的节点 - 弹出
A，找不到其他未走过的节点 - 此时栈为空了，说明遍历结束
该次遍历的顺序为： A -> B -> D-> E -> G ->F -> C
1.2 栈代码实现
//图********************************************************************** // 这部分的代码就是《【经典算法实现 30】图的创建 --- 十字链表法》 ，此处省略 。。。。。。 // 栈代码 *********************************************************************** // 实现一个 10 个元素的循环队列 #define Queue_Size 10 typedef struct List{ pNode * node; struct List *next; struct List *pre; }List; // 定义循环队列的头部和尾部 List * list_head = NULL; List * list_tail = NULL; // 往list后添加新的节点，list为队尾节点 List * Insert_pNode(List *list){ List *p; if(list == NULL){ return NULL; } p = (List *)malloc(sizeof(List)); p->node = NULL; p->next = list->next; p->pre = list->next->pre; list->next->pre = p; list->next = p; return p; } List * New_List_Queue(int size){ List * list; int i; if(size == 0) return NULL; printf("\n%s -- size=%d\n",__func__, size); // 创建头节点，单向循环链表头节点指向自已 list = (List *)malloc(sizeof(List)); list->node = NULL; list->next = list; list->pre = list; list_head = list; //队头指向 list list_tail = list; //队尾指向 list //创建剩余的节点 for(i = 0; i<size-1; i++){ list = Insert_pNode(list); } printf("\n列表创建完毕\n"); //创建完毕，返回list 的头结点，即 list->next，因为list即最后一个节点 return list->next; } void Delete_List_Queue(List *list){ List *p; while(list->next != list){ p = list->next; list->next = p->next; list->next->pre = p->pre; printf("\n释放ListQueue：%p", p); free(p); } printf("\n释放ListQueue：%p\n\n", list); free(list); } //向队尾指针添加 Node节点 void Push_Node(pNode *node){ List *p = NULL; // 如果队列满了，则自动扩充队列 if(list_tail == list_head && list_head->node != NULL){ // 找到list_head 的前一个节点 p = list_head; while(p->next != list_head) p = p->next; // 在队尾插入节点，返回队尾指针 list_tail = Insert_pNode(p); printf("\n队列容量已满，增加一个元素, list_tail=%p, list_head=%p\n", list_tail, list_head); } if(list_tail != NULL){ printf("\n插入元素 %c, list_head(%p), list_tail(%p)",node->data, list_head,list_tail ); list_tail->node = node; list_tail = list_tail->next; } } //队列：从队头取出一个 Node节点，队列无数据时，返回NULL，即先进先出 pNode * Pop_Queue(){ pNode *node; if(list_head != NULL && list_head->node != NULL){ node = list_head->node; list_head->node = NULL; list_head = list_head->next; return node; } return NULL; } //栈: 从队尾取出一个 Node节点，队列无数据时，返回NULL，即先进后出 pNode * Pop_Stack(){ pNode *node; if(list_tail->pre != NULL && list_tail->pre->node != NULL){ node = list_tail->pre->node; list_tail->pre->node = NULL; list_tail = list_tail->pre; return node; } return NULL; }
- 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
测试程序
int main() { int i; // 创建边 sNode **s = Create_sNode(); // 创建顶点 pNode *node, **p = Create_pNode(s); // 打印节点及其关系 List *p_list, *list = New_List_Queue(Queue_Size); for(i = 0; i<pNode_Num; i++){ Push_Node(p[i]); } printf("\n\n栈后进先出\n"); for(i = 0; i<pNode_Num; i++){ node = Pop_Stack(); printf("%c -- ", node->data); } printf("\n\n"); return 0; }
- 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
运行结果:
New_List_Queue -- size=10
列表创建完毕
插入元素 A, list_head(001F04B0), list_tail(001F04B0)
插入元素 B, list_head(001F04B0), list_tail(001F1030)
插入元素 C, list_head(001F04B0), list_tail(001F1048)
插入元素 D, list_head(001F04B0), list_tail(001F1018)
插入元素 E, list_head(001F04B0), list_tail(001F10A8)
插入元素 F, list_head(001F04B0), list_tail(001F1060)
插入元素 G, list_head(001F04B0), list_tail(001F1168)
栈后进先出
G -- F -- E -- D -- C -- B -- A --
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
1.3 深度优先遍历算法代码实现
// 深度优先遍历算法 , 栈实现 void DFS(pNode **p) { int i, flag=0; pNode *node; sNode *snode; char find_list[pNode_Num], *f=find_list; // 用于保存遍历的顺序 // 将 p[0] 入栈 Push_Node(p[0]); *f++ = p[0]->data; // 只要栈不为空，循环遍历 while(list_head->node != NULL){ // 从栈取出一个节点，获得该节点的下一个节点字符 node = Pop_Stack(); snode = node->firstOut; // 判断下一个节点 while(snode != NULL){ // 判断该节点是否访问过，即是否在 find_list[] 数组中 for(i = 0, flag=0; i<pNode_Num; i++) if(find_list[i] == snode->headvex) flag = 1; printf("\n下一个节点，%c ,flag=%d", snode->headvex, flag); // 判断下一个节点是否在栈中 if( flag == 0){ // 不在数组中，说明找到了一个新节点 Push_Node(node); // 将当前节点重新入栈 // 找到新字符的节点 for(i = 0; i<pNode_Num; i++){ if(p[i]->data == snode->headvex){ Push_Node(p[i]); // 将新节点入栈 *f++ = p[i]->data; snode = NULL; // 将snode 给Null 退出循环 break; } } }else snode = snode->tlink; // 在数组中，说明该节点访问过了 } } printf("\n\n深度遍历完毕,遍历顺序为: \n"); for(i = 0; i<pNode_Num; i++){ printf("%c -> ", find_list[i]); } }
- 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
二、完整代码实现
// 十字链表法实现图的保存 #include <stdio.h> //图********************************************************************** // 边结构体 typedef struct sNode{ char tailvex; // 该边的起点， 如 A->B 这条边，此处保存 A char headvex; // 该边的终点， 如 A->B 这条边，此处保存 B struct sNode *tlink; // 出表指针链表，指同起点所有边的链表，比如 A->B 和 A->C，它们的起点相同都是A struct sNode *hlink; // 入表指针链表，指同终点的所有边的链表，比如 B->D 和 C->D，它们的终点相同都是D }sNode; // 顶点结构体 typedef struct pNode{ char data; // 顶点字符，如 A struct sNode *firstIn; // 入边结构体指针链表， 指向第一条入边的结构体指针 struct sNode *firstOut; // 出边结构体指针链表， 指向第一条出边的结构体指针 }pNode; #define pNode_Num 7 // 7个顶点 #define sNode_Num 9 // 9条边 const char c_char[pNode_Num] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; const char s_char[sNode_Num][2]={ {'A','B'}, {'A','C'}, {'B','D'}, {'B','A'}, {'C','D'}, {'D','E'}, {'D','F'}, {'E','G'}, {'F','C'}}; // 创建边 sNode ** Create_sNode(){ int i; sNode **s; s = (sNode **)malloc(sizeof(sNode *) * sNode_Num); for(i = 0; i<sNode_Num; i++){ s[i] = (sNode *)malloc(sizeof(sNode)); s[i]->tailvex = s_char[i][0]; s[i]->headvex = s_char[i][1]; s[i]->tlink = NULL; s[i]->hlink = NULL; printf("sNode[%d]: \'%c\'->\'%c\' - %p - %p\n",i, s[i]->tailvex, s[i]->headvex, s[i]->tlink, s[i]->hlink); } printf("\n\n"); return s; } // 创建顶点 pNode ** Create_pNode(sNode **s){ int i, j; pNode **p; sNode *s_tmp=NULL; p = (pNode **)malloc(sizeof(pNode *) * pNode_Num); for(i = 0; i<pNode_Num; i++){ p[i] = (pNode *)malloc(sizeof(pNode)); p[i]->data = c_char[i]; p[i]->firstIn = NULL; p[i]->firstOut = NULL; // 找出当前节点所有的出边，以当前节点为起始点 for(j = 0; j<sNode_Num; j++){ if(p[i]->data == s[j]->tailvex) { if(p[i]->firstOut == NULL){ p[i]->firstOut = s[j]; s_tmp = p[i]->firstOut; } else{ s_tmp->tlink = s[j]; } } } // 找出当前节点所有的入边，以当前节点为起始点 for(j = 0; j<sNode_Num; j++){ if(p[i]->data == s[j]->headvex) { if(p[i]->firstIn == NULL){ p[i]->firstIn = s[j]; s_tmp = p[i]->firstIn; } else{ s_tmp->hlink = s[j]; } } } // 打印节点关系 printf("pNode[%d]: \'%c\' - %p - %p\nfirstIn : ",i, p[i]->data, p[i]->firstIn, p[i]->firstOut); s_tmp = p[i]->firstIn; while(s_tmp != NULL){ printf(" --> [\'%c\'->\'%c\']", s_tmp->tailvex, s_tmp->headvex); s_tmp = s_tmp->hlink; } printf("\nfirstOut: "); s_tmp = p[i]->firstOut; while(s_tmp != NULL){ printf(" --> [\'%c\'->\'%c\']", s_tmp->tailvex, s_tmp->headvex); s_tmp = s_tmp->tlink; } printf("\n\n\n"); } printf("\n\n"); return p; } // 栈代码 *********************************************************************** // 实现一个 10 个元素的循环队列 #define Queue_Size 10 typedef struct List{ pNode * node; struct List *next; struct List *pre; }List; // 定义循环队列的头部和尾部 List * list_head = NULL; List * list_tail = NULL; // 往list后添加新的节点，list为队尾节点 List * Insert_pNode(List *list){ List *p; if(list == NULL){ return NULL; } p = (List *)malloc(sizeof(List)); p->node = NULL; p->next = list->next; p->pre = list->next->pre; list->next->pre = p; list->next = p; return p; } List * New_List_Queue(int size){ List * list; int i; if(size == 0) return NULL; printf("\n%s -- size=%d\n",__func__, size); // 创建头节点，单向循环链表头节点指向自已 list = (List *)malloc(sizeof(List)); list->node = NULL; list->next = list; list->pre = list; list_head = list; //队头指向 list list_tail = list; //队尾指向 list //创建剩余的节点 for(i = 0; i<size-1; i++){ list = Insert_pNode(list); } printf("\n列表创建完毕\n"); //创建完毕，返回list 的头结点，即 list->next，因为list即最后一个节点 return list->next; } void Delete_List_Queue(List *list){ List *p; while(list->next != list){ p = list->next; list->next = p->next; list->next->pre = p->pre; printf("\n释放ListQueue：%p", p); free(p); } printf("\n释放ListQueue：%p\n\n", list); free(list); } //向队尾指针添加 Node节点 void Push_Node(pNode *node){ List *p = NULL; // 如果队列满了，则自动扩充队列 if(list_tail == list_head && list_head->node != NULL){ // 找到list_head 的前一个节点 p = list_head; while(p->next != list_head) p = p->next; // 在队尾插入节点，返回队尾指针 list_tail = Insert_pNode(p); printf("\n队列容量已满，增加一个元素, list_tail=%p, list_head=%p\n", list_tail, list_head); } if(list_tail != NULL){ printf("\n插入元素 %c, list_head(%p), list_tail(%p)",node->data, list_head,list_tail ); list_tail->node = node; list_tail = list_tail->next; } } //队列：从队头取出一个 Node节点，队列无数据时，返回NULL，即先进先出 pNode * Pop_Queue(){ pNode *node; if(list_head != NULL && list_head->node != NULL){ node = list_head->node; list_head->node = NULL; list_head = list_head->next; printf("\n弹出元素 %c",node->data); return node; } return NULL; } //栈: 从队尾取出一个 Node节点，队列无数据时，返回NULL，即先进后出 pNode * Pop_Stack(){ pNode *node; if(list_tail->pre != NULL && list_tail->pre->node != NULL){ node = list_tail->pre->node; list_tail->pre->node = NULL; list_tail = list_tail->pre; printf("\n弹出元素 %c",node->data); return node; } return NULL; } // 深度优先遍历算法 , 栈实现 void DFS(pNode **p) { int i, flag=0; pNode *node; sNode *snode; char find_list[pNode_Num], *f=find_list; // 用于保存遍历的顺序 // 将 p[0] 入栈 Push_Node(p[0]); *f++ = p[0]->data; // 只要栈不为空，循环遍历 while(list_head->node != NULL){ // 从栈取出一个节点，获得该节点的下一个节点字符 node = Pop_Stack(); snode = node->firstOut; // 判断下一个节点 while(snode != NULL){ // 判断该节点是否访问过，即是否在 find_list[] 数组中 for(i = 0, flag=0; i<pNode_Num; i++) if(find_list[i] == snode->headvex) flag = 1; printf("\n下一个节点，%c ,flag=%d", snode->headvex, flag); // 判断下一个节点是否在栈中 if( flag == 0){ // 不在数组中，说明找到了一个新节点 Push_Node(node); // 将当前节点重新入栈 // 找到新字符的节点 for(i = 0; i<pNode_Num; i++){ if(p[i]->data == snode->headvex){ Push_Node(p[i]); // 将新节点入栈 *f++ = p[i]->data; snode = NULL; // 将snode 给Null 退出循环 break; } } }else snode = snode->tlink; // 在数组中，说明该节点访问过了 } } printf("\n\n深度遍历完毕,遍历顺序为: \n"); for(i = 0; i<pNode_Num; i++){ printf("%c -> ", find_list[i]); } } int main() { int i; // 创建边 sNode **s = Create_sNode(); // 创建顶点 pNode *node, **p = Create_pNode(s); // 打印节点及其关系 List *p_list, *list = New_List_Queue(Queue_Size); DFS(p); printf("\n\n"); return 0; }
- 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
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
2.1 运行结果
sNode[0]: 'A'->'B' - 00000000 - 00000000 sNode[1]: 'A'->'C' - 00000000 - 00000000 sNode[2]: 'B'->'D' - 00000000 - 00000000 sNode[3]: 'B'->'A' - 00000000 - 00000000 sNode[4]: 'C'->'D' - 00000000 - 00000000 sNode[5]: 'D'->'E' - 00000000 - 00000000 sNode[6]: 'D'->'F' - 00000000 - 00000000 sNode[7]: 'E'->'G' - 00000000 - 00000000 sNode[8]: 'F'->'C' - 00000000 - 00000000 pNode[0]: 'A' - 00660E30 - 00660DE8 firstIn : --> ['B'->'A'] firstOut: --> ['A'->'B'] --> ['A'->'C'] pNode[1]: 'B' - 00660DE8 - 00660E18 firstIn : --> ['A'->'B'] firstOut: --> ['B'->'D'] --> ['B'->'A'] pNode[2]: 'C' - 00660E00 - 00660E48 firstIn : --> ['A'->'C'] --> ['F'->'C'] firstOut: --> ['C'->'D'] pNode[3]: 'D' - 00660E18 - 00660E60 firstIn : --> ['B'->'D'] --> ['C'->'D'] firstOut: --> ['D'->'E'] --> ['D'->'F'] pNode[4]: 'E' - 00660E60 - 00660E90 firstIn : --> ['D'->'E'] firstOut: --> ['E'->'G'] pNode[5]: 'F' - 00660E78 - 00660EA8 firstIn : --> ['D'->'F'] firstOut: --> ['F'->'C'] pNode[6]: 'G' - 00660E90 - 00000000 firstIn : --> ['E'->'G'] firstOut: New_List_Queue -- size=10 New_List_Queue -- size=10 列表创建完毕 插入元素 A, list_head(00B204B0), list_tail(00B204B0) 弹出元素 A 插入元素 A, list_head(00B204B0), list_tail(00B204B0) 插入元素 B, list_head(00B204B0), list_tail(00B20FD0) 弹出元素 B 插入元素 B, list_head(00B204B0), list_tail(00B20FD0) 插入元素 D, list_head(00B204B0), list_tail(00B21120) 弹出元素 D 插入元素 D, list_head(00B204B0), list_tail(00B21120) 插入元素 E, list_head(00B204B0), list_tail(00B21090) 弹出元素 E 插入元素 E, list_head(00B204B0), list_tail(00B21090) 插入元素 G, list_head(00B204B0), list_tail(00B21060) 弹出元素 G 弹出元素 E 弹出元素 D 插入元素 D, list_head(00B204B0), list_tail(00B21120) 插入元素 F, list_head(00B204B0), list_tail(00B21090) 弹出元素 F 插入元素 F, list_head(00B204B0), list_tail(00B21090) 插入元素 C, list_head(00B204B0), list_tail(00B21060) 弹出元素 C 弹出元素 F 弹出元素 D 弹出元素 B 弹出元素 A 深度遍历完毕,遍历顺序为: A -> B -> D -> E -> G -> F -> C -> 请按任意键继续. . .
- 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/509736
推荐阅读
相关标签
