最小生成树

加权图是一种为每条边关联一个权值或是成本的图模型。在一副航空图中国呢，边表示航线，权值可以表示距离或者费用。自然人们最感兴趣的就是如何将成本最小化。

定义：图的生成树是它的一棵含有其所有顶点的无环连通子图。一副加权无向图的**最小生成树（MST）**是它的一棵权值最小的生成树

一些约定

• 只考虑连通图
• 边的权重不一定表示距离，也可能是时间或者费用（特意说明这点主要是让大家不要通过几何来理解图
• 边的权重可能是0或者负数
• 所有边的权重都不相同。如果不同边的权重可以相同，那么最小生成树就可能不唯一了

切分定理

将加权图中的所有顶点分为两个集合、检查横跨两个集合的所有边并识别哪条边应属于图的最小生成树。如下图所示，将一幅图切分成两个集合，两个集合相连的边称为横切边，这个些横切边中权重最小的一定属于图的最小生成树，这就是切分定理。

切分定理是解决最小生成树问题的所有算法的基础，这些都是一种贪心算法的特殊情况：使用切分定理找到最小生成树的一条边，不断重复知道找到最小生成树的所有边。

加权无向图的数据类型

加权边：

class Edge {
  private v: number
  private w: number
  private weight: number

  constructor(v: number, w: number, weight: number) {
    this.v = v
    this.w = w
    this.weight = weight
  }

  public getWeight() {
    return this.weight
  }

  public either() {
    return this.v
  }

  public other(vertex: number) {
    if (vertex === this.v) {
      return this.w
    } else if (vertex === this.w) {
      return this.v
    } else {
      throw 'Inconsistent edge'
    }
  }
}

加权无向图：

// v, w, weight
export type TEdge = [number, number, number]

export type TGraphData = {
  V: number
  edges: TEdge[]
}

export class EdgeWightedGraph {
  private V: number
  private E: number
  private adj: Edge[][]

  constructor(data: TGraphData) {
    this.V = data.V
    this.E = 0
    this.adj = []

    data.edges.forEach(([v, w, weight]) => this.addEdge(new Edge(v, w, weight)))
  }

  public addEdge(e: Edge) {
    const v = e.either()
    const w = e.other(v)
    this.adj[v] = this.adj[v] || []
    this.adj[w] = this.adj[w] || []
    this.adj[v].push(e)
    this.adj[w].push(e)
    this.E++
  }

  public adjOf(v: number) {
    return this.adj[v]
  }

  public getV() {
    return this.V
  }

  public getE() {
    return this.E
  }

  public getEdges() {
    return this.adj.flat();
  }
}

总体而言，跟之前的Graph类型差不多，只是把邻接表里的元素类型换成了Edge。

Prim算法

测试图：

对应的数据：

const data: TGraphData = {
  V: 8,
  edges: [
    [4, 5, 0.35],
    [4, 7, 0.37],
    [5, 7, 0.28],
    [0, 7, 0.16],
    [1, 5, 0.32],
    [0, 4, 0.38],
    [2, 3, 0.17],
    [1, 7, 0.19],
    [0, 2, 0.26],
    [1, 2, 0.36],
    [1, 3, 0.29],
    [2, 7, 0.34],
    [6, 2, 0.4],
    [3, 6, 0.52],
    [6, 0, 0.58],
    [6, 4, 0.93],
  ],
}

Prim算法的延时实现：

class LazyPrimMST {
  private marked: boolean[] = []
  private mst: Edge[] = []
  private pq: MinPQ = new MinPQ()

  constructor(g: EdgeWightedGraph) {
    this.visit(g, 0);
    while (!this.pq.isEmpty()) {
      const e = this.pq.delMin();
      const v = e.either();
      const w = e.other(v);
      if (this.marked[v] && this.marked[w]) continue;
      this.mst.push(e);
      if (!this.marked[v]) this.visit(g, v);
      if (!this.marked[w]) this.visit(g, w);
    }
  }

