构造最小生成树 村村通

### 解决村村通问题的最小生成树算法应用

#### 背景描述
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。为了实现“畅通工程”，即确保省内任何两个村庄之间可以通过公路连接，并且使得铺设的公路总长度最短，可以采用最小生成树算法来规划最优的道路建设方案[^3]。

#### Prim算法的应用
对于给定的一组村庄及其之间的路径成本，在构建最小生成树的过程中，Prim算法从任选的一个起点出发逐步扩展到其他节点直到覆盖所有的村庄为止。每次迭代过程中都会挑选当前已加入集合内的点所能到达但尚未被访问过的最近邻居作为下一个要添加的新成员；如此这般循环往复直至所有顶点都被囊括进来形成一颗完整的树形结构。这种方法特别适用于稠密图的情况。

import sys

def prim_algorithm(graph, start_vertex):
    n = len(graph)
    key_values = {v: float('inf') for v in range(n)}
    parent = [-1]*n
    mst_set = [False]*n
    
    key_values[start_vertex], parent[start_vertex] = 0, None 

    for _ in range(n-1):
        u = min_key(key_values, mst_set)

        mst_set[u] = True
        
        for v in range(n):
            if graph[u][v]>0 and not mst_set[v]:
                if graph[u][v]<key_values[v]:
                    key_values[v]=graph[u][v]
                    parent[v]=u
                    
    result_edges = []
    
    for i in range(1,n):
        result_edges.append((parent[i],i))
        
    return result_edges


def min_key(keys,mstSet):
    minimum = sys.maxsize
    min_index=-1
    
    for vertex in range(len(mstSet)):
        if keys[vertex]<minimum and not mstSet[vertex]:
            minimum=keys[vertex]
            min_index=vertex
            
    return min_index

#### Kruskal算法的应用
而当面对的是较为稀疏的地图分布时，则更推荐使用Kruskal算法来进行处理。此方法并不拘泥于特定起始位置的选择而是直接着眼于全局视角下的每一对可能构成边的关系之中寻找权重最低者先行纳入考虑范围之内再依照其关联端点是否已经存在于同一棵树下来决定最终能否正式成为新添入的部分之一。随着不断重复这一过程直至所剩未连结部分无法继续组合成新的有效分支则整个运算结束从而获得一张由原始输入派生出来的具有最少累积耗费特性的森林形态——也就是所谓的最小生成树了[^5]。

class DisjointSets(object):

    def __init__(self,size):
        self.parent=[None]*size
        self.rank =[0]*size

    def make_set(self,x):
        self.parent[x]=x
        self.rank[x]=0

    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=self.find(x)
        root_y=self.find(y)

        if root_x !=root_y:

            if self.rank[root_x]>self.rank[root_y]:
                self.parent[root_y]=root_x
                
            elif self.rank[root_x]<self.rank[root_y]:
                self.parent[root_x]=root_y
                
            else :
                self.parent[root_y]=root_x
                self.rank[root_x]+=1



def kruskal_algorithm(edges,v_num):
    edges.sort()
    ds=DisjointSets(v_num)
    res_edge=[]

    for edge in edges:
        weight,u,v=edge
        if ds.find(u)!=ds.find(v):
            res_edge.append(edge)
            ds.union(u,v)


    return res_edge