Minimum Spanning Tree

最小生成树就是在在一个边带权重的图里一条联通所有图里结点且整个权重最小的树型结构，也就是说MST没有环，且所有结点在这个MST里全部联通，而且囊括图里所有结点，这里给一张图参考一下

MST的生成算法有两种，一种是Prim算法，基本上和Dijkstra算法是一样的实现，然后还有一种Kruskal算法，这里先用Kruskal算法实现这道题，K算法说起来也很简单，其实就是一种贪心算法在图上面的实现，大体分三步

• 对所有图结点进行遍历，逐个生成一个新的disjoint set
• 对所有边进行排序
• 对排序之后的边进行union find操作

然后对于排序，此题里的结点label都是字符串，所以可以先针对带权边，字符串实现一个comparator，然后利用这个comparator进行排序，同时使用一个哈希表记录结点的label和对应的disjoint set的下标，下面是代码

"""
Definition for a Connection
class Connection:

    def __init__(self, city1, city2, cost):
        self.city1, self.city2, self.cost = city1, city2, cost
"""

def comparator(A, B):
    if A.cost != B.cost:                      # 带权边的比较最优先
        return A.cost - B.cost

    if A.city1 != B.city1:                    # 其次比较起始城市的字符串大小
        if A.city1 < B.city1:
            return -1
        else:
            return 1

    if A.city2 == B.city2:                    # 再比较终点城市的大小
        return 0
    elif A.city2 < B.city2:
        return -1
    else:
        return 1

class Solution:
    # @param {Connection[]} connections given a list of connections
    # include two cities and cost
    # @return {Connection[]} a list of connections from results
    def lowestCost(self, connections):
        # Write your code here
        store = {}
        n = 0
        connections.sort(cmp = comparator)
        res = []

        for connection in connections:                    # 给对应的结点字符串赋一个disjoint set的下标
            if connection.city1 not in store:
                store[connection.city1] = n
                n += 1
            if connection.city2 not in store:
                store[connection.city2] = n
                n += 1

        parent = [-1] * n
        for connection in connections:
            a = self.find(store[connection.city1], parent)
            b = self.find(store[connection.city2], parent)
            if a != b:
                parent[a] = b
                res.append(connection)

        return res if len(res) == n - 1 else []

    def find(self, node, parent):
        if parent[node] == -1:
            return node
        parent[node] = self.find(parent[node], parent)
        return parent[node]