- 正确答案：判断有向图是否存在环，常用方法有三种：1）基于深度优先搜索（DFS）的三色标记法；2）基于拓扑排序的Kahn算法（统计入度并BFS删点）；3）使用Tarjan或Kosaraju算法求强连通分量（SCC），若存在大小>1的SCC或自环，则图有环。其中最常用、最直观且时间空间效率均衡的是三色DFS法和Kahn算法。 - 解答思路：以三色DFS法为例：为每个节点维护三种状态——白色（未访问）、灰色（当前DFS路径中，即正在递归栈中）、黑色（已访问完毕且确认无环）。DFS遍历时，若从灰色节点u出发又遇到另一个灰色节点v，说明存在回边u→v，构成环；若遍历完成所有邻居仍未触发该情况，则该节点安全（无环路径），标记为黑色。对所有未访问节点启动DFS，只要任一DFS过程中发现灰→灰边，即可立即返回“有环”。 Kahn算法思路则从图的结构特性出发：有向无环图（DAG）必然存在至少一个入度为0的节点；每次删除一个入度为0的节点及其出边，并更新其邻居入度；若最终能删完所有节点，则无环；否则剩余节点入度均>0，形成环（因为环内每个节点至少有一条入边来自环内）。 - 深度知识讲解： 1）三色标记法的本质是检测DFS递归栈中的“后向边”（back edge），这是有向图中环存在的充要条件（在DFS森林中，后向边连接某节点与其祖先）。注意：有向图中不区分树边/前向边/横跨边，只有后向边能确定环。三色法避免了简单二色（访问/未访问）导致的误判（如横跨边被误认为环）。 2）Kahn算法依赖DAG的数学性质：DAG存在拓扑序 ⇔ 可进行拓扑排序 ⇔ 入度队列能清空所有节点。其底层是BFS+入度数组，需O(V+E)时间与O(V+E)空间（邻接表+入度数组+队列）。 3）强连通分量角度：有向图有环 ⇔ 至少存在一个非平凡SCC（节点数≥2）或自环（单节点环）。Tarjan算法通过一次DFS维护dfn[]（时间戳）和low[]（能回溯到的最早祖先时间戳），当dfn[u] == low[u]时，栈中从u到栈顶的所有节点构成一个SCC；若该SCC大小>1或含自环（u→u），则存在环。此法可同时检测环并输出所有环结构，但实现复杂度高，通常用于需要环枚举的场景。 4）底层数据结构支撑：邻接表（vector>或list）是标准表示，支持O(1)出边遍历；入度数组（vector indegree(n,0)）配合队列为Kahn核心；DFS栈可显式用stack或隐式用递归调用栈；三色状态可用vector color(n,0)，0=白，1=灰，2=黑。 - 代码示例（三色DFS法，C++风格伪代码）： ``` bool hasCycleDFS(const vector>& graph) { int n = graph.size(); vector color(n, 0); // 0: white, 1: gray, 2: black function dfs = [&](int u) -> bool { if (color[u] == 1) return true; // back edge found if (color[u] == 2) return false; // already checked, no cycle color[u] = 1; // mark as visiting for (int v : graph[u]) { if (dfs(v)) return true; } color[u] = 2; // mark as visited return false; }; for (int i = 0; i < n; ++i) { if (color[i] == 0 && dfs(i)) return true; } return false; } ``` - 代码示例（Kahn算法，C++风格伪代码）： ``` bool hasCycleKahn(const vector>& graph) { int n = graph.size(); vector indegree(n, 0); for (int u = 0; u < n; ++u) { for (int v : graph[u]) { indegree[v]++; } } queue q; for (int i = 0; i < n; ++i) { if (indegree[i] == 0) q.push(i); } int visited = 0; while (!q.empty()) { int u = q.front(); q.pop(); visited++; for (int v : graph[u]) { indegree[v]--; if (indegree[v] == 0) q.push(v); } } return visited != n; // if not all nodes are visited, cycle exists } ``` - 扩展知识： - 实际工程中（如编译器依赖分析、任务调度系统），常需在检测环的同时给出环路径。此时可在DFS中维护parent数组或path栈，当发现灰→灰边u→v时，从v沿递归栈回溯到u即可提取环。 - 对于超大规模图（如千万级节点），可考虑并行化Kahn算法（使用原子操作更新入度）或采用分布式图处理框架（如Pregel）。 - 若图动态变化（边增删），需用动态拓扑排序算法（如Marchetti-Spaccamela等），但复杂度显著上升。 - 注意：无向图判环不能直接套用上述方法（需避免父节点重复访问），应使用并查集或DFS记录parent。

字节抖音后端实习一面 50min

全站热榜

创作者周榜