首页图的深度优先遍历和广度优先遍历C语言

图的深度优先遍历和广度优先遍历C语言

时间: 2025-05-05 14:08:00 浏览: 31

### C语言实现图的深度优先遍历对于图结构而言，深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。该算法会尽可能深入地探索每一个分支直到无法继续为止，再回溯到上一个节点并重复此过程。 ```c #include <stdio.h> #define MAX_V 100 typedef struct { int adj[MAX_V][MAX_V]; int Vnum; } Graph; void DFS(Graph* G, int v) { static int visited[MAX_V] = {0}; printf("%d ", v); visited[v] = 1; for (int w = 0; w < G->Vnum; ++w) { if (!visited[w] && G->adj[v][w]) { DFS(G, w); } } } ``` 这段代码展示了如何通过递归方式来执行深度优先遍历[^1]。需要注意的是`static`关键字使得访问标记数组在整个函数调用期间保持不变。 ### C语言实现图的广度优先遍历相比之下，广度优先搜索（BFS）则按照层次依次向外扩展，即先处理离起始点最近的一层节点之后才去考虑更远一层的节点。 ```c #include <stdio.h> #define MAX_V 100 typedef struct { int adj[MAX_V][MAX_V]; int Vnum; } Graph; // 使用简单的数组模拟队列操作 void BFS(Graph* T) { int queue[MAX_V], front = -1, rear = -1; char visited[MAX_V] = {0}; // 初始化起点 queue[++rear] = 0; visited[0] = 1; while(front != rear){ int currentVertex = queue[++front]; printf("%d ", currentVertex); for(int neighbor = 0; neighbor < T->Vnum; ++neighbor){ if(!visited[neighbor] && T->adj[currentVertex][neighbor]){ queue[++rear] = neighbor; visited[neighbor] = 1; } } } } ``` 上述程序片段给出了基于数组而非标准库中定义的数据结构来进行广度优先遍历的方法[^3]。这种方式虽然简单易懂但对于大型项目来说可能不是最优的选择；实际应用时建议采用更加成熟的容器类如链表或者STL中的queue。

阅读全文