图✅

图的遍历

答案

图的遍历主要有两种方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

function dfs (graph, start) {
  const visited = new Set()
  function traverse (node) {
    if (visited.has(node)) return
    visited.add(node)
    console.log(node)
    for (const neighbor of graph[node]) {
      traverse(neighbor)
    }
  }
  traverse(start)
}

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
}

dfs(graph, 'A') // A B D E F C

广度优先搜索（BFS）

function bfs (graph, start) {
  const visited = new Set()
  const queue = [start]

  while (queue.length > 0) {
    const node = queue.shift()
    if (visited.has(node)) continue
    visited.add(node)
    console.log(node)
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor)
      }
    }
  }
}

bfs(graph, 'A') // A B C D E F

最短路径算法

给定一个加权有向图，找到从起点到终点的最短路径。

const graph = {
  A: { B: 1, C: 4 },
  B: { C: 2, D: 5 },
  C: { D: 1 },
  D: {}
}

function dijkstra (graph, start) {

}

答案

function dijkstra (graph, start) {
  const distances = {}
  const visited = new Set()
  const pq = new PriorityQueue((a, b) => a[1] < b[1])

  for (const node in graph) {
    distances[node] = Infinity
  }
  distances[start] = 0
  pq.enqueue([start, 0])

  while (!pq.isEmpty()) {
    const [current, currentDist] = pq.dequeue()
    if (visited.has(current)) continue
    visited.add(current)

    for (const neighbor in graph[current]) {
      const newDist = currentDist + graph[current][neighbor]
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist
        pq.enqueue([neighbor, newDist])
      }
    }
  }

  return distances
}

class PriorityQueue {
  constructor (comparator = (a, b) => a > b) {
    this._heap = []
    this._comparator = comparator
  }

  size () {
    return this._heap.length
  }

  isEmpty () {
    return this.size() === 0
  }

  peek () {
    return this._heap[0]
  }

  enqueue (value) {
    this._heap.push(value)
    this._siftUp()
  }

  dequeue () {
    const poppedValue = this.peek()
    const bottom = this.size() - 1
    if (bottom > 0) {
      this._swap(0, bottom)
    }
    this._heap.pop()
    this._siftDown()
    return poppedValue
  }

  _siftUp () {
    let nodeIdx = this.size() - 1
    while (nodeIdx > 0 && this._comparator(this._heap[nodeIdx], this._heap[this._parent(nodeIdx)])) {
      this._swap(nodeIdx, this._parent(nodeIdx))
      nodeIdx = this._parent(nodeIdx)
    }
  }

  _siftDown () {
    let nodeIdx = 0
    while (
      (this._left(nodeIdx) < this.size() && this._comparator(this._heap[this._left(nodeIdx)], this._heap[nodeIdx])) ||
      (this._right(nodeIdx) < this.size() && this._comparator(this._heap[this._right(nodeIdx)], this._heap[nodeIdx]))
    ) {
      const greaterChildIdx =
        this._right(nodeIdx) < this.size() && this._comparator(this._heap[this._right(nodeIdx)], this._heap[this._left(nodeIdx)])
          ? this._right(nodeIdx)
          : this._left(nodeIdx)
      this._swap(nodeIdx, greaterChildIdx)
      nodeIdx = greaterChildIdx
    }
  }

  _parent (idx) {
    return ((idx + 1) >>> 1) - 1
  }

  _left (idx) {
    return (idx << 1) + 1
  }

  _right (idx) {
    return (idx + 1) << 1
  }

  _swap (i, j) {
    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]
  }
}

module.exports = dijkstra

Tests

最小生成树

给定一个加权无向图，找到其最小生成树。

const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 }
}

function kruskal (graph) {

}

答案

function kruskal (graph) {
  const edges = []
  for (const node in graph) {
    for (const neighbor in graph[node]) {
      edges.push([node, neighbor, graph[node][neighbor]])
    }
  }
  edges.sort((a, b) => a[2] - b[2])

  const parent = {}
  const rank = {}
  for (const node in graph) {
    parent[node] = node
    rank[node] = 0
  }

  function find (node) {
    if (parent[node] !== node) {
      parent[node] = find(parent[node])
    }
    return parent[node]
  }

  function union (node1, node2) {
    const root1 = find(node1)
    const root2 = find(node2)
    if (root1 !== root2) {
      if (rank[root1] > rank[root2]) {
        parent[root2] = root1
      } else if (rank[root1] < rank[root2]) {
        parent[root1] = root2
      } else {
        parent[root2] = root1
        rank[root1]++
      }
    }
  }

  const mst = []
  for (const [node1, node2, weight] of edges) {
    if (find(node1) !== find(node2)) {
      union(node1, node2)
      mst.push([node1, node2, weight])
    }
  }

  return mst
}

module.exports = kruskal

Tests

拓扑排序

给定一个有向无环图，找到其拓扑排序。

const graph = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['D'],
  D: []
}

function topologicalSort (graph) {

}

答案

function topologicalSort (graph) {
  const visited = new Set()
  const stack = []
  function dfs (node) {
    if (visited.has(node)) return
    visited.add(node)
    for (const neighbor of graph[node]) {
      dfs(neighbor)
    }
    stack.push(node)
  }
  for (const node in graph) {
    dfs(node)
  }
  return stack.reverse()
}

module.exports = topologicalSort

Tests