According to above picture DFS should be: 0 1 3 5 4 2
but it's returning 0 1 3 5 2
(This is happening only for one case. What I am doing wrong here?)
code:
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;
}
}
}
}
}
This should work:
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);
}
}
}
}
The main issue in the original code was in the for-loop: when arr[v][i] == 1
it means that i
a neighbor of v
. you should not push i
into the stack and not v
: you want to visit the neighbor of v
and not re-visit v
again.
Also, there is no need to check visited[i] == 0
before pushing i
into the stack. When i
will be popped from the stack (later on) the code will check its visited status.
Update
(a) The input (arr
) does not reflect the graph presented at the beginning of question. It needs to be changed to:
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) If the edges are ordered (in the sense the edge (x) -> (y)
should be traversed before the edge (x) -> (y+1)
) then indeed, as suggested earlier by Alexis C, the for-loop needs to go backwards
for (int i = numberOfNodes - 1; i >= 0; i--) {
One these fixes are applied the output becomes:
0
1
3
5
4
2