dfs && bfs

• DFS
  

  using stack, the vertical data structure.

• “Intuition”

  We need to find all subtrees of the current node first, and then find nodes which have the same parent with the current node.

• Basic : Binary Tree preorder, inorder, postorder

• Using DFS solves graphs(matrixes)

323.Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

0          3
|          |
1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

0           4
|           |
1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int (int n, vector<pair<int, int>>& edges) {
    if(edges.size() == 0)
        return n;
    int comNum = 0;
    vector<vector<int>> ajustList(n, vector<int>(0));
    vector<bool> visited(n, false);
    stack<int> nodeStack;
    for(int i = 0; i < edges.size(); i++){
        ajustList[edges[i].first].push_back(edges[i].second);
        ajustList[edges[i].second].push_back(edges[i].first);
    }

    for(int i = 0; i < n; i++){
        if(!visited[i]){
            comNum++;
            nodeStack.push(i);
            while(!nodeStack.empty()){
                int top = nodeStack.top();
                nodeStack.pop();
                visited[top] = true;
                for(int ajNode : ajustList[top]){
                    if(!visited[ajNode])
                        nodeStack.push(ajNode);
                }
            }
        }
    }

    return comNum;
}

200. Number of Islands

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int numIslands(vector<vector<char>>& grid) {
    int num = 0;
    if(grid.size() == 0)
        return num;
    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
    stack<pair<int, int>> gridStack;
    for(int i = 0; i < grid.size(); i++){
        for(int j = 0; j < grid[i].size(); j++){
            if(!visited[i][j] && grid[i][j] == '1'){
                num++;
                gridStack.push(make_pair(i, j));
                while(!gridStack.empty()){
                    auto node = gridStack.top();
                    gridStack.pop();
                    int curi = node.first;
                    int curj = node.second;
                    visited[curi][curj] = true;
                    if(curi + 1 < grid.size() && grid[curi + 1][curj] == '1' && !visited[curi+1][curj]) gridStack.push(make_pair(curi + 1, curj));
                    if(curj + 1 < grid[0].size() && grid[curi][curj + 1] == '1' && !visited[curi][curj + 1])gridStack.push(make_pair(curi, curj + 1));
                    if(curi - 1 >= 0 && grid[curi - 1][curj] == '1' && !visited[curi - 1][curj])gridStack.push(make_pair(curi - 1, curj));
                    if(curj - 1 >= 0 && grid[curi][curj - 1] == '1' && !visited[curi][curj - 1])gridStack.push(make_pair(curi, curj - 1));
                }
            }
        }
    }

    return num;
}

• BFS
  

  using queue, the horizontal data structure

• “Intuition”

  We need to get all nodes having the same parent first, and then get a node’s subtrees.

• Basic : Binary Tree level order traversal

• Using BFS solves graphs(matrixes)
  542. 01 Matrix
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

  vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { queue<pair<int, int>> mq; for(int i = 0; i < matrix.size(); i++){ for(int j = 0; j < matrix[i].size(); j++){ if(matrix[i][j] == 0) mq.push(make_pair(i, j)); else matrix[i][j] = INT_MAX; } } vector<pair<int, int>> directions; directions.push_back(make_pair(1, 0)); directions.push_back(make_pair(-1, 0)); directions.push_back(make_pair(0, 1)); directions.push_back(make_pair(0, -1)); while(!mq.empty()){ auto top = mq.front(); mq.pop(); for(auto dire : directions){ int curi = top.first + dire.first; int curj = top.second + dire.second; if(curi < 0 || curi >= matrix.size() || curj < 0 || curj >= matrix[0].size() || matrix[curi][curj] < matrix[top.first][top.second] + 1) continue; matrix[curi][curj] = matrix[top.first][top.second] + 1; mq.push(make_pair(curi, curj)); } } return matrix; }