广度优先搜索算法

介绍

广度优先算法按照一种同心圆的方式，首先访问所有和初始顶点邻接的顶点，然后访问与邻接节点邻接的所有未访问到的节点，以此类推，直到所有与初始顶点同在一个连通分量中的顶点都访问过了为止。如果图中仍然存在未被访问的节点，该算法必须从图的其他连通分量中的任意顶点重新开始。

使用队列来跟踪广度优先搜索的操作是比较方便的，该队列先从遍历的初始顶点开始，将该顶点标记为已访问。在每次迭代的时候，该算法找出所有和队头顶点邻接的未访问节点，并将它们标记为已访问，再把它们入队，然后将队头节点从队列中移除(因为该节点所有可能的下一步已经在队列中，该节点被pass)。

上述介绍比较难懂，广度优先算法致力于解决的问题可以概括为：在一个图中已知起点与终点，求从起点出发到终点的最短路径。起点即初始节点，终点为目标节点，从初始节点出发开始广度优先遍历搜索，第一次到达目标节点时走过的路径即位最短路径。

算法实现

伪代码

BFS(Graph)
  //实现给定图的广度优先查找
  //输入：图G=<V,E>
  //输出：图G的顶点，按照被BFS遍历访问的先后次序，用连续的整数标记
  //将V中的每个顶点标记为0，表示未访问
  count = 0
  for each vertex v in V do
    if v is marked with 0
      bfs(v)
  
  bfs(v)
      //访问与v邻接的所有未访问节点，根据访问顺序标记值count
      count++
      mark v with count and initialize a queue with v
      while the queue is not empty do
        for each vertex w in V adjacent to the front vertex do
          if w is marked with 0
            count++
            mark w with count
            add w to the queue
        remove the front vertex from the queue

BFS实现框架

//返回从起始节点到目标节点所需要的最少步数
int BFS(Node start, Node target) {
  Queue<Node> q = new LinkedList<>();
  Set<Node> visited = new HashSet<>();
  q.offer(start);
  visited.add(start);
  int step = 0;
  
  while(!q.isEmpty()) {
    int size = q.size();
    for(int i = 0; i < size; i++) {
      Node cur = q.poll();
      if(cur.equals(target) {
        return step;
      }
      //将当前节点的所有邻接节点加入遍历队列
      for(Node n : cur.adjacent()) {
        //这里还可以根据限制条件做过滤
        
        //判断是否被访问过
        if（n not in visited) {
          q.offer(n);
          visited(n);
        }
      }
      //当一个节点的所有下一步都搜索完成时，步数加一
      step++;
    }
  }
}

算法实践

Leetcode 752

题目可以简单描述为：

一个锁上有四个转盘，每个转盘上有0-9十个数字，每次只能转一个转盘上的一个数字，求从0000开始转到目标密码target需要的次数，在此过程中，不能出现给定的数字，即deadends数组中的所有元素都不能出现。

根据上述BFS算法的实现框架，该问题的解决如下：

public int openLock(String[] deadends, String target) {
      //将deadends初始化在visited中，是因为可以视deadends为已访问的节点，遇到时跳过
    	Set<String> visited = new HashSet<>(Arrays.asList(deadends));
      Queue<String> path = new LinkedList<>();
      path.offer("0000");
      int step = 0;
      while (!path.isEmpty()) {
          int size = path.size();
          for (int s = 0; s < size; s++) {
              String p = path.poll();
              if (visited.contains(p)) {
                  continue;
              }
              if (target.equals(p)) {
                  return step;
              }
              for (int i = 0; i < 4; i++) {
                  String up = upward(p, i);
                  path.offer(up);
                  String down = downward(p, i);
                  path.offer(down);
              }
              visited.add(p);
          }
          step++;
      }
      return -1;
  }  
  
  
  private String upward(String path, int index) {
      char[] pc = path.toCharArray();
      if (pc[index] == '0') {
          pc[index] = '9';
          return new String(pc);
      }
      pc[index]--;
      return new String(pc);
  }
  
  private String downward(String path, int index) {
      char[] pc = path.toCharArray();
      if (pc[index] == '9') {
          pc[index] = '0';
          return new String(pc);
      }
      pc[index]++;
      return new String(pc);
  }

时间复杂度分析

图以邻接表形式存储时，最坏情况下，每个节点与每条边都需要访问一次，时间复杂度为 O(|V| + |E|)
图以邻接矩阵存储时，最坏情况下，查找每个节点的邻接节点需要时间为 O(V), 即该节点所在的行和列，V个节点的时间复杂度为 O(|V|^2)

发布于 2021-06-27