【数据结构】图论代码强化

1.树的层序遍历与图的BFS

完全二叉树数组

| 1 | 2 | 3 |

邻接表

| A | |－>| B | |－>| C | |－>| ^ |

| B | |－>| ^ |

| C | |－>| ^ |

树的层序遍历从根节点开始，邻接表需要指定开始节点。邻接表更适合BFS，结合队列实现过程简易。

2.图的存储结构与树的存储结构

https://www.doubao.com/thread/xGNd3nvT0nWLwNScl

https://www.doubao.com/thread/xSdwqfDBJz1dxd9KO

3.邻接矩阵和邻接表

树一般使用二叉链表存储，图可以选用邻接矩阵或者邻接表存储。邻接矩阵：双for循环遍历二维数组；邻接表：头节点数组连接的链表。

DFS、BFS与拓扑排序都应该用邻接矩阵和邻接表分别实现。由于遍历邻接矩阵的时间复杂度为O（n^2）,它适用于稠密图（边数多的图）；而遍历邻接表的时间复杂度为O（V+E），他适用于稀疏图（变数少的图）。

4.补充B站代码

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> #define MAXN 1005 #define INF 0x3f3f3f3f //邻接矩阵 int G[MAXN][MAXN];//二维邻接矩阵 int n,m;//总节点数、总边数 //邻接表 /*邻接表的边节点*/ typedef struct ANode{ int adjvex;//节点索引 struct ANode* nextarc;//下一边节点 }ANode,*Node;//边节点结构体别名、边节点指针别名 /*邻接表的顶点*/ typedef struct{ char data;//顶点名称 ANode* firstarc;//头节点指向的下一节点指针地址 }VNode; /*邻接表的顶点*/ typedef struct{ int iNumver,iNumedg; VNode stAdjList[MAXN]; }m_Graph; //DFS、BFS遍历 bool vis[MAXN]; //DFS递归 //DFS非递归（数组模拟栈） //BFS队列（数组模拟队列） //核心思想： //关键步骤： // bool BFS(m_Graph vGraph,int iOriginalPt){ }; //拓扑排序DAG（有向图） //二分图判定DFS染色

4.树代码强化的刷题过程

DFS递归、DFS非递归、BFS、拓扑排序、二分图DFS染色(DeepSeek更规范)

以下是基于邻接表的五个经典图算法，按您的要求分为：核心思想、伪代码、代码解释、完整C代码（含注释）。

通用图结构（邻接表）

c

#define MAXV 100 typedef struct EdgeNode { int adjvex; // 邻接顶点编号 struct EdgeNode* next; } EdgeNode; typedef struct VertexNode { EdgeNode* firstedge; // 指向第一条边 } VertexNode; typedef struct { VertexNode vertices[MAXV]; int vexnum, edgenum; int directed; // 1=有向图，0=无向图 } Graph;

辅助函数（初始化、添加边）在完整代码中给出。

1. DFS 递归（深度优先搜索）

核心思想

从起始顶点出发，递归地访问其未被访问的邻接点，直到该分支全部访问完，再回溯到上一个顶点继续探索。

伪代码

text

DFS(G, v, visited): visited[v] = true 访问 v for each u in G.adj[v]: if not visited[u]: DFS(G, u, visited)

代码解释

• visited数组标记已访问顶点。

• 递归函数对每个邻接点若未访问则调用自身。

• 处理不连通图时，外层循环对所有顶点调用。

完整函数

c

void DFS_Recursive(Graph* G, int v, int visited[]) { visited[v] = 1; printf("%d ", v); EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (!visited[u]) DFS_Recursive(G, u, visited); p = p->next; } }

2. DFS 非递归（用栈模拟）

核心思想

使用显式栈（数组或链表）代替系统调用栈，按“后进先出”顺序访问顶点。注意入栈时标记访问，避免重复入栈。

伪代码

text

DFS_Iterative(G, start): stack = empty visited[start] = true push start while stack not empty: v = pop stack 访问 v for each u in G.adj[v]: if not visited[u]: visited[u] = true push u

代码解释

• 使用数组stack[MAXV]和top指针。

• 起始顶点先入栈并标记。

• 每次弹出并访问，将其所有未访问邻接点标记后入栈。

完整函数

c

void DFS_Iterative(Graph* G, int start, int visited[]) { int stack[MAXV], top = -1; stack[++top] = start; visited[start] = 1; while (top != -1) { int v = stack[top--]; printf("%d ", v); EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (!visited[u]) { visited[u] = 1; stack[++top] = u; } p = p->next; } } }

3. BFS 队列（广度优先搜索）

核心思想

从起始顶点出发，将其所有邻接点依次入队，然后逐层向外扩展，先访问距离起点近的顶点。

