首页 文章

确定邻接矩阵是否具有循环，然后输出该循环

提问于
浏览 次
2

所以我有2个功能：

UPDATED

unordered_map<int, bool> visited2;
vector<vector<int>> elements2D;


bool DFSDetectCycle(int vertex){
    s.push(vertex);
    while(!s.empty()){
        int np_vertex = s.top();
        s.pop();
        if (visited2[np_vertex] == true){
            return true;
        }
        visited2[np_vertex] = true;
        for (int i = 0; i<elements2D.size(); i++){
            if(elements2D[np_vertex][i] != 0){
                if(DFSDetectCycle(i)){
                    return true;
                }
            }
        }
    }
    return false;   
}

bool hasCycle(vector<vector<int>> v){
    if (v.empty()){
        return false;   
    }
    for (int i = 0; i<v.size(); i++){
           if (!visited2[i]){
                      if(DFSDetectCycle(i)){
                          return true;
                      } 
           }
    }
    return false;
}

在我的主要功能中，我称之为：

if (hasCycle(elements2D)){
        for (int i = 0; i<elements2D.size(); i++){
            if (!visited2[i]){
                DFSDetectCycle(i);
            }       
        }
}else{
        cout << "No cycles." << endl;
}

所以基本上，输入将如下所示：

g++ -o GraphProcessor.o GraphProcessor.cpp -std=c++11
./GraphProcessor.o graph1.txt

输出应该如下所示：

Connected components:
{0,1,2,4,7}
{3}
{5,6}
A cycle: 0 1 4 2

但我的输出看起来像这样：

Connected components:
{0,1,4,2,7}
{3}
{5,6}
No cycles.

graph1.txt看起来像这样：

0 2 6 0 0 0 0 3
2 0 0 0 4 0 0 1
6 0 0 0 3 0 0 2
0 0 0 0 0 0 0 0
0 4 3 0 0 0 0 0
0 0 0 0 0 0 7 0
0 0 0 0 0 7 0 0
3 1 2 0 0 0 0 0

不要担心连接组件部分，这不是我现在的问题 . 我的问题是我的代码没有正确检测图中的周期，也没有正确输出它们 . 似乎我的hasCycle（）函数不断给出一个错误的声明，但我不确定为什么 . elements2D是我正在使用的矩阵，因为它是从文件中读取的，我需要在某处存储它 . 对于我的visited2函数，我使用unordered_map来保持布尔值是否我访问过顶点 . 我知道如果我再次访问了一个顶点，那么我就有一个循环 . 但我不知道如何修改我的算法以获得这样的结果 .

再次感谢任何帮助 .

c++ graph cycle adjacency-matrix

2 回答

  • 0

    • 您在不使用它的返回值的情况下递归调用 DFSDetectCycle . 我建议你检查递归调用是否返回true，并返回它是如此 .

    • 您正在专门跳过循环，因为您使用 if(elements2D[np_vertex][i] != 0 && !visited2[i]) 过滤递归调用 - 这意味着您不会进入已访问顶点，跳过循环 .

    此外，代码中没有可以产生所需输出的打印件......

    回复于
  • 0

    您应该从 if(elements2D[np_vertex][i] != 0 && !visited2[i]) 删除 visited[i] ，因为如果您已经访问过 i ，则删除此检查可以检测到它 . 如果它找到循环，你应该立即返回它 .

    if(elements2D[np_vertex][i] != 0){
    if (DFSDetectCycle(i)) return true;
}

    另一个问题是如果存在边缘 0->1 和 1->0 ，那么它们会形成一个循环 . 您需要更多工作才能找到最大的周期 .

    回复于

相关问题