最小生成树

首先, 什么是最小生成树
图论基础

Prim算法(普利姆算法)

采用prim算法解决生成树问题

  1. 假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U,TE初值均为空集。
  2. 首先从V中任取一个顶点（假定取v1），将它并入U中，此时U={v1}，然后只要U是V的真子集(U∈V)，就从那些一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短边，设为(vi ,vj ),其中vi ∈U, vj ∈V-U，并把该边(vi , vj )和顶点vj 分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后得到最小生成树。
关键问题

每次如何从连接T 中和T 外顶点的所有边中，找到一条最短的

  1. 如果用邻接矩阵存放图，而且选取最短边的时候遍历所有点进行选取，则总时间复杂度为O(V 2 ), V 为顶点个数
  2. 用邻接表存放图,并使用堆来选取最短边，则总时间复杂度为O(ElogV)

特点 : 不加堆的Prim 算法适用于密集图，加堆的适用于稀疏图

Krustral算法(克鲁斯卡尔算法)

  1. 假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U=V, TE初值为空。
  2. 将图G中的边按权值从小到大依次选取，若选取的边使生成树不形成回路，则把它并入TE中，若形成回路则将其舍弃，直到TE中包含N-1条边为止，此时T为最小生成树。

特点: 适用于稀疏图

关键问题
  • 如何判断欲加入的一条边是否与生成树中边构成回路。
    1. 将各顶点划分为所属集合的方法来解决，每个集合的表示一个无回路的子集。开始时边集为空，N个顶点分属N个集合，每个集合只有一个顶点，表示顶点之间互不连通。
    2. 当从边集中按顺序选取一条边时，若它的两个端点分属于不同的集合，则表明此边连通了两个不同的部分，因每个部分连通无回路，故连通后仍不会产生回路，此边保留，同时把相应两个集合合并

经典最小生成树题目畅通工程
prim算法和kruskal算法比较

  1. Kruskal:
    • 将所有边从小到大加入，在此过程中判断是否构成回路
    • 使用数据结构：并查集
    • 时间复杂度：O(ElogE)
    • 适用于稀疏图
  2. Prim:
    • 从任一节点出发，不断扩展
    • 使用数据结构：堆
    • 时间复杂度：O(ElogV) 或 O(VlogV+E)(斐波那契堆）
    • 适用于密集图
    • 若不用堆则时间复杂度为O(V2 )

最小生成树一·Prim算法
生成树二·Kruscal算法

最小生成树扩展

最小度数限制生成树