java - 查找节点之间的最短路径，以及图是否连通

Question

显然下面是一个家庭作业问题。我听不懂我的教授在说什么，所以我什至不需要知道从哪里开始寻找找到这个问题的答案所需的信息。如果你能给我一些关于在哪里学习这些东西以及你如何解决这个问题的线索，我将不胜感激。

在下图中，找到两个节点之间的最短路径 - 您的选择，但要让问题变得有趣。

这是一个连通图吗？

Answer 1

您应该使用星型算法来找到两个节点之间的最短路径。 http://en.wikipedia.org/wiki/A_star

您可以使用门格尔定理来判断它是否正在连接 http://en.wikipedia.org/wiki/Menger%27s_theorem

---

Answer 2

最好先了解图形在内存中的表示方式。如果由您决定，您可以使用二维数组，因为这是表示加权边缘的最简单方法。

最容易实现的最短路径算法可能是 Djikstra 算法，它比 A* 稍慢但不太复杂。要使用 Djikastra，您首先要实现优先级队列。在 Java 中有一个 PriorityQueue 类，否则您必须自己实现它。之后，使用 Wikipedia 或其他任何地方提供的伪代码，实现应该相当简单。