c++ - 检测和打印无向图中的循环

Question

我有类似的问题 - 相同 - 与此 one .所以我想知道如何不仅检测循环而且打印出这个循环包含的顶点。我尝试了上面问题中提到的方法，但我一定做错了什么，为什么它对我不起作用。我的程序还检查一个特定的顶点是否形成循环。我的代码在这里:

#include<iostream>
#include <list>
using namespace std;


class Graph
{
    int V;    
    list<int> *adj;    
public:
    Graph(int V);   
    void addEdge(int v, int w);   
    bool Graph::isCyclicUtil(int v, bool visited[], int *cycleVertices, int parent, int index);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); 
    adj[w].push_back(v);
}


bool Graph::isCyclicUtil(int v, bool visited[], int *cycleVertices, int parent, int index)
{

    visited[v] = true;


    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
    {

        if (!visited[*i])
        {
            if (isCyclicUtil(*i, visited, cycleVertices, v, index)) {
                if (index <= 1 || cycleVertices[0] != cycleVertices[index - 1])
                    cycleVertices[index++] = *i;
                return true;
            }
        }

        else if (*i != parent) {
            cycleVertices[index++] = *i;
            return true;
        }
    }
    return false;
}


int main()
{
    bool *visited = new bool[5];
    for (int i = 0; i < 5; i++)
        visited[i] = false;
    int cycleVertices[5];
    for (int i = 0; i < 5; i++)
        cycleVertices[i] = -1;
    Graph g1(5);
    g1.addEdge(1, 0);
    g1.addEdge(0, 2);
    g1.addEdge(2, 1);
    g1.addEdge(0, 3);
    g1.addEdge(3, 4);
    g1.isCyclicUtil(4, visited, cycleVertices, -1, 0) ? cout << "Graph contains cycle\n" :
        cout << "Graph doesn't contain cycle\n";
    int x = 0;
    while (cycleVertices[x] != -1)
        cout << cycleVertices[x++] << " ";
    return 0;
}

Answer 1

我找到了解决方案。我在这个 post 中尝试了 j_random_hacker 的解决方案它没有用。但问题在于我的代码中的 cycleVertices 中的索引。变量索引总是相同的。所以我在类 Graph 中添加了一个新的属性索引，现在它可以工作了。所以这是编辑后的代码:

#include<iostream>
#include <list>

#define FINISHED -1
#define NOCYCLE -2
using namespace std;


class Graph
{
    int V;   
    int index;
    list<int> *adj;   
public:
    Graph(int V);   
    void addEdge(int v, int w);  
    void set_index();
    int Graph::isCyclicUtil(int v, bool visited[], int *cycleVertices, int parent);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
    this->index = 0;
}

void Graph::set_index()
{
    this->index = 0;
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); 
    adj[w].push_back(v); 
}

int Graph::isCyclicUtil(int v, bool visited[], int *cycleVertices, int parent)
{
    visited[v] = true;

    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
    {
        if (!visited[*i])
        {
            int result = isCyclicUtil(*i, visited, cycleVertices, v);
            if (result == FINISHED)
                return FINISHED;
            else if (result != NOCYCLE) {
                cycleVertices[index++] = v;
                if (result == v)
                    return FINISHED;
                else
                    return result;
            }
        }

        else if (*i != parent) {
            return *i;
        }
    }
    return NOCYCLE;
}


int main()
{
    bool *visited = new bool[4];
    for (int i = 0; i < 4; i++)
        visited[i] = false;
    int cycleVertices[4];
    for (int i = 0; i < 4; i++)
        cycleVertices[i] = -1;
    Graph g1(4);
    g1.addEdge(0, 1);
    g1.addEdge(1, 2);
    g1.addEdge(2, 3);
    g1.addEdge(3, 0);
    g1.isCyclicUtil(3, visited, cycleVertices, -1) ? cout << "Graph contains cycle\n" :
        cout << "Graph doesn't contain cycle\n";
    int x = 0;
    while (cycleVertices[x] != -1)
        cout << cycleVertices[x++] << " ";
    return 0;
}