1.树的层序遍历与图的BFS完全二叉树数组| 1 | 2 | 3 |邻接表| A | || B | || C | || ^ || B | || ^ || C | || ^ |树的层序遍历从根节点开始邻接表需要指定开始节点。邻接表更适合BFS结合队列实现过程简易。2.图的存储结构与树的存储结构https://www.doubao.com/thread/xGNd3nvT0nWLwNSclhttps://www.doubao.com/thread/xSdwqfDBJz1dxd9KO3.邻接矩阵和邻接表树一般使用二叉链表存储图可以选用邻接矩阵或者邻接表存储。邻接矩阵双for循环遍历二维数组邻接表头节点数组连接的链表。DFS、BFS与拓扑排序都应该用邻接矩阵和邻接表分别实现。由于遍历邻接矩阵的时间复杂度为On^2,它适用于稠密图边数多的图而遍历邻接表的时间复杂度为OVE他适用于稀疏图变数少的图。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 递归深度优先搜索核心思想从起始顶点出发递归地访问其未被访问的邻接点直到该分支全部访问完再回溯到上一个顶点继续探索。伪代码textDFS(G, v, visited): visited[v] true 访问 v for each u in G.adj[v]: if not visited[u]: DFS(G, u, visited)代码解释visited数组标记已访问顶点。递归函数对每个邻接点若未访问则调用自身。处理不连通图时外层循环对所有顶点调用。完整函数cvoid 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 非递归用栈模拟核心思想使用显式栈数组或链表代替系统调用栈按“后进先出”顺序访问顶点。注意入栈时标记访问避免重复入栈。伪代码textDFS_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指针。起始顶点先入栈并标记。每次弹出并访问将其所有未访问邻接点标记后入栈。完整函数cvoid 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 队列广度优先搜索核心思想从起始顶点出发将其所有邻接点依次入队然后逐层向外扩展先访问距离起点近的顶点。伪代码textBFS(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指针。入队时立即标记访问防止重复入队。完整函数cvoid 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 的顶点及其出边并用队列保存删除顺序。若最终删除的顶点数小于总顶点数则图中有环。伪代码textTopologicalSort(G): 计算所有顶点入度 indegree[] queue 所有 indegree0 的顶点 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此处假设图是有向的添加边时只加一次。完整函数cint 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 两种颜色若发现邻接点颜色相同则非二分图。伪代码textisBipartite(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。递归检查邻接点必须颜色相反否则失败。完整函数cint 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; }运行结果示例textDFS 递归 (从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算法小结算法适用场景空间时间DFS递归连通性、路径查找O(V)O(VE)DFS非递归同上避免栈溢出O(V)O(VE)BFS最短路径无权、层次遍历O(V)O(VE)拓扑排序任务调度、依赖关系DAGO(V)O(VE)二分图染色判定二分图、匹配问题O(V)O(VE)
【数据结构】图论代码强化
1.树的层序遍历与图的BFS完全二叉树数组| 1 | 2 | 3 |邻接表| A | || B | || C | || ^ || B | || ^ || C | || ^ |树的层序遍历从根节点开始邻接表需要指定开始节点。邻接表更适合BFS结合队列实现过程简易。2.图的存储结构与树的存储结构https://www.doubao.com/thread/xGNd3nvT0nWLwNSclhttps://www.doubao.com/thread/xSdwqfDBJz1dxd9KO3.邻接矩阵和邻接表树一般使用二叉链表存储图可以选用邻接矩阵或者邻接表存储。邻接矩阵双for循环遍历二维数组邻接表头节点数组连接的链表。DFS、BFS与拓扑排序都应该用邻接矩阵和邻接表分别实现。由于遍历邻接矩阵的时间复杂度为On^2,它适用于稠密图边数多的图而遍历邻接表的时间复杂度为OVE他适用于稀疏图变数少的图。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 递归深度优先搜索核心思想从起始顶点出发递归地访问其未被访问的邻接点直到该分支全部访问完再回溯到上一个顶点继续探索。伪代码textDFS(G, v, visited): visited[v] true 访问 v for each u in G.adj[v]: if not visited[u]: DFS(G, u, visited)代码解释visited数组标记已访问顶点。递归函数对每个邻接点若未访问则调用自身。处理不连通图时外层循环对所有顶点调用。完整函数cvoid 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 非递归用栈模拟核心思想使用显式栈数组或链表代替系统调用栈按“后进先出”顺序访问顶点。注意入栈时标记访问避免重复入栈。伪代码textDFS_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指针。起始顶点先入栈并标记。每次弹出并访问将其所有未访问邻接点标记后入栈。完整函数cvoid 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 队列广度优先搜索核心思想从起始顶点出发将其所有邻接点依次入队然后逐层向外扩展先访问距离起点近的顶点。伪代码textBFS(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指针。入队时立即标记访问防止重复入队。完整函数cvoid 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 的顶点及其出边并用队列保存删除顺序。若最终删除的顶点数小于总顶点数则图中有环。伪代码textTopologicalSort(G): 计算所有顶点入度 indegree[] queue 所有 indegree0 的顶点 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此处假设图是有向的添加边时只加一次。完整函数cint 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 两种颜色若发现邻接点颜色相同则非二分图。伪代码textisBipartite(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。递归检查邻接点必须颜色相反否则失败。完整函数cint 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; }运行结果示例textDFS 递归 (从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算法小结算法适用场景空间时间DFS递归连通性、路径查找O(V)O(VE)DFS非递归同上避免栈溢出O(V)O(VE)BFS最短路径无权、层次遍历O(V)O(VE)拓扑排序任务调度、依赖关系DAGO(V)O(VE)二分图染色判定二分图、匹配问题O(V)O(VE)