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

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 中的索引。变量索引总是相同的。所以我在 class 图中添加了一个新的属性索引，现在它可以工作了。所以这是编辑后的代码：

#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;
}

Answer 2

这是我在 Python

中的 DFS 解决方案

#program to print all nodes included in the cycle in the given undirected graph 

import collections

edges = [[1, 2], [2, 3], [1, 3], [2, 4], [4, 5], [5, 6], [4, 6]]
n = 6

parent = [0] * (n + 1)
color = [0] * (n + 1)
mark = [0] * (n + 1)
cycleno = 0

graph = collections.defaultdict(set)

for i, j in edges:
    graph[i].add(j)
    graph[j].add(i)

def dfs(u, v):
    global cycleno 

    if color[u] == 2: #node explore complete
        return 
    elif color[u] == 1: #cycle found
        cycleno += 1
        cur = v 
        mark[cur] = cycleno 
        while cur != u:
            cur = parent[cur]
            mark[cur] = cycleno 
    else:
        parent[u] = v 
        color[u] = 1
        for nei in graph[u]:
            if nei == parent[u]:    continue 
            dfs(nei, u)
        color[u] = 2 #exploration for this node completed
    

dfs(1, 0)
print(mark)

输出： [0, 1, 1, 1, 2, 2, 2]表示节点1、2、3和4、5、6分别属于循环

参考：https://www.tutorialspoint.com/print-all-the-cycles-in-an-undirected-graph-in-cplusplus

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

Detecting and printing cycle in undirected graph

c++

graph

cycle

depth-first-search