检查是否可以到达相互链接的两点列表之间的所有点的算法

Question

给定几对点，我想找出一种方法来确定是否可以从彼此到达所有点。

例如，给定点之间的这些无向路径 [1,6]:

我可以看到所有点都可以相互到达。

然而，对于类似的东西：

5 - 2
0 - 5
6 - 7

无法从 0、5 和 2 到达点 6 和 7。

我尝试了很多 HashMaps 和其他存储数据的方法，但我似乎无法找到一种方法来验证这一切。特别是在第一个例子中给出像 1 这样只有一个实例的点。

我已经能够检查 2 个给定点之间是否存在路径：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class GondolaLiftsOne {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt(), start = in.nextInt(), destination = in.nextInt(), count = 0, entries = 0;
        HashMap<Integer, ArrayList<Integer>> paths = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int key = in.nextInt();
            if (!paths.containsKey(key)) paths.put(key, new ArrayList<>());

            entries++;
            paths.get(key).add(in.nextInt());
        }

        while (destination != start) {
            if (count > entries*2) {
                System.out.println("No, but you can walk!");
                return;
            }
            destination = getPath(paths, destination);
            count++;
        }
        System.out.println("YESSIREE");
    }

    public static int getPath (HashMap<Integer, ArrayList<Integer>> paths, int destination) {
        for (Map.Entry<Integer, ArrayList<Integer>> entry : paths.entrySet()) {
            for (int value : entry.getValue()) {
                if (value == destination) return entry.getKey();
            }
        }
        return -1;
    }
}

但除此之外，我很难弄清楚所有的点是否都相连。我似乎无法在网上找到任何类似的问题。

Answer 1

这对于无向图来说基本上很简单BFS。

创建邻接表
如果你有任何顶点 in-degree 0, return False
选取任何节点并通过将其邻居排队并维护一个 visited 列表

最后，如果所有的顶点都被标记了true，就知道所有的点都可以到达。

Answer 2

这是您可以使用的一种算法。不知道有没有更好的。

维护一组点，其中每个点都包含由路径链接的点。对于您遇到的每条新边，找出边上的每个点属于哪个集合。

如果他们已经在同一组中，则无需执行任何操作。
如果它们在不同的集合中，则将这两个集合替换为一个新集合，这就是两者的并集。
如果一个在集合中，而另一个不在集合中，则将新点添加到集合中。
如果它们都不在集合中，请创建一个新集合并添加两个点。

以这种方式遍历完所有边后，看看有多少组。如果不止一个，那么你的图没有连接。

要了解实际效果，请考虑您的第一个示例。

最初，我们的集合是空的。 {}
边 1 4 是情况 4，因为这两个点都不在集合中。所以制作一个包含两个点的新集合。{{1,4}}
边 4 5 是情况 3，因为 4 已经在一个集合中。因此，将 5 添加到集合中。 {{1,4,5}}
边 2 6 是情况 4，因为这两个点都不在集合中。做一个新集合 {{1,4,5},{2,6}}
边 2 4 是情况 2，因为 2 和 4 在不同的集合中。删除这两个集合并用它们的并集替换它们。 {{1,4,5,2,6}}.
边 5 2 是情况 1，因为 2 和 5 已经在同一个集合中。

流程结束时只有一组，所以图是连通的。

检查是否可以到达相互链接的两点列表之间的所有点的算法

Algorithm to check whether all points between a list of two points linked to each other can be reached

java

algorithm