行业知识
C语言数据结构与算法——深度、广度优先搜索（DFS、BFS）
2026-11-07 08:15:09
来源：互联网转载
���录
一、深度优先搜索（Depth-First-Search 简称：DFS）
无向图的深度优先搜索
有向图的深度优先搜索
二、广度优先搜索（Breadth-First-Search 简称：BFS）
无向图的广度优先搜索
有向图的广度优先搜索
深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）是两种常见的图遍历算法，它们在C语言中被广泛应用于解决各种数据结构和算法问题。这两种搜索算法都用于遍历图或树中的节点，以便查找特定的目标或执行其他相关任务。
一、深度优先搜索（Depth-First-Search 简称：DFS）
图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程。
无向图的深度优先搜索
1.1 遍历过程：
（1）从图中某个顶点v出发，访问v。
（2）找出刚才第一个被顶点访问的邻接点。访问该顶点。以这个顶点为新的顶点，重复此步骤，直到访问过的顶点没有未被访问过的顶点为止。
（3）返回到步骤（2）中的被顶点v访问的，且还没被访问的邻接点，找出该点的下一个未被访问的邻接点，访问该顶点。
（4）重复（2） （3） 直到每个点都被访问过，遍历结束。
例无权图：
第1步：访问A。
第2步：访问（A的邻接点）B。 在第1步访问A之后，接下来应该访问的是A的邻接点，即"B、F、E"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，B在"D、F和E"的前面，因此，先访问B。
第3步：访问（B的邻接点）C。在第2步访问B之后，接下来应该访问B的邻接点，即"F、D、C"中一个(A已经被访问过，就不算在内)。而由于C在D、F之前，先访问C。
第4步：访问（C的邻接点）D。在第3步访问C之后，接下来应该访问C的邻接点，即D。(B已经被访问过，就不算在内)。
第5步：访问（D的邻接点）E。
第6步：访问（E的邻接点）F。
故遍历结果为 A->B->C->D->E->F
有向图的深度优先搜索
第1步：访问A。
第2步：访问B。在访问A之后，接下来访问A的出边的另一个顶点，即顶点B。
第3步：访问C。 在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。
第4步：访问E。接下来访问C的出边的另一个顶点，即顶点E。
第5步：访问D。接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。
第6步：访问F。接下应该回溯"访问A的出边的另一个顶点F"。
第7步：访问G。
故遍历结果为A->b->c->E->D->F->G
二、广度优先搜索（Breadth-First-Search 简称：BFS）
广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。
它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。
无向图的广度优先搜索
第1步：访问A。
第2步：依次访问B,E,F。
在访问了A之后，接下来访问A的邻接点。顶点ABCDEFG按照顺序存储，B在"E和F"的前面，因此，先访问B。再访问完B之后，再依次访问E,F。
第3步：依次访问C,D。
在第2步访问完B,E,F之后，再依次访问它们的邻接点。首先访问B的邻接点C，再访问E的邻接点D。
因此访问顺序是:A->B->E->F->C->D
有向图的广度优先搜索
第1步：访问A。
第2步：访问B。
第3步：依次访问C,E,F。
在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。顶点ABCDEFG按照顺序存储，因此会先访问C，再依次访问E,F。
第4步：依次访问D,G。
在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。
因此访问顺序是：A->B->C->E->F->D->G
邻接矩阵图表示的"无向图"
/** * C: 邻接矩阵图表示的"无向图(Matrix Undirected Graph)" * * @author skywang * @date 2014/04/18 */#include #include #include #include #define MAX 100#define isLetter(a) ((((a)>='a')&&((a)='A')&&((a)vexnum = v; pG->edgnum = e; // 初始化"顶点" for (i = 0; i vexnum; i++) { printf("vertex(%d): ", i); pG->vexs[i] = read_char(); } // 初始化"边" for (i = 0; i edgnum; i++) { // 读取边的起始顶点和结束顶点 printf("edge(%d):", i); c1 = read_char(); c2 = read_char(); p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); if (p1==-1 || p2==-1) { printf("input error: invalid edge!\n"); free(pG); return NULL; } pG->matrix[p1][p2] = 1; pG->matrix[p2][p1] = 1; } return pG;}/* * 创建图(用已提供的矩阵) */Graph* create_example_graph(){ char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; int vlen = LENGTH(vexs); int elen = LENGTH(edges); int i, p1, p2; Graph* pG; // 输入"顶点数"和"边数" if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL ) return NULL; memset(pG, 0, sizeof(Graph)); // 初始化"顶点数"和"边数" pG->vexnum = vlen; pG->edgnum = elen; // 初始化"顶点" for (i = 0; i vexnum; i++) { pG->vexs[i] = vexs[i]; } // 初始化"边" for (i = 0; i edgnum; i++) { // 读取边的起始顶点和结束顶点 p1 = get_position(*pG, edges[i][0]); p2 = get_position(*pG, edges[i][1]); pG->matrix[p1][p2] = 1; pG->matrix[p2][p1] = 1; } return pG;}/* * 返回顶点v的第一个邻接顶点的索引，失败则返回-1 */static int first_vertex(Graph G, int v){ int i; if (v(G.vexnum-1)) return -1; for (i = 0; i = 0; w = next_vertix(G, i, w)) { if (!visited[w]) DFS(G, w, visited); } }/* * 深度优先搜索遍历图 */void DFSTraverse(Graph G){ int i; int visited[MAX]; // 顶点访问标记 // 初始化所有顶点都没有被访问 for (i = 0; i = 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点 { if (!visited[k]) { visited[k] = 1; printf("%c ", G.vexs[k]); queue[rear++] = k; } } } } printf("\n");}/* * 打印矩阵队列图 */void print_graph(Graph G){ int i,j; printf("Martix Graph:\n"); for (i = 0; i 邻接表表示的"无向图"
/** * C: 邻接表表示的"无向图(List Undirected Graph)" * * @author skywang * @date 2014/04/18 */#include #include #include #include #define MAX 100#define isLetter(a) ((((a)>='a')&&((a)='A')&&((a)next_edge; p->next_edge = node;}/* * 创建邻接表对应的图(自己输入) */LGraph* create_lgraph(){ char c1, c2; int v, e; int i, p1, p2; ENode *node1, *node2; LGraph* pG; // 输入"顶点数"和"边数" printf("input vertex number: "); scanf("%d", &v); printf("input edge number: "); scanf("%d", &e); if ( v (v * (v-1)))) { printf("input error: invalid parameters!\n"); return NULL; } if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL ) return NULL; memset(pG, 0, sizeof(LGraph)); // 初始化"顶点数"和"边数" pG->vexnum = v; pG->edgnum = e; // 初始化"邻接表"的顶点 for(i=0; ivexnum; i++) { printf("vertex(%d): ", i); pG->vexs[i].data = read_char(); pG->vexs[i].first_edge = NULL; } // 初始化"邻接表"的边 for(i=0; iedgnum; i++) { // 读取边的起始顶点和结束顶点 printf("edge(%d): ", i); c1 = read_char(); c2 = read_char(); p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); // 初始化node1 node1 = (ENode*)malloc(sizeof(ENode)); node1->ivex = p2; // 将node1链接到"p1所在链表的末尾" if(pG->vexs[p1].first_edge == NULL) pG->vexs[p1].first_edge = node1; else link_last(pG->vexs[p1].first_edge, node1); // 初始化node2 node2 = (ENode*)malloc(sizeof(ENode)); node2->ivex = p1; // 将node2链接到"p2所在链表的末尾" if(pG->vexs[p2].first_edge == NULL) pG->vexs[p2].first_edge = node2; else link_last(pG->vexs[p2].first_edge, node2); } return pG;}/* * 创建邻接表对应的图(用已提供的数据) */LGraph* create_example_lgraph(){ char c1, c2; char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; int vlen = LENGTH(vexs); int elen = LENGTH(edges); int i, p1, p2; ENode *node1, *node2; LGraph* pG; if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL ) return NULL; memset(pG, 0, sizeof(LGraph)); // 初始化"顶点数"和"边数" pG->vexnum = vlen; pG->edgnum = elen; // 初始化"邻接表"的顶点 for(i=0; ivexnum; i++) { pG->vexs[i].data = vexs[i]; pG->vexs[i].first_edge = NULL; } // 初始化"邻接表"的边 for(i=0; iedgnum; i++) { // 读取边的起始顶点和结束顶点 c1 = edges[i][0]; c2 = edges[i][1]; p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); // 初始化node1 node1 = (ENode*)malloc(sizeof(ENode)); node1->ivex = p2; // 将node1链接到"p1所在链表的末尾" if(pG->vexs[p1].first_edge == NULL) pG->vexs[p1].first_edge = node1; else link_last(pG->vexs[p1].first_edge, node1); // 初始化node2 node2 = (ENode*)malloc(sizeof(ENode)); node2->ivex = p1; // 将node2链接到"p2所在链表的末尾" if(pG->vexs[p2].first_edge == NULL) pG->vexs[p2].first_edge = node2; else link_last(pG->vexs[p2].first_edge, node2); } return pG;}/* * 深度优先搜索遍历图的递归实现 */static void DFS(LGraph G, int i, int *visited){ int w; ENode *node; visited[i] = 1; printf("%c ", G.vexs[i].data); node = G.vexs[i].first_edge; while (node != NULL) { if (!visited[node->ivex]) DFS(G, node->ivex, visited); node = node->next_edge; }}/* * 深度优先搜索遍历图 */void DFSTraverse(LGraph G){ int i; int visited[MAX]; // 顶点访问标记 // 初始化所有顶点都没有被访问 for (i = 0; i ivex; if (!visited[k]) { visited[k] = 1; printf("%c ", G.vexs[k].data); queue[rear++] = k; } node = node->next_edge; } } } printf("\n");}/* * 打印邻接表图 */void print_lgraph(LGraph G){ int i,j; ENode *node; printf("List Graph:\n"); for (i = 0; i ivex, G.vexs[node->ivex].data); node = node->next_edge; } printf("\n"); }}void main(){ LGraph* pG; // 自定义"图"(自己输入数据) //pG = create_lgraph(); // 采用已有的"图" pG = create_example_lgraph(); // 打印图 print_lgraph(*pG); DFSTraverse(*pG); BFS(*pG);} 邻接矩阵表示的"有向图"
/** * C: 邻接矩阵表示的"有向图(Matrix Directed Graph)" * * @author skywang * @date 2014/04/18 */#include #include #include #include #define MAX 100#define isLetter(a) ((((a)>='a')&&((a)='A')&&((a)vexnum = v; pG->edgnum = e; // 初始化"顶点" for (i = 0; i vexnum; i++) { printf("vertex(%d): ", i); pG->vexs[i] = read_char(); } // 初始化"边" for (i = 0; i edgnum; i++) { // 读取边的起始顶点和结束顶点 printf("edge(%d):", i); c1 = read_char(); c2 = read_char(); p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); if (p1==-1 || p2==-1) { printf("input error: invalid edge!\n"); free(pG); return NULL; } pG->matrix[p1][p2] = 1; } return pG;}/* * 创建图(用已提供的矩阵) */Graph* create_example_graph(){ char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'B'}, {'B', 'C'}, {'B', 'E'}, {'B', 'F'}, {'C', 'E'}, {'D', 'C'}, {'E', 'B'}, {'E', 'D'}, {'F', 'G'}}; int vlen = LENGTH(vexs); int elen = LENGTH(edges); int i, p1, p2; Graph* pG; // 输入"顶点数"和"边数" if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL ) return NULL; memset(pG, 0, sizeof(Graph)); // 初始化"顶点数"和"边数" pG->vexnum = vlen; pG->edgnum = elen; // 初始化"顶点" for (i = 0; i vexnum; i++) { pG->vexs[i] = vexs[i]; } // 初始化"边" for (i = 0; i edgnum; i++) { // 读取边的起始顶点和结束顶点 p1 = get_position(*pG, edges[i][0]); p2 = get_position(*pG, edges[i][1]); pG->matrix[p1][p2] = 1; } return pG;}/* * 返回顶点v的第一个邻接顶点的索引，失败则返回-1 */static int first_vertex(Graph G, int v){ int i; if (v(G.vexnum-1)) return -1; for (i = 0; i = 0; w = next_vertix(G, i, w)) { if (!visited[w]) DFS(G, w, visited); } }/* * 深度优先搜索遍历图 */void DFSTraverse(Graph G){ int i; int visited[MAX]; // 顶点访问标记 // 初始化所有顶点都没有被访问 for (i = 0; i = 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点 { if (!visited[k]) { visited[k] = 1; printf("%c ", G.vexs[k]); queue[rear++] = k; } } } } printf("\n");}/* * 打印矩阵队列图 */void print_graph(Graph G){ int i,j; printf("Martix Graph:\n"); for (i = 0; i 邻接表表示的"有向图"
/** * C: 邻接表表示的"有向图(List Directed Graph)" * * @author skywang * @date 2014/04/18 */#include #include #include #include #define MAX 100#define isLetter(a) ((((a)>='a')&&((a)='A')&&((a)next_edge; p->next_edge = node;}/* * 创建邻接表对应的图(自己输入) */LGraph* create_lgraph(){ char c1, c2; int v, e; int i, p1, p2; ENode *node1, *node2; LGraph* pG; // 输入"顶点数"和"边数" printf("input vertex number: "); scanf("%d", &v); printf("input edge number: "); scanf("%d", &e); if ( v (v * (v-1)))) { printf("input error: invalid parameters!\n"); return NULL; } if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL ) return NULL; memset(pG, 0, sizeof(LGraph)); // 初始化"顶点数"和"边数" pG->vexnum = v; pG->edgnum = e; // 初始化"邻接表"的顶点 for(i=0; ivexnum; i++) { printf("vertex(%d): ", i); pG->vexs[i].data = read_char(); pG->vexs[i].first_edge = NULL; } // 初始化"邻接表"的边 for(i=0; iedgnum; i++) { // 读取边的起始顶点和结束顶点 printf("edge(%d): ", i); c1 = read_char(); c2 = read_char(); p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); // 初始化node1 node1 = (ENode*)malloc(sizeof(ENode)); node1->ivex = p2; // 将node1链接到"p1所在链表的末尾" if(pG->vexs[p1].first_edge == NULL) pG->vexs[p1].first_edge = node1; else link_last(pG->vexs[p1].first_edge, node1); } return pG;}/* * 创建邻接表对应的图(用已提供的数据) */LGraph* create_example_lgraph(){ char c1, c2; char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'B'}, {'B', 'C'}, {'B', 'E'}, {'B', 'F'}, {'C', 'E'}, {'D', 'C'}, {'E', 'B'}, {'E', 'D'}, {'F', 'G'}}; int vlen = LENGTH(vexs); int elen = LENGTH(edges); int i, p1, p2; ENode *node1, *node2; LGraph* pG; if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL ) return NULL; memset(pG, 0, sizeof(LGraph)); // 初始化"顶点数"和"边数" pG->vexnum = vlen; pG->edgnum = elen; // 初始化"邻接表"的顶点 for(i=0; ivexnum; i++) { pG->vexs[i].data = vexs[i]; pG->vexs[i].first_edge = NULL; } // 初始化"邻接表"的边 for(i=0; iedgnum; i++) { // 读取边的起始顶点和结束顶点 c1 = edges[i][0]; c2 = edges[i][1]; p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); // 初始化node1 node1 = (ENode*)malloc(sizeof(ENode)); node1->ivex = p2; // 将node1链接到"p1所在链表的末尾" if(pG->vexs[p1].first_edge == NULL) pG->vexs[p1].first_edge = node1; else link_last(pG->vexs[p1].first_edge, node1); } return pG;}/* * 深度优先搜索遍历图的递归实现 */static void DFS(LGraph G, int i, int *visited){ int w; ENode *node; visited[i] = 1; printf("%c ", G.vexs[i].data); node = G.vexs[i].first_edge; while (node != NULL) { if (!visited[node->ivex]) DFS(G, node->ivex, visited); node = node->next_edge; }}/* * 深度优先搜索遍历图 */void DFSTraverse(LGraph G){ int i; int visited[MAX]; // 顶点访问标记 // 初始化所有顶点都没有被访问 for (i = 0; i ivex; if (!visited[k]) { visited[k] = 1; printf("%c ", G.vexs[k].data); queue[rear++] = k; } node = node->next_edge; } } } printf("\n");}/* * 打印邻接表图 */void print_lgraph(LGraph G){ int i,j; ENode *node; printf("List Graph:\n"); for (i = 0; i ivex, G.vexs[node->ivex].data); node = node->next_edge; } printf("\n"); }}void main(){ LGraph* pG; // 自定义"图"(自己输入数据) //pG = create_lgraph(); // 采用已有的"图" pG = create_example_lgraph(); // 打印图 print_lgraph(*pG); DFSTraverse(*pG); BFS(*pG);}
上一篇：光遇服务器怎么修复?
下一篇：软件怎么修改服务器信息?
