Kruskal常用的检查是否成环的数据结构是UnionFind(并查集)，UnionFind有个操作，一个是Find检查元素所在集合的编号，Union将两个元素合并成一个集合。

KRUSKAL(g)
  let edges be all the edges of g
  sort(edges)
  let uf be new UnionFind
  let e = 0
  let i = 0
  let result be new Array
  while e < edges.length()
    let edge = edges[i]
    i = i + 1
    if uf.find(edge.src) != uf.find(edge.des)
      result.append(edge)
      e = e + 1
      uf.union(edge.src,edge.des)
  end
  return result

V表示顶点的个数，E表示边的个数，排序E个边加上E次UnionFind操作

时间复杂度:O(Elog2E+Elog2V)

• Prim

有了推论1，Prim算法的正确性理解起来就很简单了，一直只对最小生成树子集进行切割，然后选择出最小生成树子集与其他连通分量的最小代价边就OK了。Prim算法就是一直选择最小生成树子集与其他顶点连接的最小代价边。

Prim算法维持这样一个最小堆，存储最小生成树子集以外的顶点，与最小生成树子集临接的顶点的权重是其临接边的值，其余的最小堆中的顶点权重都是无穷。Prim算法初始将起始顶点在最小堆中的权重置为0，其余的顶点置为无穷。然后从最小堆中一直取权重最小的顶点，即选择最小代价边加入最小生成树，如果取出的顶点的临接顶点不在最小生成树中，且这个临接顶点在最小堆中的权重比边大，则更新临接顶点在最小堆的权重，直到从最小堆中取出所有的顶点，就得到了一颗最小生成树。

伪代码：
PRIM(g,s)
  let heap be new MinHeap
  let result be new Array
  for i from 1 to the number of vertex in g
    let vertex be new Vertex(i)
    vertex.weight = INT_MAX
    heap.insert(vertex)
  end
  heap.decrease(s,0)
  while heap.empty() == false
    vertex v = heap.top()
    for u equal to every vertex adjacent to v
      if heap.isNotInHeap(u) and v->u < heap.getWeightOfNode(u)
        result[u] = v
        heap.decrease(u,v->u)
    end  
  end
  return result

V表示顶点的个数，E表示边的个数，对V个顶点和E条边进行decrease操作

时间复杂度:O(Elog2V+Vlog2V)

• Boruvka

Kruskal是根据所有边中最小代价边的一端的连通分量分割，Prim根据最小生成子树的子集分割，Boruvka根据所有的连通分量分割，实际上都是基于推论1。Boruvka算法将所有连通分量与其他连通分量的最小代价边选择出来，然后将这些边中未加入最小生成树子集的加进去，一直到生成最小生成树。

Boruvka算法同样使用了UnionFind去记录连通分量，用cheapest数组记录连通分量与其他连通分量连接的最小代价边的编号。

伪代码：
Boruvka(g)
  let uf be new UnionFind
  let cheapest be new Array
  let edges be all the edge of g
  let numTree = the number of vertex in g
  let result be new Array
  for i from 1 to number of vertex in g
    cheapest[i] = -1
  end
  while numTree > 0
    for i from 1 to the number of edge in g
      let set1 = uf.find(edges[i].src)
      let set2 = uf.find(edges[i].des)
      if set1 == set2
        continue
      if cheapest[se1] == -1 or edges[cheapest[set1]].weight > edges[i].weight
        cheapest[set1] = i
      if cheapest[set2] == -1 or edges[cheapest[set2]].weight > edges[i].weight
        cheapest[set2] = i
    end
    for i from 1 to the number of vertex in g
      if cheapest[i] != -1
        let set1 = uf.find(edges[cheapest[i]].src)
        let set2 = uf.find(edges[cheapest[i]].des)
        if set1 == set2
          continue
        result[edges[cheapest[i]].src] = edges[cheapest[i]].des 
        uf.union(set1,set2)
        numTree = numTree - 1
    end
  end
  return result

时间复杂度:O(Elog2V)，V表示顶点的个数，E表示边的个数

单源最短路径(Single-Source-Shortest-Paths)

给出一张连通、有向图，找出一个顶点s到其他所有顶点的最短路径。可以看到，如果图中存在负环，不存在最短路径。因为存在负环就可以无限循环负环得到更短的路径。

看通用的算法之前，同样要讨论一下问题的性质。

假设，存在一条顶点s到顶点v的最短路径，i、j为路径上的两个顶点。那么在这条s到v最短路径上，i到j的路径是否是i到j的最短路径？是的，如果存在i到j的更短路径，就等价于存在一条s到v的更短路径，这与假设不符。也就是说，如果存在一条从s到v的最短路径，这条路径上任意两个顶点的路径都是这两个顶点的最短路径。那么，这个问题就具有动态规划的状态转移特征。

解决此问题的朴素想法就是求出所有顶点s到顶点v的路径，然后取最小值。那么要是实现这个步骤，就要为v点存储一个估计值d，并设起始为无穷，如果有到达v的路径小于这个估计值，更新这个估计值，并且记录v的现阶段最小路径。这步操作叫做松弛操作(relax)。假设u为小于估计值路径上的上个顶点。

RELAX(u,v,result)
  if v.d > u.d + u->v
    v.d = u.d + u->v
    result[v] = u