Search code examples
javaarraysdepth-first-searchneighbours

DFS isn't working on 2d array


So I have a a 2darray of colors. The colors are represented by numbers. I have made a dfs that currently only checks for the number 1, which is red. I don;t think I hav the code right. I have a get neighbors that does get the neighbors around the node it is at and adds them to a list. The boards is the array of ints and the visited is an array of true or false if the node has been visited. Here is my dfs:

private int dfs(int startRow, int startCol, int[][]boards, boolean[][] visitedd){
    int f;
    int t;
    visitedd[startRow][startCol] = true;
    for(; startRow < q; startRow++){
        for(; startCol < q; startCol++){
            if(boards[startRow][startCol] == 1 && visitedd[startRow][startCol] == false){
                g+=1;
                f = startRow;
                t = startCol;
                dfs(f, t, boards, visitedd);
            }
        }
    }
    return g;

I'm not sure how to use the get neighbors to properly traverse to the next red.


Solution

  • In DFS you mark child nodes explored as you LEAVE them. Check out this Pseudocode from Wikipedia:

    procedure DFS(G,v):
      label v as discovered
      for all edges from v to w in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
          recursively call DFS(G,w)
    

    Notice you don't check the parent for being visited. You check the children.