根据上图,DFS 应该是: 0 1 3 5 4 2
但它返回 0 1 3 5 2
(这只发生在一种情况下。我我在这里做错了吗?)
代码:
import java.util.Stack;
public class DFSDetectCycleSelf {
static int arr[][] = {
{ 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0 }
//working fine for static int arr[][]={{0,1,1,0,0,0},
// {0,0,0,1,1,0},
//{0,0,0,0,0,1},
//{0,0,0,0,0,0},
//{0,0,0,0, 0,0},
//{0,0,0,0,0,0}};
static Stack<Integer> stack;
DFSDetectCycleSelf(){
stack = new Stack<Integer>();
}
public static void main(String[] args){
DFSDetectCycleSelf df = new DFSDetectCycleSelf();
PrintDFS();
}
public static void PrintDFS(){
int source = 0;
int numberOfNodes = arr[source].length;
int [] visited = new int[numberOfNodes];
int v;
stack.push(source);
while (!stack.isEmpty()){
v = stack.pop();
if(visited[v]==0) {
visited[v] = 1;
System.out.println(v);
}
for(int i=0;i<numberOfNodes;i++){
if(arr[v][i]==1 && visited[i]==0){
stack.push(v);
System.out.println(i);
visited[i]=1;
v = i;
}
}
}
}
}
最佳答案
这应该有效:
public static void PrintDFS(){
int source = 0;
int numberOfNodes = arr[source].length;
int [] visited = new int[numberOfNodes];
int v;
stack.push(source);
while (!stack.isEmpty()){
v = stack.pop();
if(visited[v]==0) {
visited[v] = 1;
System.out.println(v);
for(int i=0;i<numberOfNodes;i++){
if(arr[v][i]==1)
stack.push(i);
}
}
}
}
原始代码中的主要问题是在 for 循环中:当 arr[v][i] == 1
时这意味着i
v
的邻居。你不应该推i
进入堆栈而不是 v
:您想要访问 v
的邻居并且不再访问v
再次。
此外,无需检查 visited[i] == 0
推前i
入栈。当i
将从堆栈中弹出(稍后),代码将检查其访问状态。
更新
(a) 输入 ( arr
) 不反射(reflect)问题开始时呈现的图表。需要修改为:
static int arr[][] = {
{ 0, 1, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0 }
};
(b) 如果边是有序的(从某种意义上说,边 (x) -> (y)
应该在边 (x) -> (y+1)
之前遍历),那么确实,正如 Alexis C 之前所建议的,for 循环需要向后移动
for (int i = numberOfNodes - 1; i >= 0; i--) {
应用这些修复后,输出将变为:
0
1
3
5
4
2
关于java - 为什么这个 DFS 代码在某些情况下不起作用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30951715/