算法最小生成树Qt项目 包含prim算法和kruskal算法 其中二者的执行过程可以动态展示 包含报告和源代码
最近在Qt框架下搞了个最小生成树的可视化项目，把Prim和Kruskal这两个经典算法从黑盒子里拽出来晒太阳。这个项目的核心是要让算法执行过程像看动画片一样直观——边选边动，树苗长成大树的过程尽收眼底。
先说说Prim算法的实现。核心在于维护两个阵营：已占领的节点和待攻克的节点。这里用了个取巧的边容器，每次只关注连接两个阵营的最短边：
// 这个结构体专门记录搞对象失败的边（雾） struct TempEdge { int from; int to; float weight; bool operator<(const TempEdge& other) const { return weight > other.weight; // 故意反着来，为了优先队列 } }; // 算法主循环片段 while (!minHeap.empty()) { TempEdge current = minHeap.top(); if (visited[current.to]) { minHeap.pop(); continue; } // 把这条幸运边加入MST全家福 mstEdges.append(current); // 更新占领区域 updateVisited(current.to); // 触发界面重绘信号 emit stepUpdated(); // 这里故意卡个300ms让观众看清楚 QThread::msleep(300); }这里有个骚操作：优先队列用最大堆但是按边的权值升序排列。因为标准库的优先队列默认是最大堆，通过反转比较运算符就能白嫖这个特性。每次弹出堆顶元素时，如果目标节点已经被收编，就直接跳过，避免形成环路。
转头看看Kruskal算法的实现。这货的核心是并查集，用来判断两个节点是不是一伙的。代码里整了个PathFinder类专门干这事：
class PathFinder { QVector<int> parent; public: PathFinder(int size) : parent(size) { for(int i=0; i<size; ++i) parent[i] = i; } // 找祖宗十八代 int find(int x) { while(parent[x] != x) { parent[x] = parent[parent[x]]; // 路径压缩 x = parent[x]; } return x; } // 撮合两个帮派 bool unite(int x, int y) { int rootX = find(x); int rootY = find(y); if(rootX == rootY) return false; parent[rootX] = rootY; return true; } };边排序这里有个坑：Qt的qSort对自定义结构不太友好，得先给边容器做个大保健：
qSort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){ return a.weight < b.weight; });可视化部分用QGraphicsScene搭台唱戏。每个算法步骤触发信号，让视图层更新当前选中的边。比如当某条边被临幸时，会变成基佬紫并闪烁三下：
// 在图形项中处理选中状态 void EdgeItem::setState(EdgeState state) { if(state == Selected) { animation = new QPropertyAnimation(this, "color"); animation->setDuration(500); animation->setLoopCount(3); animation->setStartValue(QColor(Qt::darkMagenta)); animation->setEndValue(QColor(Qt::cyan)); animation->start(); } // 其他状态处理... }为了让观众不睡着，算法每走一步都会通过信号槽通知界面线程更新。这里有个细节：算法跑在独立线程，通过跨线程信号触发UI刷新，避免界面假死。
项目结构上，核心代码分三大块：
Algorithms/里蹲着Prim和Kruskal的实现Views/管图形项的绘制和动画Utils/塞着并查集、优先队列这些工具人
测试时发现个邪门bug：当节点数量超过50个时，Kruskal的动画会抽风。后来发现是排序后的边容器被多个线程同时访问，加了个QMutex才镇住场子。
代码仓库里除了源码，还有个20页的报告文档，详细记录了从算法复杂度分析到Qt信号槽的线程安全注意事项。不过说实在的，最实用的还是那个能拖拽节点动态生成拓扑图的演示模式——拿这个去给学妹讲算法，效果拔群。
