display 生成树

### 生成树算法及其数据结构

#### Prim算法概述
Prim算法用于求解加权无向图中的最小生成树(MST)，即在一个连通图中找到一棵包含所有节点且总权重最小的子树。该过程始于任意选定的一个顶点，逐步加入具有最低成本的新边直至覆盖全部顶点[^2]。

#### 数据结构设计
为了高效实现上述逻辑，采用两种基本的数据结构来表示网络拓扑关系：

- **Node (节点)**
定义`struct Node { int id; }`存储各个独立端点的信息，在实际编码过程中可能还需要附加其他属性比如访问状态标记等辅助字段。

- **Edge (边)**
使用`struct Edge { int from, to, weight; }`描述每条连接两端的具体情况——起点、终点以及它们之间的距离度量值。这些信息对于计算路径长度至关重要[^1]。

#### Python代码实例展示
下面给出一段基于优先队列优化过的Python版本Prim算法源码片段:

import heapq

def prim(graph, start_vertex):
    mst = []
    visited = set([start_vertex])
    edges = [(weight, start_vertex, neighbor) for neighbor, weight in graph[start_vertex].items()]
    
    heapq.heapify(edges)

    while edges:
        weight, u, v = heapq.heappop(edges)
        
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            
            for next_node, w in graph[v].items():
                if next_node not in visited:
                    heapq.heappush(edges, (w, v, next_node))

    return mst

这段程序通过维护一个动态调整大小的小根堆（Min Heap），使得每次都能快速获取当前未处理集合中最短的一条候选边，从而保证了整体时间复杂性的最优性O(E log V)。