邻接表必须用new动态分配Edge节点并链式管理，避免vector重分配导致指针失效；Prim需用索引+键值分离的优先队列配合懒删除；Kruskal应采用数组索引版并查集；所有Edge内存须贯穿MST全程，结束后统一释放。
用指针管理图结构时，邻接表节点必须动态分配
直接在栈上定义 Node 数组或用 std::vector<node></node> 存邻接表，会导致边指针悬空或内存重复释放。最小生成树（如 Prim）需频繁插入/删除边，且图规模未知，必须用 new 分配每个 Edge 节点，并由顶点指针链式管理。
常见错误：用 vector<edge> edges</edge> 存所有边，再让顶点指向其中元素——vector 重分配时指针全失效；或忘记 delete 导致内存泄漏。
实操建议：
- 定义
struct Edge { int to; int weight; Edge* next; };，next指向下一条邻接边 - 顶点数组声明为
Edge** head;（即Edge* head[n]），每个head[i]指向以i为起点的边链表头 - 添加边时用
new Edge{to, w, head[from]}，再赋值head[from] = new_edge - 析构时逐个遍历每条链表，
delete每个Edge，最后delete[] head
Prim 算法中优先队列不能存裸指针，要用索引+键值分离
priority_queue<edge vector>, cmp></edge> 听起来直接，但实际不可行：比较函数依赖 weight，而 Edge* 在堆中地址无序，且插入后边节点可能被删，指针变野指针。
立即学习“C++免费学习笔记（深入）”；
正确做法是用索引代替指针，把“当前到某点的最短边权”和“该点编号”分开维护：
- 声明
vector<int> minWeight(n, INT_MAX)</int>和vector<bool> inMST(n, false)</bool> - 优先队列存
pair<int int></int>（权重，顶点下标），用greater小顶堆 - 每次取堆顶时先检查
inMST[to]是否已加入，避免重复处理（lazy deletion） - 更新邻居时只改
minWeight[v]并 push 新 pair，不修改已有堆中元素
Kruskal 需要指针版并查集，但 parent 数组用索引更安全
有人试图写 struct Node { Node* parent; }; 实现并查集，看似面向对象，实则增加间接访问开销且易出错：路径压缩时 parent 指针可能指向已释放内存，find 返回的指针若未缓存会重复解引用。
更可靠的做法是回归数组索引语义：
- 声明
vector<int> parent(n)</int>，parent[i] == i表示根 - 用
int find(int x)返回根下标，内部做路径压缩（parent[x] = find(parent[x])） - 合并时比较根下标，小索引作大索引的父（或按秩合并）
- 边集合仍可用
vector<edge></edge>存指针，但排序和 union-find 过程完全不依赖边指针生命周期
delete 不及时会导致 Prim 中堆里出现过期边
即使用了 lazy deletion，如果边节点本身在算法中途被 delete（比如动态删边优化），而堆里还存着指向它的 Edge*，后续解引用就崩溃。所以边内存应贯穿整个 MST 计算周期，直到结果输出完毕再统一释放。
关键约束：
- 所有
Edge*只在图构建完成后分配，MST 完成前禁止delete - 若需支持多次调用 MST，应在类成员中封装
clear()方法，按链表顺序逐个delete，再delete[] head - 用智能指针反而碍事：
shared_ptr<edge></edge>会因环引用（A→B，B→A）导致无法释放；unique_ptr无法满足邻接表的多指针共享需求
真正难的不是写对算法逻辑，而是让指针的生存期严格匹配图结构的使用边界——少一次 new 或多一次 delete，都会在某个稀疏图或大数据量下突然崩掉。
