Hopcroft-Karp 的 C 算法

Question

我正在研究图算法理论(我是数学家，对计算机科学一无所知)，并且我确实有一些与 self 匹配的问题，出于严重的原因我使用 Hopcroft-Karp ( Hopcroft–Karp algorithm )。我不想用手解决它们，所以我想使用一个程序来解决。但因为我正在学习 C，所以我有兴趣有一个 C 代码来解决它。我发现了一些有关 C++ 的想法，但我还无法阅读此内容(可能是几年后的下一个编程语言......)

你们中有人在他的计算机上有一个很好的 C 编程 Hopcroft Karp 算法并愿意与我和社区分享吗？这不仅仅是代码，如果能解释它在 C 中的工作原理，我会感到惊讶。我还无法想象如何使用指针来使用 BFS 和 DFS。如果有人有代码+解释，请提前致谢。

====

编辑:正如我对 Young Developers 所说的那样，我现在已经 fork 了该存储库，并尝试在对 C 语言不太了解的情况下尽我所能将其实现。您可以在 main.c 文件中找到所有内容，没有 header 等存在。每个有“TODO”的地方都意味着还有事情要做。因此，此刻，我实现了所有内容并将其更改为 C 功能，如您在此处所看到的。 https://github.com/Dabendorf/hopcroft-karp/blob/master/main.c

它正在编译，但是在某处有一个我找不到的错误，因为它给出了错误的结果。这与原作者从一开始计数而我使用普通数组从零开始计数这一事实有关。但这只是我的猜测。所以错误也可能在其他地方。

有人看到吗？

Answer 1

Vermagav 实现 Hopcroft–Karp Algorithm与类相关，其他功能不直接映射到 C。也许从该实现开始是您最好的选择。如果开始创建 Vermagav 项目的 Github 分支，我们都可以帮助您。