kruskal

基于klonenet平台的kruskal算法实现

kruskal算法是是应用于求出最小生成树问题的经典算法。该次作业要求如下：
1、使用python获取给定json文件中编制好的网络信息，包括主机mac地址、交换机dpid、带宽、传输延时等；
2、选取适宜的数据结构储存读取到的网络信息；
3、根据数据结构实现kruskal算法，获取最小生成树路径。

最小生成树

对于一个连通无向图G=(V, E)，我们希望找到一种连接方式使得所有结点能够连接起来并且拥有最小的边权重之和。如图中红线就是该网络的最小生成树

使用贪心策略的解决办法

知晓贪心的读者应该已经大概知道如何去找到这个最小生成树了，接下来展示课本《算法导论》中提炼的伪码实现：
A = ∅
while A does not from the spanning tree
find an edge(u, v) that is safe for A
A = A∪{(u, v)}
return A
其中，每次循环A都是某棵最小生成树的子集；而对于A安全的边指的是该条边加入到集合A后不会破坏A的循环不变式。

kruskal算法

kruskal算法便是上文伪代码的一种细化方式，我们很容易地看到贪心策略的解决办法其难点在于安全边的确定。kruskal算法的解决方式是每次都选取边权最小的边来加入集合A。伪代码如下：
A = ∅
for each vertex v ∈ G.V
MAKE-SET(v)
sort the edges of G.E into nondecreasing order by weight w
for each edges e(u, v) in G.E
if FIND-SET(u) ≠ FIND-SET(v)
A = A∪{(u, v)}
UNION(u, v)
return A
也就是说，kruskal算法将图的每一个结点都独立为一个集合（MAKE-SET），再根据边权由小到大进行排序，遍历边的集合时判断边的两个顶点是否属于同一集合（同一棵树），不是则将这条边加入集合A，再将u，v所在集合合并（UNION）。如若u，v顶点属于同一集合依旧将(u,v)边加入A的话那A中集合就会成环，最后结果就不是最小生成树了。