打印图循环中的所有顶点

Question

我按照这个Algorithm to find and print simple cycle in complexity of O(n) on undirected graph试过了。根据我的导师的说法，它是在 C++ 中完成的，下面是我的代码：

int parent[1000] = {0};
int status[1000] = {0};
bool oriented = true;

#include ...

using namespace std;
array<list<int>, 1000 + 1> g;


void PrintCycle(int v, int u) {
    do {
        printf("%d",u);
        u = parent[u];
    } while (u != v);
}

bool DFS_cycle(int u) {
    status[u] = 1;
    for (int v:g[u]) {
        if (status[v] == 0) {
            parent[v] = u;
            DFS_cycle(v);
        }
        if (status[v] == 1 && v != parent[u]) {
            PrintCycle(v,u);
        }
    }
    status[u] = 2;
}


int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int N, u, v;
    cin >> N;
    while (cin >> u >> v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    parent[1] = 1;
    DFS_cycle(1);
    return 0;
}

但它不适用于以下输入：（第一行是顶点数。顶点从1开始编号。之后每行描述一条边。）

8

3 1

3 4

3 2

2 5

2 6

6 7

6 8

我做错了什么？

Answer 1

首先你用的是C++而不是C.

对于给定的输入，没有循环。它也不打印任何循环。所以它确实对给定的输入起作用。

但是您的代码有错误。如果我们添加另一条边 (5,8)，则形成一个循环 (2 -> 5 -> 8 -> 6)。但是您的代码将循环打印为 (6 -> 8 -> 5)。

检查我的代码以解决您的错误：

void PrintCycle(int v, int u) {
    while(u != v)
    {
        printf("%d ",u); // You didn't give any space after %d
        // It could not be possible to differentitate between '1''2'
        // and '12'

        u = parent[u];
    }

    printf("%d \n", v);

}

bool DFS_cycle(int u) {

    status[u] = 1;
    for (int v:g[u]) {
        if (status[v] == 0) {
            parent[v] = u;
            DFS_cycle(v);
        }
        else if (status[v] == 1 && v != parent[u]) { // It should be 'else if' NOT 'if'
            PrintCycle(v,u);
            break;
        }
    }
    status[u] = 2;
}

最好是 #define WHITE 0、#define GRAY 1 等然后使用 WHITE、GRAY 等而不是使用 1、2等

打印图循环中的所有顶点

Print all verticies in graph's cycle

algorithm

graph

cycle