DFS \BFS生成树

根据给定文件中的标题“DFS \BFS生成树”、描述以及部分代码内容，我们可以提炼出以下几个关键知识点：邻接表、深度优先搜索（Depth-First Search, DFS）、广度优先搜索（Breadth-First Search, BFS）以及如何利用这两种搜索算法生成树或森林。 ### 1. 邻接表 邻接表是一种用于存储图数据结构的数据结构。它通过一系列链表来表示图中各个顶点的相邻关系。对于无向图，如果顶点\( v_i \)与顶点\( v_j \)相连，则在\( v_i \)的链表中会有一个指向\( v_j \)的指针，在\( v_j \)的链表中也会有一个指向\( v_i \)的指针；对于有向图，则只会在起点的链表中添加一个指向终点的指针。 ### 2. 深度优先搜索（DFS） #### 2.1 DFS算法原理 DFS是一种遍历或搜索树或图的算法。其基本思想是从图中某个顶点\( v \)出发，首先访问\( v \)，然后选择一个与\( v \)相邻且未被访问过的顶点\( w \)继续进行深度优先搜索，直到当前路径无法深入时，才回溯到上一个节点继续探索。DFS可以用来解决很多问题，比如寻找连通分量、判断环路的存在等。 #### 2.2 DFS生成树 DFS可以用来生成一棵树或森林。当从某个顶点开始执行DFS时，每遇到一个未被访问过的顶点，就将该顶点加入到树中。最终形成的树被称为DFS生成树。如果图是连通的，则生成一棵树；如果图不是连通的，则生成森林。 #### 2.3 DFS代码实现 ```c typedef enum {FALSE, TRUE} Boolean; Boolean visited[MaxVertexNum]; void DFSTraverseTREE(ALGraph* G) { for (int i = 0; i < G->n; i++) visited[i] = FALSE; for (int i = 0; i < G->n; i++) if (!visited[i]) DFSTree(G, i); } void DFSTree(ALGraph* G, int i) { visited[i] = TRUE; EdgeNode* p = G->adjlist[i].firstedge; while (p) { if (!visited[p->adjvex]) { printf("(%c, %c)\n", G->adjlist[i].vertex, G->adjlist[p->adjvex].vertex); DFSTree(G, p->adjvex); } p = p->next; } } ``` ### 3. 广度优先搜索（BFS） #### 3.1 BFS算法原理 BFS同样是一种遍历或搜索树或图的算法。其基本思想是从图中某个顶点\( v \)出发，首先访问\( v \)，然后依次访问所有与\( v \)相邻的顶点，再依次访问它们的所有未被访问过的相邻顶点，以此类推。BFS通常使用队列来管理待访问的顶点。 #### 3.2 BFS生成树 BFS也可以用来生成一棵树或森林。与DFS类似，当从某个顶点开始执行BFS时，每遇到一个未被访问过的顶点，就将该顶点加入到树中。最终形成的树被称为BFS生成树。 #### 3.3 BFS代码实现 ```c void BFSTraverseTREE(ALGraph* G) { for (int i = 0; i < G->n; i++) visited[i] = FALSE; for (int i = 0; i < G->n; i++) if (!visited[i]) BFSTree(G, i); } void BFSTree(ALGraph* G, int k) { CirQueue Q; InitQueue(&Q); visited[k] = TRUE; EnQueue(&Q, k); while (!QueueEmpty(&Q)) { int i = DeQueue(&Q); EdgeNode* p = G->adjlist[i].firstedge; while (p) { if (!visited[p->adjvex]) { printf("(%c, %c)\n", G->adjlist[i].vertex, G->adjlist[p->adjvex].vertex); visited[p->adjvex] = TRUE; EnQueue(&Q, p->adjvex); } p = p->next; } } } ``` 以上就是关于DFS和BFS生成树的相关知识点。这两种算法都是非常基础且重要的图论算法，对于理解图的各种特性非常有帮助。