高效练习图论算法的方法

Question

我刚刚在《算法导论》一书中读到了广度优先搜索算法，并在纸上手动模拟了该算法。现在我想练习实现它的代码。

我曾考虑过从头开始实现所有数据结构（如邻接表、"颜色"、"距离"和"父节点"数组），但后来我想起了目前存在的图形库，例如Boost图形库和Python中的其他图形API。

我还尝试在UVA和Sphere Judge Online上寻找一些与BFS相关的问题，但我无法确定哪些问题需要BFS解决方案。

我的问题是，练习这些图形算法最无痛的方法是什么（不仅限于BFS，还包括当我想要实现DFS，Dijkstra，Floyd-Warshall等时也会有用）。欢迎提供练习问题的网站。

- Steve

Answer 1

我个人认为，理解这些内容的最佳方式是从头开始实现图形表示法。

一方面，这将向您展示实际实现注意事项，从中了解特定算法可能会有什么样的有趣/好的/高效等方面。另一方面，我认为，通过自下而上的方法理解图形及其在现实生活中的应用，包括其影响（递归、性能/可扩展性、应用程序、替代方案等），会更加容易。

但也许这只是我的个人口味。以上内容非常个人化。

- balpha

Answer 2

我觉得你的问题很有趣，我上网搜索了一下，发现了JGraphEd。

它并不涵盖所有的图算法，但看起来是一个进行实验的好工具。

- Nick Dandoulakis

Answer 3

我同意balpha的观点。真正学习和理解算法的最佳方法是实现它。只需选择一个算法并实现它。当你遇到困难或不确定时，可以查看一些现有的示例。然后，您将能够从理解的角度将自己的思考与他人进行比较，而不仅仅是接受所提供的内容。

一旦您学到了想要的知识，巩固您的理解的最佳方法是尝试向他人教授或描述它。您可能会有一些愿意听您讲解的人，或者至少您可以为刚刚学习的算法编写博客文章，以供新手参考。

但是，如果您正在寻找“无痛苦”的方法，那么也许您应该完全避开算法；-）

- user108687

---

仅供记录，引号应该放在“最无痛苦”的周围。 - Steve

Answer 4

这个网站可能会对你有所帮助

在这里，你可以找到ACM问题集中每个问题的描述。你可以看到每个问题的类别和解决它的提示。只需浏览与图形相关的问题。好的建议是，如果你自己尝试解决问题失败了，才使用这些提示。

- dpetek

Answer 5

展示一些最短路径算法在真实数据上的可视化，其中探索区域以黄色显示：

• （双向）Dijkstra
• A*

- Karussell