My Muri Life

切换主题

本页目录

无向图 ​

本篇主要讲讲无向图的两个非常重要的算法：最小生成树算法和最短路径算法。

最小生成树 ​

最小生成树算法主要是Kruskal算法和Prim算法。

Kruskal算法 ​

Kruskal算法（常用于稀疏图）是一种贪心算法，操作的对象是无向图的边edge，要实现该算法，我们需要用到两个辅助数据结构：并查集与优先队列。

算法过程描述

  1. 首先使用无向图的节点，对节点进行并查集数据初始化；
  2. 然后根据图中的每个edge按照权重大小初始化小堆顶；
  3. 当最小堆不为空时，取出堆顶元素（即权重最小的边）并在并查集中查询形成当前边edge的两个节点（edge.from、edge.to）是否属于同一集合：
    1. 只有当两节点不属于同一集合时，将该边加入生成树（即连接两节点），并且更新集合。
  4. 当最小堆为空时，最小生成树生成完毕。

为什么会用到并查集？
因为若两个顶点已在同一集合内（说明已经通过其他边相连），再将这两个顶点形成的边添加到生成树中，那么就会形成环（死循环）！

JavaScript
const kMST = graph => {
  const nodes = graph.nodes.values()
  // 初始化并查集
  const ufSet = new UnionFindSet(nodes)
  // 根据边的权重初始化小顶堆
  const compare = (e1, e2) => e1.weight - e2.weight
  const queue = new BinaryHeap(compare)
  for (const edge of graph.edges) {
    queue.add(edge)
  }

  const ret = new Set()
  while (queue.length) {
    const edge = queue.poll()
    // 不属于同一集合
    if (!ufSet.isSameSet(edge.from, edge.to)) {
      ret.add(edge)
      ufSet.union(edge.from, edge.to)
    }
  }
}

Prim算法 ​

Prim算法（常用于稠密图）也是一种贪心算法，操作的对象是无向图的节点node，要实现该算法，我们只需要用到一个辅助数据结构：优先队列。

算法过程描述

  1. 从任一点node出发，将该点加入Set中（避免重复使用该点）；
  2. 然后将该点所有相连的边edge加入小顶堆中；
  3. 当最小堆不为空时，取出堆顶元素（即权重最小的边），并考察此边的到达节点tNode是否存在于集合Set中：
    1. 若不存在，则说明此节点为新节点，对应的边edge为最小生成树的一部分，将其加入答案，并更新Set，而此时的新节点tNode对应的边可能存在我们需要的部分答案，故对应的边应该加入小顶堆。
  4. 当最小堆为空时，最小生成树生成完毕。
JavaScript
const pMST = graph => {
  const nodes = graph.nodes.values()
  const compare = (e1, e2) => e1.weight - e2.weight
  const queue = new BinaryHeap(compare)

  const ret = new Set()
  // 用于避免重复考察同一点
  const set = new Set()
  // 从任一节点开始
  for (const node of nodes) {  // 连通图可不写这句
    if (!set.has(node)) {
      set.add(node)
      for (const edge of node.edges) {
        queue.add(edge)
      }
      while (queue.length) {
        const edge = queue.poll()
        const tNode = edge.to
        if (!set.has(tNode)) {
          set.add(tNode)
          ret.add(edge)
          for (const tEdge of tNode.edges) {
            queue.add(tEdge)
          }
        }
      }
    }
  }
}

最短路径 ​

Dijkstra算法 ​

Dijkstra算法（必须规定起点）是一个基于贪心、广度优先搜索、动态规划求一个图中一个点到其它所有点的最短路径的算法。

核心思想：每次从未求出最短路径的点中取出距离起点最短路径的点，以这个点为桥梁更新未求出最短路径的点的距离。

  • dMap：用于存放节点与从出发节点到当前节点的距离，即{ node : number }；
JavaScript
const dijkstra = head => {
  const dMap = new Map()
  // 出发节点到自己的距离为 0
  dMap.set(head, 0)
  // 标记已经选过的节点
  const set = new Set()
  // 辅助函数：用于找出未选过的点中最小距离的点
  const getMinNode = (dMap, set) => {
    let [minNode, minDistance] = [null, Infinity]
    const entries = dMap.entries()
    for (const entry of entries) {
      const [node, distance] = entry
      if (!set.has(node) && distance < minDistance) {
        [minNode, minDistance] = [node, distance]
      }
    }
    return minNode
  }
  // 从起点head出发
  let minNode = getMinNode(dMap, set)
  while (minNode) {
    const distance = dMap.get(minNode)
    // 考察所有边
    for (edge of minNode.edges) {
      // 边对应的到达节点
      const tNode = edge.to
      // 没记录时，新增
      if (!dMap.has(tNode)) {
        dMap.set(tNode, distance + edge.weight)
      }
      // 更新
      dMap.set(tNode, Math.min(dMap.get(tNode), distance + edge.weight))
    }
    // 标记
    set.add(minNode)
    minNode = getMinNode(dMap, set)
  }
  return dMap
}

数据结构应用 ​

leetcode
  1. 407. 接雨水 II