检查有向图是否有环 CS50 tideman

Question

检查循环程序从图中的第一个节点到图中每个锁定的节点->检查它之前是否访问过，然后它是一个循环，否则从检查的下一个节点递归重复。当我自己测试它时它可以工作但是当我在 tide 人选中使用它时它没有。

问题说明：https://cs50.harvard.edu/x/2020/psets/3/tideman/

此问题的目标是使用 tideman 投票算法从选举中选出获胜者。 CS50 ide provides test function Check50 ，我正在尝试修复这些错误： 1.lock_pairs 如果创建循环则跳过最后一对 2.lock_pairs 如果创建循环，则跳过中间对。

我的逻辑错了吗？

int graph[nodes_count][nodes_count];
bool check_cycle()
{
    //if a node is visited during checking cycles visited[]=true
    bool visited[nodes_count];
    bool circle = false;
    return gointo(circle, visited, 0);
}
bool gointo(bool &circle, bool visited[], int to)
{
// start trip form one node in the graph check if it have been visited ( Cycle )
    visited[to] = true;
    for (int n = 0; n < nodes_count; n++)
    {
        if (graph[to][n])
        {
            if (visited[n])
            {
                circle = true;
            }
            else
            {
                gointo(visited, n);
            }
            break;
        }
    }

    return circle;
}

我的完整解决方案：https://pastebin.com/sbua3EGA
感谢您的宝贵时间，抱歉英语不好:)

Answer 1

你的算法在无向图中是正确的。在有向图中，它并不那么明显。

首先，从节点0开始，你可能不会访问所有的节点。反例： 1 -> 0 -> 2

从节点0开始检查时，根本不会访问1。如果 1 也有一个循环的边缘，您将不会检测到它。这意味着，您应该为每个顶点创建一个循环，如果尚未访问它，则运行 'gointo' 函数。

通过上述更改，您最终可能会发现没有任何循环。

例如：

1 -> 2 -> 3

4 -> 2

如果您首先执行 gointo(1)，您会将 1、2 和 3 标记为已访问。然后当调用 gointo(4) 时你会 'detect a cycle'，因为 4 有边到已经标记的顶点。这就是为什么您需要两个数组，一个告诉您已经访问过该节点，另一个告诉您在此特定的 gointo 调用中访问了该节点。

代码应如下所示：

int graph[nodes_count][nodes_count];
bool check_cycle()
{
    //if a node is visited during checking cycles visited[]=true
    bool visited[nodes_count];
    bool this_call[nodes_count];
    bool circle = false;
    for (int i = 0; i < nodes_count; ++i)
    {
         if(!visited[i] && gointo(circle, visited, i))
           return true;
    }
    return false;
}
bool gointo(bool &circle, bool visited[], int to)
{
// start trip form one node in the graph check if it have been visited ( Cycle )
    visited[to] = true;
    this_call[to] = true;
    for (int n = 0; n < nodes_count; n++)
    {
        if (graph[to][n])
        {
            if (visited[n] && this_call[n])
            {
                circle = true;
            }
            else if(!visited[n])
            {
                gointo(visited, n);
            }
        }
    }
    this_call[to] = false;
    return circle;
}

检查有向图是否有环 CS50 tideman

check if there is a cycle in directed graph CS50 tideman

c

algorithm

cs50

adjacency-matrix

directed-graph