首页 > itarticle > bfs 1 – graph traversal

bfs 1 – graph traversal

admin 11月 11, 2020 0

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, vector<vector<bool>>& isVisited, int rr,
         int cc) {
  int rows = grid.size(), cols = grid[0].size();
  int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};  // Matrix的基本bfs遍历方法
  queue<pair<int, int>> q;
  q.push(make_pair(rr, cc));
  while (!q.empty()) {
    pair<int, int> cur = q.front();
    q.pop();
    isVisited[cur.first][cur.second] = true;
    for (int i = 0; i < 4; i++) {
      int nextx = cur.first + dir[i][0], nexty = cur.second + dir[i][1];
      if (nextx >= rows || nextx < 0 || nexty >= cols || nexty < 0 ||
          isVisited[nextx][nexty] || !grid[nextx][nexty])
        continue;
      q.push(make_pair(nextx, nexty));
    }
  }
}
int numIslands(vector<vector<bool>>& grid) {
  if (grid.size() == 0) return 0;
  if (grid[0].size() == 0) return 0;
  int num = 0, rows = grid.size(), cols = grid[0].size();
  vector<vector<bool>> isVisited(rows, vector<bool>(cols, false));
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (!isVisited[i][j] && grid[i][j]) {  // 是1才进去算!
        num++;
        bfs(grid, isVisited, i, j);
      }
    }
  }
  return num;
}

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;
  unordered_set<UndirectedGraphNode*> isVisited;
  queue<UndirectedGraphNode*> q;
  q.push(node);
  while (!q.empty()) {
    UndirectedGraphNode* cur = q.front();
    q.pop();
    if (values[cur] == target) return cur;  // 找到立马返回，不能放后边
    isVisited.insert(cur);
    for (auto i : cur->neighbors) {  // Graph的基本bfs遍历方法
      if (isVisited.find(i) == isVisited.end()) {
        q.push(i);
      }
    }
  }
  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]) {
      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);
  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];
}