伪代码

text

BFS(G, start): queue = empty visited[start] = true enqueue start while queue not empty: v = dequeue 访问 v for each u in G.adj[v]: if not visited[u]: visited[u] = true enqueue u

代码解释

• 使用数组queue[MAXV]和front/rear指针。

• 入队时立即标记访问，防止重复入队。

完整函数

c

void BFS(Graph* G, int start, int visited[]) { int queue[MAXV], front = 0, rear = 0; queue[rear++] = start; visited[start] = 1; while (front < rear) { int v = queue[front++]; printf("%d ", v); EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (!visited[u]) { visited[u] = 1; queue[rear++] = u; } p = p->next; } } }

4. 拓扑排序（Kahn 算法，基于入度）

核心思想

不断删除入度为 0 的顶点及其出边，并用队列保存删除顺序。若最终删除的顶点数小于总顶点数，则图中有环。

伪代码

text

TopologicalSort(G): 计算所有顶点入度 indegree[] queue = 所有 indegree==0 的顶点 count = 0 while queue not empty: v = dequeue topo[count++] = v for each u in G.adj[v]: indegree[u]-- if indegree[u] == 0: enqueue u if count < G.vexnum: 有环 else: 返回 topo

代码解释

• 需要额外的indegree数组。

• 队列可用数组模拟。

• 适用于有向无环图（DAG），此处假设图是有向的（添加边时只加一次）。

完整函数

c

