根据无向图画出最小生成树的画法

### 无向图构建最小生成树的算法方法

#### Prim算法
Prim算法是一种用于寻找加权无向图中的最小生成树的有效贪心算法。此算法通过逐步扩展一棵正在生长的树来工作，每次迭代都会选择一条连接已选顶点集合与未选顶点之间具有最低权重的边加入到当前部分形成的子图中，直至包含了所有的顶点。

初始状态下选取任一顶点作为起点，将其标记为已访问并将它所关联的所有边放入候选列表内。之后，在每一步操作里从未被处理过的边上挑选出拥有最小权重且仅有一个端点位于现有树内的那条边，并把对应的另一个端点也纳入进来成为新的成员[^1]。

import sys
from collections import defaultdict


class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

    # A utility function to find the vertex with minimum distance value,
    # from the set of vertices not yet included in shortest path tree.
    def minKey(self, key, mstSet):

        # Initialize min value
        min_val = sys.maxsize
        min_index = None

        for v in range(self.V):
            if key[v] < min_val and mstSet[v] is False:
                min_val = key[v]
                min_index = v

        return min_index

    # Function to construct and print MST for a graph represented using adjacency matrix representation.
    def primMST(self):

        # Key values used to pick minimum weight edge in cut.
        key = [sys.maxsize] * self.V
        parent = [None] * self.V  # Array to store constructed MST.

        # Make key 0 so that this vertex is picked as first vertex.
        key[0] = 0
        mstSet = [False] * self.V

        parent[0] = -1  # First node is always root of MST.

        for cout in range(self.V):

            u = self.minKey(key, mstSet)

            mstSet[u] = True

            for v in range(self.V):

                if (
                    self.graph[u][v] > 0
                    and mstSet[v] is False
                    and key[v] > self.graph[u][v]
                ):
                    key[v] = self.graph[u][v]
                    parent[v] = u
                    
        result_edges = []
        for i in range(1, self.V):
            result_edges.append((parent[i], i, self.graph[parent[i]][i]))
        
        return result_edges

#### Kruskal算法
Kruskal算法同样是用来查找给定连通、有权重无向图里的最小生成树的一种策略。不同于Prim的是，这种方法并不依赖于特定起始节点的选择而是直接作用在整个图形之上。具体做法是从所有可用边缘当中按照从小至大顺序依次考虑各条边，只要这条边不会造成环路形成就把它添加进最终的结果集中去，直到收集到了足够数量——即等于总定点数目减掉一个单位长度为止[^2]。

为了高效判断是否会构成循环结构，通常会借助并查集数据结构来进行辅助管理各个组件之间的关系变化情况。

def kruskal_mst(edges, n_vertices):
    
    edges.sort(key=lambda x: x[2])  
    parent = list(range(n_vertices))
    rank = [0] * n_vertices
    
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node])
        return parent[node]

    def union(u, v):
        root_u = find(u)
        root_v = find(v)
        if root_u != root_v:
            if rank[root_u] > rank[root_v]:
                parent[root_v] = root_u
            elif rank[root_u] < rank[root_v]:
                parent[root_u] = root_v
            else:
                parent[root_v] = root_u
                rank[root_u] += 1
                
    mst = []

    for edge in edges:
        u, v, w = edge
        
        if find(u) != find(v):            
            mst.append(edge)
            union(u,v)
            
        if len(mst)==n_vertices-1:
            break
            
    return mst