c++ - 如何找到有向图中选定节点内是否存在循环？(C++)

Question

我目前正在研究一个发现循环的问题，该循环包括有向图中的选定节点。
对于此处描述的实例:

在节点1、2、3内有一个循环，并且在1、2、4内未找到任何循环。
我尝试通过以下操作自己实现该算法:

从所选节点内的第一个节点开始。

将当前节点标记为“已访问”。

检查相邻节点是否在所选节点内。

如果尚未访问该节点，则进行递归调用，如果已访问该节点，则返回true。

函数结尾:返回false。

我的实现如下(为每个选定的节点调用该函数，并且每次都会初始化存储访问节点的数组)

bool hasLoop(const int startNode, const bool directions[][MAX_DOT_NUM], const int nodesLen, bool nodesVisited[], const int selectedNodes[], const int selectedNum){
nodesVisited[startNode] = true;

for(int i = 0; i < nodesLen; i++){ //loop through all nodes 
    if(withinSelected(i, selectedNodes, selectedNum) == false) continue;  //check loop only for selected nodes
    if(directions[startNode][i] == 1){ //connected and is within selected nodes
        if(nodesVisited[i] == true){ 
            return true;                
        }else{
            if(hasLoop(i, directions, nodesLen, nodesVisited, selectedNodes, selectedNum)){
                return true;
            }
        }
    }
}
return false;

}
但是，此实现不适用于我使用的在线法官的所有测试数据。
我发现我的算法与深度优先搜索不同，深度优先搜索使用白色，灰色，黑色数组来存储未访问，正在访问或不需要访问的节点，我不知道这是引起问题的原因。
希望我能在您的帮助下找到导致该实现无法在所有情况下运行的错误!
非常感谢您阅读本文!
编辑:这是有向图!对此表示抱歉。

编辑:非常感谢您的帮助!我修改了实现，以使函数仅在找到指向函数开始的节点的节点时才返回true。
这是我使用的在线法官接受的最终实现:

bool hasLoop(const int currentNode, const bool directions[][MAX_DOT_NUM], const int nodesLen, bool nodesVisited[], const int selectedNodes[], const int selectedNum, const int startNode){
// cout << currentNode << " -> ";
nodesVisited[currentNode] = true;

for(int i = 0; i < nodesLen; i++){
    if(withinSelected(i, selectedNodes, selectedNum) == false) continue;
    if(directions[currentNode][i] == 1){ //connected and is within selected nodes
        if(nodesVisited[i] == true){ 
            if(i == startNode) return true;        
        }else{
            if(hasLoop(i, directions, nodesLen, nodesVisited, selectedNodes, selectedNum, startNode)){
                return true;
            }
        }
    }
}
return false;

}

Answer 1

您的实现是DFS，但是对于不创建循环的“侧节点”将失败:
考虑具有3个节点(A,B,C)的图:

      A
    /   \
   /     \
  V       V
  B <---- C

您的算法会告诉您图形有一个循环，而实际上-它没有!
您可以通过找到 Strongly Connected Components并查看是否存在非平凡(size> 1)组件来解决它。
另一种解决方案是使用 Topological Sort-当且仅当图形具有循环时，它才返回错误。
在这两种解决方案中，仅将算法应用于包含“选定节点”的子图。两种解决方案都是 O(|V|+|E|)时间和 O(|V|)空间。