检查有向图是否有环 CS50 tideman

check if there is a cycle in directed graph CS50 tideman

检查循环程序从图中的第一个节点到图中每个锁定的节点->检查它之前是否访问过,然后它是一个循环,否则从检查的下一个节点递归重复。 当我自己测试它时它可以工作但是当我在 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
感谢您的宝贵时间,抱歉英语不好:)

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

首先,从节点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;
}