使用 DFS 检测 Tideman 中的周期

Question

为什么该算法不能检测循环？

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // array[0] being true means that there is an edge or more pointing at candidate number 0
    bool array[candidate_count];
    for (int l = 0; l < pair_count; l++)
    {
        // add an edge, as long as it doesn't make a cycle
        if (!will_cycle(array, pairs[l].loser))
        {
            locked[pairs[l].winner][pairs[l].loser] = true;
            array[pairs[l].loser] = true;
        }
    }
}
// index is the index of the candidate the edge will be pointing at if it's added
// the function temporarily sets array[index] as true, like there's an edge pointing at it
// the function then iterates over all the array array, if they're all true it means there'll be a cycle.
// so it's undo the array[index] to false again.
// and if there's at least one false in the array array, it means there won't be a cycle
bool will_cycle(bool array[], int index) // return true if it will make a cycle
{
    array[index] = true;
    int flag = 0; // var for number of true candidates
    for (int i = 0; i < candidate_count; i++)
    {
        if (array[i])
            flag++;
    }

    if (flag == candidate_count) // they're all true
    {
        array[index] = false;
        return true;
    }
    return false;
}

虽然（在我的理解中）图中的循环意味着没有源的图，并且源是没有指向它们的边的候选者，所以“数组”数组全部为真意味着所有候选者都至少有一条边指向它们，所以这是一个循环。

为什么不能通过有关 lock_pair 跳过对的 check50 测试，这将导致循环，尽管我测试了它并且工作正常？ 为什么我必须使用像 DFS 这样的算法，为什么 check50 不喜欢这样？

我尝试测试 cs50 网站 pset 页面后台标题中找到的 Alice、Charlie 和 Bob 的示例。我追踪了它，发现我的算法在跳过最后一对（这给出了一个循环）方面运行良好，甚至给出了正确的获胜者名字。

Answer 1

问题是你关于寻找周期的假设是完全错误的。 假设你有 5 个候选人，

a,b,c,d,e

如果你有对

(a,b), and (b,c)

你不能添加

(c,a)

句点，因为这会产生一个循环。

所以问题是你的算法是错误的。此外，您没有使用深度优先搜索。你根本没有穿越深度。你唯一要做的就是检查这是否会让每个候选人都成为某人的失败者。这不是基本情况。然而，这非常接近您在下一步中检测获胜者所需的内容。

你需要问自己你在寻找什么，如果有一个循环会发生什么？然后防止这种情况发生。有很多方法可以做到这一点。你可以不断地从赢家走到输家，直到你发现要么存在循环，要么不存在。您可以查看是否从输家开始，然后向后查看是否存在锁定对，其中您的输家路径永远是您最初赢家的赢家。在所有情况下，您最初都需要传入您建议添加到图表中的对的两个成员。