邻接矩阵表示法的克鲁斯卡尔算法

### 使用邻接矩阵表示法实现克鲁斯卡尔算法

克鲁斯卡尔算法是一种用于寻找加权无向图最小生成树的有效方法[^1]。通常情况下，该算法通过边列表来操作更为高效；然而，在某些场景下可能需要基于邻接矩阵的实现方式。

#### 邻接矩阵定义
对于给定的一个具有 \(n\) 个顶点的图 \(G=(V,E)\)，其邻接矩阵是一个大小为 \(n \times n\) 的二维数组 `adj_matrix`。如果存在一条连接节点 \(i\) 和节点 \(j\) 权重为 \(w\) 的边，则设置 `adj_matrix[i][j]= w` 并且由于是无向图也应有 `adj_matrix[j][i]= w`; 否则对应位置设为无穷大或特定值（比如0），用来表明两点间不存在直接相连的情况[^4]。

为了适应克鲁斯卡尔算法的需求，还需要额外的数据结构存储所有边的信息以及它们各自的权重。这可以通过遍历整个邻接矩阵并提取有效的边对来完成：

def get_edges_from_adj_matrix(adj_matrix):
    edges = []
    num_vertices = len(adj_matrix)

    for i in range(num_vertices):
        for j in range(i + 1, num_vertices):  # 只需考虑上三角部分即可避免重复计数
            if adj_matrix[i][j] != float('inf'):
                edges.append((i, j, adj_matrix[i][j]))
    
    return sorted(edges, key=lambda item:item[2])  # 对所有的边按照权重升序排列

一旦获得了按权重排序后的边集合之后就可以应用标准版本的克鲁斯卡尔逻辑了——即不断选取当前最轻量级的安全边加入到正在构建中的森林里直到形成一棵完整的树为止。这里需要注意的是要维护一个不相交集数据结构(disjoint-set data structure)以检测循环并管理连通分量之间的合并过程[^2]。

下面给出了一种简化版的具体Python代码片段展示如何利用上述思路结合邻接矩阵来进行克鲁斯卡尔算法的操作:

class DisjointSet:
    def __init__(self, size):
        self.parent = [-1]*size
    
    def find(self, v):
        while self.parent[v]!=-1:v=self.parent[v]
        return v
        
    def union(self,u,v):
        root_u=self.find(u)
        root_v=self.find(v)
        
        if root_u!=root_v:self.parent[root_u]=root_v


def kruskal_with_adj_matrix(adj_matrix):
    dsu=DisjointSet(len(adj_matrix))
    mst=[]

    for u,v,w in get_edges_from_adj_matrix(adj_matrix):
        set_u=dsu.find(u)
        set_v=dsu.find(v)

        if set_u!=set_v:# 如果两个端点不属于同一个子集就安全添加这条边
           mst.append((u,v,w)) 
           dsu.union(set_u,set_v)

    total_weight=sum([weight for _,_,weight in mst])
    print(f'Minimum Spanning Tree Edges:{mst}')
    print(f'Total Weight Of MST Is {total_weight}')

# 假设有如下形式的邻接矩阵作为输入样本测试上面函数的功能
sample_adj_matrix=[
     [float('Inf'), 7 ,5 ],
     [7         ,float('Inf') ,8],
     [5          ,8       ,float('Inf')]
]

kruskal_with_adj_matrix(sample_adj_matrix)

此段程序首先初始化了一个离散集合对象以便于后续处理过程中判断新增入MST的新边是否会构成回路问题。接着调用了之前提到过的辅助功能获取由原图转换而来的有序边序列，并逐条考察这些候选者能否被接纳成为最终解的一部分。最后输出所找到的一组满足条件的最佳路径及其累积代价总和。