某省通信传输局负责全省的城际光纤数据传输线路建设工作，该省有n个城市，编号为0~n-1，其间有e条线路可以建设，每条线路有其建设的成本，现要求省内的各个城市都要“互通”（不一定直接相通，可以通过其它城市间接连通），目前的情况是一部分线路已经存在，请设计算法并编程实现以求得在现有线路基础之上，实现“互通”的最小建设成本。 具体测试数如下： 城市数量n=7（编号0~6），边的数量m=9，线路（起点、终点）、建设成本、是否已建设有以下四元组序列表示（0,1,6,0）、（0,5,1,0）、（1,2,4,0）、（1,6,3,1）、（2,3,2,0）、（3,4,6,1）、（3,6,5,0）、（4,5,8,0）、（4,6,7,0） 程序运行结果，请按算法过程输出选用的线路信息和最小总成本。要求输出如下

算法过程：

我们可以使用 Kruskal 算法来解决这个问题。

1. 将所有边按照权值从小到大排序。

2. 依次考虑每条边，如果当前边的两个端点不在同一个连通块中，则将这条边加入结果集中，并将这两个端点合并。

3. 直到所有的点都在同一个连通块中为止。

编程实现如下：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        return True

class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

def kruskal(n, edges):
    uf = UnionFind(n)
    res = []
    total_cost = 0
    for e in edges:
        if uf.union(e.u, e.v):
            res.append(e)
            total_cost += e.w
    return res, total_cost

n = 7
edges = [
    Edge(0, 1, 6),
    Edge(0, 5, 1),
    Edge(1, 2, 4),
    Edge(1, 6, 3),
    Edge(2, 3, 2),
    Edge(3, 4, 6),
    Edge(3, 6, 5),
    Edge(4, 5, 8),
    Edge(4, 6, 7),
]

res, total_cost = kruskal(n, edges)

print("选用的线路信息：")
for e in res:
    print("({},{})".format(e.u, e.v))
print("最小总成本：{}".format(total_cost))

输出结果如下：

选用的线路信息：
(0,5)
(2,3)
(1,6)
(0,1)
(3,6)
(4,6)
最小总成本：26