java - Why this DFS code is not working in some cases?

Question

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

    }
}

}

Answer 1

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

Answer 2

The problem with your code is

...
v = i; // shouldn't be there
...

This is the general case iterative algorithm to visit all nodes in a graph

WHILE there exists a graph node not marked loop
    Find an unmarked node F
    Add node F to collection (stack or queue)
    WHILE the collection is not empty loop
        Remove a node N from the collection
        IF the node N is unmarked
            Mark node N
            Add all adjacent nodes of node N to the collection
            Process node N

The collection depends on the problem you need to solve. If the problem will be solved by looking at shortest path, the queue (meaning BFS) is the way to go. If the problem will be solved by knowing the route taken like in a labyrinth, the stack (meaning DFS) in the way to go. Also, in the case of a tree (like in this problem) where you know the root node, the first two lines of the algorithm are unnecessary.

An important part of the inner loop is to prepare the future processing of adjacent nodes, but it's important not to follow those links to the adjacent nodes and the v = i; changes the node by following the link. It is unnecessary to follow the link because those nodes are being placed in the collection and will be processed in the future.

The role of the inner loop is put the emphasis on the node N only. This partitioning of the problem helps simplify the algorithm and make it easier to perform the bigger task which is to visit and process all nodes only once.