无向图连接
Undirected graph connection
我有一个作业正在尝试使用 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){}
您确切地知道需要的 N-1 条边 -- 1-2 或 2-1、2-3 或 3-2 等等 -- 因此无需搜索图形.
您应该只创建一个 N-1 布尔值数组来表示这些边。检查您拥有的所有边,每当您看到需要的边时,将其布尔值设置为 true。
最后,检查您的所有布尔值是否为真。
正如@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
}
我有一个作业正在尝试使用 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){}
您确切地知道需要的 N-1 条边 -- 1-2 或 2-1、2-3 或 3-2 等等 -- 因此无需搜索图形.
您应该只创建一个 N-1 布尔值数组来表示这些边。检查您拥有的所有边,每当您看到需要的边时,将其布尔值设置为 true。
最后,检查您的所有布尔值是否为真。
正如@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
}