  // 标记一个点v，扫描v的邻接点，将被没有被标记的邻接点的边加入到pq中
  // 而其余的边其实就是失效的边，之后也不会再用到了
  private visit(g: EdgeWightedGraph, v: number) {
    this.marked[v] = true
    g.adjOf(v).forEach((e) => {
      if (!this.marked[e.other(v)]) {
        this.pq.insert(e)
      }
    })
  }

  public getEdges() {
    return this.mst;
  }
}

MinPQ为最小列队，但是这里懒得去从0开始实现了，只是简单的实现了其接口，是一个假的最小队列，whatever ……

正所谓贪心算法，LazyPrimMST每次访问一个点就会一直朝着权重最小路径走下去，直到发现对面的点被访问过了，也就是走到头了。然后拿出最小队列里最小的边继续这个过程。

const main = () => {
  const g = new EdgeWightedGraph(data);
  const mst = new LazyPrimMST(g);
  
  mst.getEdges().forEach(e => {
    const v = e.either();
    const w = e.other(v);
    const weight = e.getWeight();
    console.log(`${v}-${w} ${weight}`);
  });
}

/*
0-7 0.16
1-7 0.19
0-2 0.26
2-3 0.17
5-7 0.28
4-5 0.35
6-2 0.4
*/

Prim算法的即时实现：

上面的延时实现把所有边都丢到了最小队列里，但是其实有很多边是用不到的，也就是那些失效的边，实际上只要保存到每个顶点的最小权重的那条边就可以了。这就是即时实现要做，书上用了个索引最小列队，我也懒得实现了，和上面一样只是实现了下接口。main函数同上。

class PrimMST {
  private edgeTo: Edge[] = []  // 保存到每个顶点的权重最小路径
  private distTo: number[] = []  // 保存到每个顶点的权重最小路径的权重 distTo[w] = edgeTo[w].weight()
  private marked: boolean[] = []
  private pq: IndexMinPQ  // 只保存有效的横切边

  constructor(g: EdgeWightedGraph) {
    for (let v = 0; v < g.getV(); v++) {
      this.distTo[v] = Infinity
    }

    this.pq = new IndexMinPQ(g.getV())

    this.distTo[0] = 0
    this.pq.insert(0, 0)
    while (!this.pq.isEmpty()) {
      this.visit(g, this.pq.delMin())
    }
  }

  private visit(g: EdgeWightedGraph, v: number) {
    this.marked[v] = true
    g.adjOf(v).forEach((e) => {
      const w = e.other(v)
      // this.marked[w]为true，则表示v-w这条路径失效，不做处理，直接略过
      if (!this.marked[w] && e.getWeight() < this.distTo[w]) {
        this.edgeTo[w] = e
        this.distTo[w] = e.getWeight()
        if (this.pq.contains(w)) {
          this.pq.change(w, e.getWeight())
        } else {
          this.pq.insert(w, e.getWeight())
        }
      }
    })
  }

  public getEdges() {
    return this.edgeTo
  }
}

/*
1-7 0.19
0-2 0.26
2-3 0.17
4-5 0.35
5-7 0.28
6-2 0.4
0-7 0.16
*/

Kruskal算法

这个算法就更好理解了，将所有边交给最小队列管理，所有顶点交给union-find管理，每次取得权重最小的一条边，如果这个边的两个顶点在uf中不连通，那么就将他们连通起来，同时该边加入最小生成树中。

class KruskalMST {
  private mst: Edge[];

  constructor(g: EdgeWightedGraph) {
    this.mst = [];
    const pq = new MinPQ(g.getEdges());
    const uf = new UF(g.getV());

    while (!pq.isEmpty() && this.mst.length < g.getV() - 1) {
      const e = pq.delMin();
      const v = e.either();
      const w = e.other(v);
      if (uf.connected(v, w)) continue;
      uf.union(v, w);
      this.mst.push(e);
    }
  }

  public getEdges() {
    return this.mst;
  }
}
/*
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
4-5 0.35
6-2 0.4
*/

该算法的会进行E次connected()和V次union()操作，但是这些成本相比ElogE的总时间的增长数量级可以忽略不计。

本节代码：https://github.com/Yuijam/algorithms-note/tree/main/graph/mst