【数据结构】工程化实现BFS

这里是邻接表邻接图实现的完整BFS代码用动态链表存储边效率更高适合稀疏图。c#include stdio.h #include stdlib.h #include stdbool.h #define MAX_VERTICES 100 // 邻接表节点边 typedef struct EdgeNode { int vertex; // 邻接顶点编号 struct EdgeNode* next; } EdgeNode; // 顶点结构头节点 typedef struct { EdgeNode* head; // 指向第一条边 } Vertex; Vertex graph[MAX_VERTICES]; // 图数组 bool visited[MAX_VERTICES]; // 访问标记 // ---------- 队列数组模拟---------- int queue[MAX_VERTICES]; int front 0, rear 0; void enqueue(int v) { queue[rear] v; } int dequeue() { return queue[front]; } bool isEmpty() { return front rear; } // ---------- 添加边无向图---------- void addEdge(int u, int v) { // 添加 u - v EdgeNode* newNode (EdgeNode*)malloc(sizeof(EdgeNode)); newNode-vertex v; newNode-next graph[u].head; graph[u].head newNode; // 添加 v - u无向 newNode (EdgeNode*)malloc(sizeof(EdgeNode)); newNode-vertex u; newNode-next graph[v].head; graph[v].head newNode; } // ---------- BFS 遍历 ---------- void bfs(int start) { enqueue(start); visited[start] true; while (!isEmpty()) { int cur dequeue(); printf(%d , cur); // 遍历 cur 的所有邻接点 EdgeNode* p graph[cur].head; while (p ! NULL) { int neighbor p-vertex; if (!visited[neighbor]) { enqueue(neighbor); visited[neighbor] true; } p p-next; } } } // ---------- 主函数 ---------- int main() { int n, edges, u, v, start; printf(请输入顶点数: ); scanf(%d, n); printf(请输入边数: ); scanf(%d, edges); // 初始化图头节点置空访问标记false for (int i 0; i n; i) { graph[i].head NULL; visited[i] false; } printf(请输入 %d 条边 (u v):\n, edges); for (int i 0; i edges; i) { scanf(%d %d, u, v); addEdge(u, v); } printf(请输入起始顶点: ); scanf(%d, start); printf(BFS遍历结果: ); bfs(start); // 处理不连通分量 for (int i 0; i n; i) { if (!visited[i]) { printf(\n检测到不连通分量从 %d 继续: , i); // 重置队列因为 front/rear 已到末尾需重置 front rear 0; bfs(i); } } printf(\n); // 释放链表内存可选为简洁略 return 0; }运行示例text请输入顶点数: 5 请输入边数: 4 请输入 4 条边 (u v): 0 1 0 2 1 3 1 4 请输入起始顶点: 0 BFS遍历结果: 0 1 2 3 4关键点邻接表每个顶点维护一个链表存储所有相邻顶点。添加边无向图需双向插入若为有向图只插入 u→v。队列数组模拟注意遍历不连通分量时需重置front和rear。复杂度时间 O(VE)空间 O(VE)。如果需要带权图或记录层数可以在边节点中增加weight字段或使用distance数组。