javadata-structuresmicrosoft-distributed-file-system

Why this DFS code is not working in some cases?


enter image description here

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;
            }
        }

    }
}

}


Solution

  • 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