在图中查找循环

Question

我想编写一个代码，用于在给定的有向矩阵形式的有向图中查找固定长度的循环

bool check(int vertex,int current_vertex, int k, int** graph , int n) {
if (k == 0)
    return (vertex == current_vertex);
for (int i = 0; i < n; i++) {
    if (graph[current_vertex][i] == 1) {
        graph[current_vertex][i] = 0;
        if (check(vertex, i, k - 1, graph, n)) return true;
        graph[vertex][i] = 1;
    }
}
return false;
}

从 main 调用函数：

    for (int i = 0; i < n; i++) {
        cycle = check(i,i,k,graph,n);
        if (cycle) break;
    }
    cout << (cycle?"TRUE":"FALSE");

我的输入在下面给出，只有一个循环，正如预期的那样，它对“5”给出 true，对“1”、“2”、“4”给出 false，但对“3”也给出 true。我错过了什么？

Answer 1

我运行你的代码。

您在访问图表时正在更改图表。这会给您带来不可预测的结果。

当您将边缘设置为已访问时，您必须将该边缘设置回其原始值。

1) 在你之前 return 是的。万一它找到循环

2) 在完成循环后转到下一个顶点之前（您使用的是 vertex 而不是 current_vertex。

这是您的函数的有效实现。

bool check(int vertex,int current_vertex, int k, int** graph , int n) {
    if (k == 0)
        return (vertex == current_vertex);
    for (int i = 0; i < n; i++) {
        if (graph[current_vertex][i] == 1) {
            graph[current_vertex][i] = 0;
            if (check(vertex, i, k - 1, graph, n)){
                graph[current_vertex][i] = 1;
                return true;
            }
            graph[current_vertex][i] = 1;
        }
    }
    return false;
}

希望对您有所帮助。

在图中查找循环

Finding a cycle in a graph

c++

graph

cycle