数据结构-图-最小生成树

最小生成树

最小生成树通过每个顶点相连接的所有边，取当前最小的一条边，判断两个顶点是否都被记录过，如果是，则跳过，否则，继续使用另一个顶点重复上述过程。期间使用最小堆模拟优先队列，每次拿到最小的那条边，放入到最小生成树中，把生成树中的每条边累加就得到生成树所有权值。

代码实现

const MinHeap = require('./min-heap');

class LazyPrim {
  constructor(g) {
    this.g = g; // 图的引用
    this.marked = new Array(g.V()).fill(false); // 标志数组，表示每个顶点是否被访问过
    this.mst = []; // 最小生成树包含的所有边
    this.weight = 0; // 最小生成树的权值
    
    const compare = (parent, child) => {
      return parent && child && parent.weight > child.weight;
    };
    this.pq = new MinHeap(compare); // 最小堆来模拟优先队列
    this.visit(0);

    while (!this.pq.isEmpty()) {
      const e = this.pq.extractMin();

      if (this.marked[e.v] && this.marked[e.w]) continue;
      this.mst.push(e);

      if (this.marked[e.v]) {
        this.visit(e.w);
      } else {
        this.visit(e.v);
      }
    }
  }

  visit(v) {
    if (this.marked[v]) return;

    this.marked[v] = true;
    for (const e of this.g.adj(v)) {
      if (!this.marked[e.other(v)]) {
        this.pq.insert(e);
      }
    }
  }

  mstEdges() {
    return this.mst;
  }

  mstWeight() {
    for (const item of this.mst) {
      this.weight += item.wt();
    }

    return this.weight;
  }
}

module.exports = LazyPrim;

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG

最小生成树

CATALOG

FEATURED TAGS

FRIENDS