algorithm - 图中的路径是否连通

Question

我对图中的路径有疑问。我们有一个图，例如：
5 个顶点和 4 个边
1 2 第一个连接到第二个，等等
2 3
3 4
5 1

现在我想回答问题（例如）：如果顶点 1 连接到顶点 3。答案是肯定的 - 因为我们有路径“1 -> 2 -> 3。

你有什么建议？

我不知道该怎么做。

Answer 1

这将需要您进行一些研究。这个想法是使用像深度优先或广度优先这样的图遍历算法。从一个顶点（如示例中的 1）开始并继续遍历图形，直到您到达目标节点（示例中为 3）或找不到更多可遵循的路径。

Answer 2

DFS 或 BFS（我更喜欢 DFS，因为它会导致更少的回溯）从起始节点开始，如果算法完成但没有找到无法访问的节点。