这几天通过做老师的比赛题，也愈来愈发现自己的不足及和别人的差距，一开始我总是不能正确的找到解题思路。想一个题目哪怕是简单题也得想挺长时间（做题少呗），并且自己掌握的知识并不牢固。
下周就是第十四周了，加油吧。
克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。
具体实现：并查集+最小堆(算了，千万别用优先队列，太费时啊，不如用vector<node> 存储，排一次序，遍历即可。
模板
//一下模板重在思想，小心使用 const int MAX=10000; int pre[MAX]; struct node { int f,t,dis; bool operator<(node A) { return dis>A.dis; } }; priority_queue<node> v; int Find(int x) { return x==pre[x]?x:pre[x]=Find(pre[x]); } void join(int x,int y) { int q,p; p=Find(x); q=Find(y); if(p!=q) pre[p]=q; } void init(int T)//并查集初始化 { for(int i=1;i<=T;++i) pre[i]=i; } int main() { }普利姆算法的核心步骤是：在带权连通图中，从图中某一顶点v开始，此时集合U={v}，重复执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，就找到了这颗最小生成树。
其实，由步骤我们就可以定义查找法则：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边
下面盗图：
首先，确定起始顶点。我以顶点A作为起始点。根据查找法则，与点A相邻的点有点B和点H，比较AB与AH，我们选择点B，如下图。并将点B加入到U中。
继续下一步，此时集合U中有{A,B}两个点，再分别以这两点为起始点，根据查找法则，找到边BC（当有多条边权值相等时，可选任意一条），如下图。并将点C加入到U中。
继续，此时集合U中有{A,B,C}三个点，根据查找法则，我们找到了符合要求的边CI，如下图。并将点I加入到U中。
继续，此时集合U中有{A,B,C,I}四个点，根绝查找法则，找到符合要求的边CF，如下图。并将点F加入到集合U中。
继续，依照查找法则我们找到边FG,如下图。并将点G加入到U中。
继续，依照查找法则我们找到边GH,如下图。并将点H加入到U中。
继续，依照查找法则我们找到边CD,如下图。并将点D加入到U中。
继续，依照查找法则我们找到边DE,如下图。并将点E加入到U中。
此时，满足U = V，即找到了这颗最小生成树。 附注：prim算法最小生成树的生成过程中，也有可能构成回路，需做判断。判断的方法和克鲁斯卡尔算法一样。
模板
int prime(int cur) { int index; int sum = 0; memset(visit, false, sizeof(visit)); visit[cur] = true; for(int i = 0; i < m; i ++){ dist[i] = graph[cur][i]; } for(int i = 1; i < m; i ++){ int mincost = INF; for(int j = 0; j < m; j ++){ if(!visit[j] && dist[j] < mincost){ mincost = dist[j]; index = j; } } visit[index] = true; sum += mincost; for(int j = 0; j < m; j ++){ if(!visit[j] && dist[j] > graph[index][j]){ dist[j] = graph[index][j]; } } } return sum; }以上文章部分参考https://www.cnblogs.com/adforce/p/3247437.html
