文章目录
  1. 生成树
  2. Prime算法
  3. Kruskal算法

生成树

对于一个无向有权图G，在其连通时，它的生成树就是一个由连接了G所有顶点的边生成的树；而最小生成树就是其所有边的权之和最小的生成树。

对于最小生成树，有两种算法可以求出。

Prime算法

初始：已添加到生成树中的顶点集K，初始只包含图中任一顶点。

循环：将$w=\textrm{argmin}\{c(u,v)|(u,v)\in E, u\in K, v\notin K\}$加入K；

退出：所有顶点均添加到K中；

为求出w，可定义$d(v)=\textrm{min}\{c(u,v)|u\in K\}$，而在每轮$d(v)(v\notin K)$的更新为$d(v)=\textrm{min}\{d(v),c(w,v)\}$，其中w为新加入K中的顶点。

Kruskal算法

每次按照最小的权选择边，并且当所选的边不会使生成树产生环时，将其加入生成树的边TE，生成树的顶点集记为TV。判断环的办法是所选边的两个顶点是否都属于TV。

判断两个顶点是否都属于TV，可使用不相交集；

  • 对两个顶点使用Find运算，若其返回值相等，则表明它们均属于TV(不属于TV的顶点属于其自身，因此只有当它们均属于TV时，它们Find的返回值才会相同)，即加入这条边会使生成树形成环；
  • 找到要加入的边之后，将不在TV中的顶点使用Union运算合并到TV中，并将这条边加入TE。

选择边可通过构建一个最小堆(堆中元素可以是指向边的指针，避免了大量数据的移动)，每次考察堆根节点的边(能加入TE或不能加入TE)后，都将这条边从最小堆中”删除”(事实上只需要移动即可)。