思路
BFS
代码

leetcode 847. 访问所有节点的最短路径

August 06, 2021

思路

BFS

给定图是一个无向无权联通图,也就是两个节点间的距离可以被看作是 1, 对无权无向图求最短路可以使用BFS,理由是每次用BFS向下搜索时,只会走一步,也就是说,每次BFS一步能走到的节点都是最短的。

又由于每个节点都可以被遍历多次,如果只是简单的判断节点 x 是否被遍历过,并不能解决问题,所以我们需要找到另外一种状态 state, state 能唯一确定节点 x 在遍历中的信息,遍历过程中如果遇到state已经出现过,则跳过当前遍历。

伪代码表示

queue = [initial state]
visited = []
while (queue is not empty) {
  state = queue.head()
  visited.add(state)
  遍历 state 的下一个状态 nextState
    if (!visited.has(nextState))
      queue.push(nextState)
}

这里我们使用二元组 [节点序号i, 已经被遍历过的序列route]来表示,每个节点有无遍历可以使用 1/0 表示,因此 route 可以使用一个二进制序列表示简化运算。

另外需要注意我们要求的是路径长度,也是遍历的层级数,因此还需要一个状态带上当前层级数,所以最后的状态为

[v, route, level] 分别表示节点序号,当前已遍历的节点序列,当前遍历的路径长度

代码

/**
 * @param {number[][]} graph
 * @return {number}
 */
var shortestPathLength = function (graph) {
  const n = graph.length,
    queue = [];
  let visited = Array.from({ length: n }).map(_ => new Set());

  for (let i = 0; i < n; i++) {
    queue.push([i, 1 << i, 1]);
    visited[i].add(1 << i);
  }

  while (queue.length) {
    let [node, route, dist] = queue.shift();
    for (let next of graph[node]) {
      let nextRoute = route | (1 << next);

      if (nextRoute === (1 << n) - 1) {
        return dist;
      }

      if (!visited[next].has(nextRoute)) {
        queue.push([next, nextRoute, dist + 1]);
        visited[next].add(nextRoute);
      }
    }
  }

  return 0;
};
  • 时间复杂度: $O(n ^ 2 * 2 ^ n)$, 其中 n 为节点数
  • 空间复杂度: $O(n ^ 2)$, 其中 n 为节点数

feiker 少年起而行之