# Depth/Breadth First Search

###### tags: `DFS` `BFS`

>Prerequisite: Recursion

## Content
[ToC]

## Depth First Search

DFS is an algorithm that is often used to traverse the tree or the graph as deep as possible. Suppose that we have currently traversed to node i of a graph, we will next pick a possible adjacent node. If the adjacent node is not yet traversed, we will traverse the node and recursively redo the process. We will return to the previous state when we meet the invalid node.
### Example 1
Given a graph and compute the number of islands on the graph. The character '~' means water. There are two types of islands, denoted as '#' and '@'. Also, the initial two numbers represent the row and column of the map. Take the following input for example:

Input:
7 8
~~~~~~@~
~###~~~~
~##~~~~#
~~~@@@~~
~~~@@@~~
~~~~~~~~
~~~~##~~

Output: @:2 #:3

The number of #-typed islands is 3, and the number of @-typed islands is 2.

Note that two '#'s are considered connected only if they are horizontal or vertical neighbors. Diagonal neighbors are not considered connected. The rule is the same for '@'.

In the algorithm, we will go through the board to see whether the current node is either '@' or '#'. If we find a possible pond, we will use the dfs to change the character into '~'. As the code below:

#include <stdio.h>

char board[100][100];

void dfs1(int i, int j, int rows, int cols){
    if(board[i][j] != '@' || i < 0 || i >= rows || j < 0 || j >= cols)
        return;
    else{
        board[i][j] = '~';
        dfs1(i+1, j, rows, cols);
        dfs1(i-1, j, rows, cols);
        dfs1(i, j+1, rows, cols);
        dfs1(i, j-1, rows, cols);
    }
}
void dfs2(int i, int j, int rows, int cols){
    if(board[i][j] != '#' || i < 0 || i >= rows || j < 0 || j >= cols)
        return;
    else{
        board[i][j] = '~';
        dfs1(i+1, j, rows, cols);
        dfs1(i-1, j, rows, cols);
        dfs1(i, j+1, rows, cols);
        dfs1(i, j-1, rows, cols);
    }
}

int main(){
    int row, col;
    scanf("%d %d",&row, &col);
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            scanf(" %c", &board[i][j]);
        }
    }
    int cnt1 = 0;
    int cnt2 = 0;
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            if(board[i][j] == '@'){
                cnt1++;
                dfs1(i, j, row, col);
                for(int i1 = 0; i1 < row; i1++){
            }
            else if(board[i][j] == '#'){
                cnt2++;
                dfs2(i, j, row, col);
            }
        }
    }
    printf("@: %d\n#: %d\n", cnt1, cnt2);
    return 0;
}

### Example 2

Max-pooling is a part of the process of Convolution Central Network. If given an m ✕ n matrix A, please calculate the k-by-k max-pooling of A.
Both m and n are multiples of k. The computation of k-by-k max-pooling is to find the maximum for each k-by-k block of A. Also, the first line contains the number m, n, k, respectively. Take the following input for example:

Input:
4 6 2
1 2 3 4 5 6
6 5 4 3 2 1
9 8 7 6 5 4
4 5 6 7 8 9

Output:
6 4 6
9 7 9

The method of finding the max value of a submatrix will be similar to the previous example. We first go to the initial point of the current submatrix, and we will use dfs to find the current maximum value of the submatrix. As the code below:

#include <stdio.h>
int board[500][500];

int curMax = 0;
void dfs(int i, int j, int row, int col){
    if(i >= row || j >= col) return;
    else{
        if(board[i][j] > curMax) curMax = board[i][j];
        dfs(i+1, j, row, col);
        dfs(i, j+1, row, col);
    }
}

int main(){
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            scanf(" %d", &board[i][j]);
        }
    }
    int pool[m/2][n/2];
    for(int i = 0; i < n; i+=2){
        for(int j = 0; j < n; j+=2){
            dfs(i, j, i+2, j+2);
            pool[i/2][j/2] = curMax;
            curMax = 0;
        }
    }
    
    for(int i = 0; i < m/2; i++){
        for(int j = 0; j < n/2; j++){
            printf("%d ", pool[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

## Breadth First Search

BFS is an algorithm that is often used to traverse the tree or the graph as breadth as possible. Suppose that we have currently traversed to node i of a graph, we will next go through all possible adjacent nodes. If the adjacent node is not yet traversed, we will traverse the node and recursively redo the process.

### Example
Given a MxN matrix where each element can either be 0 or 1. Find the shortest path between a given source cell to a destination cell. The path can only be created out of a cell if its value is 1.

Input:
    mat[ROW][COL]  = {{1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                      {1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                      {1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                      {0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                      {1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                      {1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                      {1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                      {1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                      {1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
    Source = {0, 0};
    Destination = {3, 4};
Output:
    Shortest Path is 11.

Note that BFS will first operate on the adjacent node; therefore, we will need a FIFO data structure to store the order of node traversal.

The queue Q should store the current node coordination and the current distance from the start point to the current point. Also the current distance will be the distance of the previous node distance+1.

As the code below:

#include <iostream>
#include <queue>
#define ROW 9
#define COL 10

using namespace std;

struct Point{
    int x;
    int y;
};
struct queueNode{
    Point pt;
    int dist;
};

int r[] = {1,0,-1,0};
int c[] = {0,1,0,-1};

int BFS(int board[ROW][COL], Point start, Point end){
    bool visited[ROW][COL];
    memset(visited, 0, sizeof(visited));
    
    queue<queueNode> Q;
    queueNode s = {start, 0};
    Q.push(s);
    while(!Q.empty()){
        queueNode cur = Q.front();
        Point curpt = cur.pt;
        
        if(curpt.x == end.x && curpt.y == end.y){
            return cur.dist;
        }
        Q.pop();
        
        for(int i = 0; i < 4; i++){
            int next_i = curpt.x + r[i];
            int next_j = curpt.y + c[i];
            if(next_i < ROW && next_i >= 0 && next_j < COL && next_j >= 0 && visited[next_i][next_j] == 0 && board[next_i][next_j] == 1){
                queueNode next_pt = {next_i, next_j, cur.dist+1};
                Q.push(next_pt);
            }
        }
    }
    return -1;
}
int main(){
    int board[ROW][COL] =
        {
            { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
            { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
            { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
            { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
            { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
            { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
            { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
            { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
        };
    Point source = {0, 0};
    Point dest = {3, 4};
 
    int dist = BFS(board, source, dest);
 
    if (dist != -1)
        cout << "Shortest Path is " << dist << "." << endl;
    else
        cout << "Shortest Path doesn't exist" << endl;
}