所谓一个 带权图 的最小生成树，就是原图中边的权值最小的生成树 ，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。
边多的图用prim，边少的图用kruskal
时间复杂度总结：
prim o(e+vlogv), 主要是优先队列top v次，每次log(v), 然后边遍历总计2e.
kruskal o(eloge), 主要是边的排序耗时上。
Prim
prim算法的核心信仰是：从已知扩散寻找最小。它的实现方式和Dijkstra算法相似但稍微有所区别，Dijkstra是求单源最短路径。而每计算一个点需要对这个点从新更新距离。而prim甚至不用更新距离。直接找已知点的邻边最小加入即可！ 对于具体算法具体步骤，大致为：
- 寻找图中任意点，以它为起点，它的所有边V加入集合(优先队列)q1,设置一个boolean数组bool[]标记该位置已经确定。
- 从集合q1找到距离最小的那个边v1并判断边另一点p是否被标记(访问)，如果p被标记说明已经确定那么跳过，如果未被标(访问)记那么标记该点p,并且与p相连的未知点(未被标记)构成的边加入集合q1，边v1(可以进行计算距离之类，该边构成最小生成树) .
- 重复1，2直到q1为空，构成最小生成树 ！
时间复杂度：对于邻接矩阵，O(n2)； 对于邻接链表，O((n+e)logn)
Prim’s algorithm
Step 1: x 属于 V, Let A = {x}, B = V - {x}
Step 2: Select (u, v) E, u A, v B such that (u, v) has the smallest weight between A and B
Step 3: (u, v) is in the tree. A = A {v}, B = B - {v}
Step 4: If B = , stop; otherwise, go to Step 2.
time complexity:
O(n2), n = |V|.
public Prim(List<int[]>[] graph) {
this.graph = graph;
this.pq = new PriorityQueue<>((a, b) -> {
// 按照边的权重从小到大排序
return a[2] - b[2];
});
// 图中有 n 个节点
int n = graph.length;
this.inMST = new boolean[n];
// 随便从一个点开始切分都可以，我们不妨从节点 0 开始
inMST[0] = true;
cut(0);
// 不断进行切分，向最小生成树中添加边
while (!pq.isEmpty()) {
int[] edge = pq.poll();
int to = edge[1];
int weight = edge[2];
if (inMST[to]) {
// 节点 to 已经在最小生成树中，跳过
// 否则这条边会产生环
continue;
}
// 将边 edge 加入最小生成树
weightSum += weight;
inMST[to] = true;
// 节点 to 加入后，进行新一轮切分，会产生更多横切边
cut(to);
}
}
// 将 s 的横切边加入优先队列
private void cut(int s) {
// 遍历 s 的邻边
for (int[] edge : graph[s]) {
int to = edge[1];
if (inMST[to]) {
// 相邻接点 to 已经在最小生成树中，跳过
// 否则这条边会产生环
continue;
}
// 加入横切边队列
pq.offer(edge);
}
}
# coding:UTF-8
def prim(graph, vertex_num):
INF = 1 << 10
visit = [False] * vertex_num
dist = [INF] * vertex_num
#preIndex = [0] * vertex_num
#对所有的顶点进行循环，首先是确定头结点
#找到当前无向图的最小生成树
for i in range(vertex_num):
minDist = INF + 1
nextIndex = -1
#第一次循环时，nextIndex就是头结点
#所以要把minDIst加上1，之后这个循环
#的功能是找到基于当前i，邻接矩阵中i行到哪一行距离最小的那个位置作为下一个结点，当然前提是那个结点没有去过
for j in range(vertex_num):
if dist[j] < minDist and not visit[j]:
minDist = dist[j]
nextIndex = j
print (nextIndex)
visit[nextIndex] = True
#由于前面已经找到了下一个结点了，现在就要构建再下一个结点的dist矩阵了，这就要看当前这个nextIndex这一行了
for j in range(vertex_num):
if dist[j] > graph[nextIndex][j] and not visit[j]:
dist[j] = graph[nextIndex][j]
#preIndex[j] = nextIndex
return dist, #preIndex
_ = 1 << 10
graph = [
[0, 6, 3, _, _, _],
[6, 0, 2, 5, _, _],
[3, 2, 0, 3, 4, _],
[_, 5, 3, 0, 2, 3],
[_, _, 4, 2, 0, 5],
[_, _, _, 3, 5, 0],
]
if __name__ == '__main__':
prim(graph, 6)
Kruskal
百度百科定义的基本思想：
先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
简而言之，Kruskal算法进行调度的单位是边,它的信仰为:所有边能小则小，算法的实现方面和并查集(不相交集合)很像，要用到并查集判断两点是否在同一集合。
而算法的具体步骤为：
- 将边(以及2顶点)的对象依次加入集合(优先队列)q1中。初始所有点相互独立。
- 取出当前q1最小边，判断边的两点是否联通。
- 如果联通，跳过，如果不连通，则使用union（并查集合并）将两个顶点合并。这条边被使用(可以储存或者计算数值)。
- 重复2，3操作直到集合（优先队列）q1为空。此时被选择的边构成最小生成树。
Kruskal()
{
T = ;
for each v V
MakeSet(v);
sort E by increasing edge weight w
for each (u,v) E (in sorted order)
if FindSet(u) FindSet(v) //如果不在同一集合中,则不会产生回路
T = T U {u,v};
Union(FindSet(u), FindSet(v));//合并两个集合
}
What will affect the running time?
1 Sort
O(V) MakeSet() calls
O(E) FindSet() calls
O(V) Union() calls
邻接表+小堆实现: O(n + m logn)
template <class T>
struct EdgeInfo
{
T beginVex, endVex;
int cost;
};
int Find(int Father[],int v)
{
int t;
t = v;
while (Father[t] > 0)
t = Father[t];
return(t);
}
template <class T>
void OrderEdge(Graph<T> G, EdgeInfo<T> edge[])
{
int i,j,n = G.NumberOfVertices;
int k = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (G.getWeight(i,j)) {
edge[k].beginVex=i;
edge[k].endVex=j;
edge[k].cost= G.getWeight(i,j);
k++;
}
// sort
int temp;
for (i =0; i < k; i++)
for (j = k-1; j >= i; j--) {
if (edge[j+1].cost < edge[j].cost) {
temp = edge[j].cost;
edge[j].cost = edge[j+1].cost;
edge[j+1].cost = temp;
}
}
}
template <class T>
void MiniSpanTreeKruskal(Graph<T> G, EdgeInfo<T> edge[])
{
int Father[k];
int vf1, vf2;
for (i = 0; i < k; i ++) Father[i] = 0;
for (i = 0; i < k; i ++)
{
vf1 = Find(Father,edge[i].beginVex);
vf2 = Find(Father,edge[i].endVex);
if (vf1 != vf2)
{ Father[vf2] = vf1;
cout << Edges[i].beginVex << Edges[i].endVex; // output
}
}
}