C语言实现广度深度遍历源码解析

本文主要探讨了使用纯C语言实现图的广度优先遍历（BFS）和深度优先遍历（DFS）的源码。提供的代码示例包括图的结构定义、初始化、创建以及输出等基本操作。 在图的遍历中，广度优先遍历和深度优先遍历是两种常用的方法，主要用于访问图的所有节点。 1. 广度优先遍历（BFS） BFS 是一种逐层展开的遍历方法，首先访问根节点，然后依次访问其所有相邻节点，再对这些相邻节点的相邻节点进行访问，直到所有节点都被访问到。BFS 通常使用队列数据结构来辅助实现，因为它遵循“先入先出”的原则。 2. 深度优先遍历（DFS） DFS 是一种沿着某条路径一直深入到不能再深入时，再回溯到上一个节点并尝试其他路径的遍历方法。DFS 通常使用栈或递归实现，因为它具有“后入先出”的特性。 以下是一个简单的DFS实现示例： ```c void DFS(GRAPH* G, int start) { int visited[n]; for (int i = 0; i < G->num; i++) { visited[i] = 0; } visited[start] = 1; printf("访问 %c\n", G->vexs[start]); for (int i = 0; i < G->num; i++) { if (!visited[i] && G->arcs[start][i] != 0) { DFS(G, i); } } } ``` 而BFS的实现通常需要一个队列来存储待访问的节点： ```c void BFS(GRAPH* G, int start) { int visited[n]; for (int i = 0; i < G->num; i++) { visited[i] = 0; } queue<int> Q; Q.push(start); visited[start] = 1; while (!Q.empty()) { int u = Q.front(); Q.pop(); printf("访问 %c\n", G->vexs[u]); for (int v = 0; v < G->num; v++) { if (!visited[v] && G->arcs[u][v] != 0) { Q.push(v); visited[v] = 1; } } } } ``` 在实际应用中，这两种遍历方法各有优势。BFS 更适合寻找最短路径，而 DFS 适用于寻找是否存在路径或找到特定路径。 为了使用这些遍历算法，首先需要创建一个图对象。在提供的代码中，`GraphCreate()` 函数用于输入顶点信息和边权矩阵，创建一个图对象。`GraphOut()` 函数用于打印图的顶点数和顶点信息。 请注意，上述代码中的 `GRAPH` 结构体定义了一个邻接矩阵表示的图，其中 `vexs` 存储顶点信息，`arcs` 存储边的权值，`num` 存储实际顶点数。在创建图时，用户需要输入顶点数目、每个顶点的字符信息以及图的边权矩阵。 在实际编程中，根据具体需求，可能还需要添加其他功能，如删除节点、添加边、查找路径等。同时，为了提高效率和防止内存溢出，应当考虑优化数据结构，如使用邻接表代替邻接矩阵，特别是在处理大规模图时。