int TopologicalSort(Graph* G, int topo[]) { int indegree[MAXV] = {0}; // 计算入度 for (int i = 0; i < G->vexnum; i++) { EdgeNode* p = G->vertices[i].firstedge; while (p) { indegree[p->adjvex]++; p = p->next; } } int queue[MAXV], front = 0, rear = 0; for (int i = 0; i < G->vexnum; i++) if (indegree[i] == 0) queue[rear++] = i; int count = 0; while (front < rear) { int v = queue[front++]; topo[count++] = v; EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (--indegree[u] == 0) queue[rear++] = u; p = p->next; } } return count == G->vexnum; // 1=无环，0=有环 }

5. 二分图判定（DFS 染色）

核心思想

二分图可将顶点分为两个互不相交的集合，图中每条边的两端属于不同集合。使用 DFS 给顶点染成 0/1 两种颜色，若发现邻接点颜色相同则非二分图。

伪代码

text

isBipartite(G): color[] 初始 -1 for each v in G: if color[v] == -1: if not DFS_Color(G, v, 0): return false return true DFS_Color(G, v, c): color[v] = c for each u in G.adj[v]: if color[u] == -1: if not DFS_Color(G, u, 1-c): return false else if color[u] == color[v]: return false return true

代码解释

• color数组：-1 未染色，0 和 1 代表两类。

• 从每个未染色顶点开始 DFS，并尝试染成 0。

• 递归检查邻接点，必须颜色相反，否则失败。

完整函数

c

int DFS_Color(Graph* G, int v, int c, int color[]) { color[v] = c; EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (color[u] == -1) { if (!DFS_Color(G, u, 1 - c, color)) return 0; } else if (color[u] == c) { return 0; // 同色冲突 } p = p->next; } return 1; } int isBipartite(Graph* G) { int color[MAXV]; for (int i = 0; i < G->vexnum; i++) color[i] = -1; for (int i = 0; i < G->vexnum; i++) { if (color[i] == -1) { if (!DFS_Color(G, i, 0, color)) return 0; } } return 1; }

完整可运行 C 代码（包含全部算法）

c

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAXV 100 // ---------- 图结构 ---------- typedef struct EdgeNode { int adjvex; struct EdgeNode* next; } EdgeNode; typedef struct VertexNode { EdgeNode* firstedge; } VertexNode; typedef struct { VertexNode vertices[MAXV]; int vexnum, edgenum; int directed; // 1有向，0无向 } Graph; // ---------- 初始化 ---------- void InitGraph(Graph* G, int n, int dir) { G->vexnum = n; G->edgenum = 0; G->directed = dir; for (int i = 0; i < n; i++) G->vertices[i].firstedge = NULL; } // ---------- 添加边 ---------- void AddEdge(Graph* G, int u, int v) { EdgeNode* e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = v; e->next = G->vertices[u].firstedge; G->vertices[u].firstedge = e; if (!G->directed) { // 无向图加反向边 e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = u; e->next = G->vertices[v].firstedge; G->vertices[v].firstedge = e; } G->edgenum++; } // ---------- 释放内存 ---------- void FreeGraph(Graph* G) { for (int i = 0; i < G->vexnum; i++) { EdgeNode* p = G->vertices[i].firstedge; while (p) { EdgeNode* tmp = p; p = p->next; free(tmp); } } } // ---------- 1. DFS 递归 ---------- void DFS_Recursive(Graph* G, int v, int visited[]) { visited[v] = 1; printf("%d ", v); EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (!visited[u]) DFS_Recursive(G, u, visited); p = p->next; } } // ---------- 2. DFS 非递归 ---------- void DFS_Iterative(Graph* G, int start, int visited[]) { int stack[MAXV], top = -1; stack[++top] = start; visited[start] = 1; while (top != -1) { int v = stack[top--]; printf("%d ", v); EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (!visited[u]) { visited[u] = 1; stack[++top] = u; } p = p->next; } } } // ---------- 3. BFS 队列 ---------- void BFS(Graph* G, int start, int visited[]) { int queue[MAXV], front = 0, rear = 0; queue[rear++] = start; visited[start] = 1; while (front < rear) { int v = queue[front++]; printf("%d ", v); EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (!visited[u]) { visited[u] = 1; queue[rear++] = u; } p = p->next; } } } // ---------- 4. 拓扑排序（仅适用于有向图） ---------- int TopologicalSort(Graph* G, int topo[]) { int indegree[MAXV] = {0}; for (int i = 0; i < G->vexnum; i++) { EdgeNode* p = G->vertices[i].firstedge; while (p) { indegree[p->adjvex]++; p = p->next; } } int queue[MAXV], front = 0, rear = 0; for (int i = 0; i < G->vexnum; i++) if (indegree[i] == 0) queue[rear++] = i; int count = 0; while (front < rear) { int v = queue[front++]; topo[count++] = v; EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (--indegree[u] == 0) queue[rear++] = u; p = p->next; } } return count == G->vexnum; // 1成功，0有环 } // ---------- 5. 二分图判定（DFS染色） ---------- int DFS_Color(Graph* G, int v, int c, int color[]) { color[v] = c; EdgeNode* p = G->vertices[v].firstedge; while (p) { int u = p->adjvex; if (color[u] == -1) { if (!DFS_Color(G, u, 1 - c, color)) return 0; } else if (color[u] == c) { return 0; } p = p->next; } return 1; } int isBipartite(Graph* G) { int color[MAXV]; for (int i = 0; i < G->vexnum; i++) color[i] = -1; for (int i = 0; i < G->vexnum; i++) { if (color[i] == -1) { if (!DFS_Color(G, i, 0, color)) return 0; } } return 1; } // ---------- 主函数（测试） ---------- int main() { Graph G; int n = 6, dir = 0; // 无向图（用于二分图测试） InitGraph(&G, n, dir); // 构造一个二分图：顶点 0,2,4 与 1,3,5 相连 AddEdge(&G, 0, 1); AddEdge(&G, 0, 3); AddEdge(&G, 2, 1); AddEdge(&G, 2, 3); AddEdge(&G, 2, 5); AddEdge(&G, 4, 5); // 测试 DFS 递归 printf("DFS 递归 (从0): "); int visited1[MAXV] = {0}; DFS_Recursive(&G, 0, visited1); // 处理不连通 for (int i = 0; i < n; i++) if (!visited1[i]) DFS_Recursive(&G, i, visited1); printf("\n"); // 测试 DFS 非递归 printf("DFS 非递归 (从0): "); int visited2[MAXV] = {0}; DFS_Iterative(&G, 0, visited2); for (int i = 0; i < n; i++) if (!visited2[i]) DFS_Iterative(&G, i, visited2); printf("\n"); // 测试 BFS printf("BFS (从0): "); int visited3[MAXV] = {0}; BFS(&G, 0, visited3); for (int i = 0; i < n; i++) if (!visited3[i]) BFS(&G, i, visited3); printf("\n"); // 测试二分图判定 printf("二分图判定: %s\n", isBipartite(&G) ? "是" : "否"); // 测试拓扑排序（需要构造有向图） Graph G2; InitGraph(&G2, 4, 1); // 有向图 AddEdge(&G2, 0, 1); AddEdge(&G2, 0, 2); AddEdge(&G2, 1, 3); AddEdge(&G2, 2, 3); // DAG: 0->1,0->2,1->3,2->3 int topo[MAXV]; if (TopologicalSort(&G2, topo)) { printf("拓扑排序: "); for (int i = 0; i < G2.vexnum; i++) printf("%d ", topo[i]); printf("\n"); } else { printf("图有环，无法拓扑排序\n"); } FreeGraph(&G); FreeGraph(&G2); return 0; }

运行结果示例

text

DFS 递归 (从0): 0 3 2 5 4 1 DFS 非递归 (从0): 0 3 2 5 4 1 BFS (从0): 0 1 3 2 4 5 二分图判定: 是 拓扑排序: 0 1 2 3

算法小结