无向图连接

Question

我有一个作业正在尝试使用 Java 完成，任何帮助或指导将不胜感激，下面是问题

I have been given an integer N and two arrays A and B, I should return true if there exists a path from vertex 1 to N going through all vertices, one by one , in increasing order or false otherwise.

给定 N=4 ，A=[1,2,4,4,3] 和 B[2,3,1,3,1] 下面的函数应该 return 为真，因为有一个路径 (1 -> 2 -> 3 -> 4) 使用边 (1,2) (2,3) 和 (4,3)

public boolean dfs(int N, int[] A, int[] B){}

Answer 1

您确切地知道需要的 N-1 条边 -- 1-2 或 2-1、2-3 或 3-2 等等 -- 因此无需搜索图形.

您应该只创建一个 N-1 布尔值数组来表示这些边。检查您拥有的所有边，每当您看到需要的边时，将其布尔值设置为 true。

最后，检查您的所有布尔值是否为真。

Answer 2

正如@Matt 所建议的，您不需要使用搜索查看所有边；相反，查找每个（已知的）所需的边就足够了；一旦发现缺少所需的边缘，您就会失败。因此，

public static boolean incrementalConnected(int N, int A[], int B[]) {
    Set<String> edges = new HashSet<>(N); // quick lookup
    for (int i=0; i<N; i++) {
        int lo = Math.min(A[i], B[i]);
        int hi = Math.max(A[i], B[i]);
        edges.add("" + lo + "-" + hi);    // undirected
    }

    for (int i=1; i<N; i++) {
        if (! edges.contains("" + i + "-" + (i+1))) {
            return false; // missing a required edge
        }
    }
    return true; // all required edges present
}

无向图连接

Undirected graph connection

java

algorithm

graph-theory