BFS 1 - Graph Traversal

BFS in Graph vs. BFS in Tree: 无向图 vs. 有向图; 需要标记数组 vs. 不需要

时间复杂度：O(m + n)，m是边数，n是点数

1. Number of Islands

Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Find the number of islands.

void bfs(vector<vector<bool>> &grid, int starti, int startj) {
    queue<pair<int, int>> q;
    q.push(make_pair(starti, startj));
    int neibor[4][2] {-1, 0, 1, 0, 0, -1, 0, 1};
    while(!q.empty()) {
        auto tmp = q.front();
        q.pop();
        grid[tmp.first][tmp.second] = 0;  // 记得标记
        for(int i = 0; i < 4; i++) {
            int nextx = tmp.first + neibor[i][0];
            int nexty = tmp.second + neibor[i][1];
            // 不要忘了先判断边界，否则会越界访问grid
            if(nextx >= 0 && nextx < grid.size() && nexty >= 0 && nexty < grid[0].size() && grid[nextx][nexty] == 1) {
                grid[nextx][nexty] = 0;  // ！！放的时候就标记，记得标记，会优化时间！防止重复进来
                q.push(make_pair(nextx, nexty));
            }
        }
    }
}
int numIslands(vector<vector<bool>> &grid) {
    // 1. 找这个矩阵里的第一个1，放到queue里
    // 2. bfs开始找，然后弄成0
    // 3. 重复上述2步，直到矩阵没有1
    if (grid.size() == 0) return 0;
    if (grid[0].size() == 0) return 0;
    int num = 0, rows = grid.size(), cols = grid[0].size();
    int num_island = 0;
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            if(grid[i][j] == 1) {
                num_island++;
                bfs(grid, i, j);
            }
        }
    }
    return num_island;
}

2. Search Graph Nodes

Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can't find.

UndirectedGraphNode* searchNode(vector<UndirectedGraphNode*>& graph,
                                    map<UndirectedGraphNode*, int>& values,
                                    UndirectedGraphNode* node,
                                    int target) {
    if(graph.size() == 0) return NULL;
    queue<UndirectedGraphNode*> q;
    unordered_set<UndirectedGraphNode*> visited;
    q.push(node);
    visited.insert(node);
    while(!q.empty()) {
        UndirectedGraphNode *cur = q.front();
        q.pop();
        if(values[cur] == target) return cur;  // 弹出的时候，判断结果
        for(auto n: cur->neighbors) {
            if(visited.find(n) != visited.end()) continue;
            q.push(n);
            visited.insert(n);  // 放的时候就标记
        }
    }
    return NULL;
}

3. Graph Valid Tree

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 check whether these edges make up
a valid tree.
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.
Example
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

bool validTree(int n, vector<vector<int>>& edges) {
  int nedges = edges.size();
  // 边数对，且从任意一点，能遍历到所有节点
  if (nedges != n - 1) return false;
  set<int> nodes;
  unordered_map<int, vector<int>> orders;
  for (int i = 0; i < nedges; i++) {
    orders[edges[i][0]].push_back(edges[i][1]);
    orders[edges[i][1]].push_back(edges[i][0]);
  }
  queue<int> q;
  q.push(0);
  nodes.insert(0);  // just pick one to start
  while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (auto i : orders[cur]) {
      // !! nodes可以充当visited的角色，不需要再开一个visited了
      if (nodes.find(i) != nodes.end()) continue;
      nodes.insert(i);
      q.push(i);
    }
  }
  return nodes.size() == n;
}

Union-Find algorithm

bool validTree(int n, vector<vector<int>>& edges) {
  vector<int> root(n, -1);
  for (int i = 0; i < edges.size(); i++) {
    int root1 = find(root, edges[i][0]);
    int root2 = find(root, edges[i][1]);
    if (root1 == root2) return false;
    root[root1] = root2;
  }
  return edges.size() == n - 1;
}
int find(vector<int>& root, int e) {
  if (root[e] == -1)
    return e;
  else
    return root[e] = find(root, root[e]);
}

4.Clone Graph

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
  if (node == NULL) return NULL;
  // 1. BFS: Get list of all the nodes
  // 2. Copy these nodes, and get hash map: old->new
  unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> corres;
  unordered_set<UndirectedGraphNode *> visited;
  queue<UndirectedGraphNode *> q;
  q.push(node);
  visited.insert(node);  // 图的BFS一定注意有visited
  while (!q.empty()) {
    UndirectedGraphNode *cur = q.front();
    corres[cur] = new UndirectedGraphNode(cur->label);
    q.pop();
    for (auto i : cur->neighbors) {
      if (visited.find(i) != visited.end()) continue;
      q.push(i);
      visited.insert(i);
    }
  }
  // 3. Copy the edges.
  for (auto i : corres) {
    for (auto j : i.first->neighbors) {
      i.second->neighbors.push_back(corres[j]);  // push corres[j]
    }
  }
  return corres[node];
}