深度优先搜索(DFS)详解

深度优先搜索（DFS）可以用于寻找有向图中的环路。在DFS过程中，如果遇到了已经访问过的节点，且该节点不是当前节点的父节点，那么就说明存在环路。 具体的实现可以使用递归函数来进行DFS遍历，并使用一个visited数组来记录每个节点是否已经访问过。在遍历到某个节点时，先将其标记为已访问，然后遍历其所有的邻居节点。如果邻居节点已经被访问过并且不是当前节点的父节点，则说明存在环路，直接返回true。如果邻居节点没有被访问过，则递归遍历该节点，如果返回true，则说明存在环路，直接返回true。遍历完所有邻居节点后，将当前节点标记为已完成，并返回false。 具体的代码实现如下： bool hasCycle(vector<vector<int>>& graph, int start, vector<bool>& visited, vector<bool>& completed) { visited[start] = true; for (int i = 0; i < graph[start].size(); i++) { int neighbor = graph[start][i]; if (visited[neighbor] && !completed[neighbor]) { return true; // found cycle } if (!visited[neighbor] && hasCycle(graph, neighbor, visited, completed)) { return true; // found cycle } } completed[start] = true; return false; // no cycle found } bool hasCycle(vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); vector<bool> completed(n, false); for (int i = 0; i < n; i++) { if (!visited[i]) { if (hasCycle(graph, i, visited, completed)) { return true; } } } return false; }