c++ - BFS 检测不应该出现的周期

Question

我已经实现了一个 BFS 算法来检测图中的循环，这是以下代码:

            void hasCycle(node *root,string start){  
            if(root->visted){
                if(root->name == start) cout << "Has cycle" << endl;
                else return;
            }
            root->visted = true;
            int ind;
            for(ind = 0; ind < root->adj.size(); ind++)
                hasCycle(root->adj[ind], start);
            root->visted = false;
            }

其中start是起始节点。其中节点是以下结构:

            struct node{
                string name;
                bool   visted;
                vector <node *> adj;
            };

这是我构建的图表:

            Graph *grp = new Graph();
            grp->addVertex("A");
            grp->addVertex("B");
            grp->addVertex("C");

            grp->addEdge("A","B");
            grp->addEdge("B","A");
            grp->addEdge("A","C");
            grp->addEdge("C","A");

输出是: 有周期 有周期 有循环

正确的输出是什么都没有，因为没有循环。我花了很多时间尝试调试这个，请帮忙!

注意:这不是有向图所以我希望它们是双边

Answer 1

我假设您想要在无向图中使用大小为 3 或更大的循环。在这种情况下，您应该在检查“已访问”时忽略 BFS 遍历中的父级。