深度优先搜索DFS寻找有向图环路
时间: 2023-10-13 13:07:29 浏览: 51
深度优先搜索(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;
}