今天做洛谷的时候，磨练了很多图式问题，发现自己在这方面算法的掌握还有待提高。 这里先介绍一下最小生成树的算法吧。
最小生成树最小生成树(minimum spanning tree )是用n个顶点、n-1个边连接一个连接图，使权重最小的结构。
最小生成树可以通过prim (prim )算法或kruskal (无知的姐姐)算法求出。
它还可以由bfs和dfs生成。 分别称为bfs生成树和dfs生成树。
例如：
prim (prim )算法这里是存储在邻接矩阵中的，
我个人认为Prim类似于最短路的dijkstra。 方法：
首先做只有一个节点的树。 该节点可以是原始图中的任何节点。
用一条边扩展此树，要求此边一个顶点在树中，另一个顶点不在树中，且此边权重最小。
重复步骤，直到所有顶点都在树上。
图：
# include stdio.h # definemax 100 # definemaxcost 100000 int graph [ max ] [ max ]； voidprim(intgraph[][max]，int n ) { int lowcost[MAX]； //lowcost[i]:表示以I为终点的边上的最小权重，在lowcost[i]=0的情况下在I点上添加MST int mst[MAX]； 表示与lowcost[i]相对应的起点，当mst[i]=0时，表示起点I加入MST int i，j，min，minid，sum=0； for(I=2； i=n； I ) { lowcost[i]=graph[1][i]； //lowcost存储顶点1可到达点的路径长度mst[i]=1； //初始化以1位开始(MST(1)=0； for(I=2； i=n； I ) { min=MAXCOST； minid=0； for(j=2； j=n； j () if ) lowcost[j]minlowcost[j]！=0) { min=lowcost[j]； //找到权重最短的路径长度minid=j找到最小的id ] printf (v % d-v % d=% dn )、mst[minid]、minid、min )； sum =min； //合计lowcost[minid]=0； //此处的最短路径为0for(j=2； j=n； j () if ) graph[minid][j]lowcost[j] ) /更新在此点正交的顶点的路径{ lowcost[j]=graph[minid][j]； mst[j]=minid； } } } printf ('最小权重之和=%dn '，sum )； (}int main ) ) { int i，j，k，m，n； int x，y，cost； scanf('%d%d )、m和n )； //m=顶点个数，n=边的个数for(I=1； i=m； I//初始化映射{for(j=1； j=m； j({graph[I][j]=MaxCost； }for(k=1； k=n； k ) Scanf('%d%d%d )、I、j、cost )； graph[i][j]=cost； graph[j][i]=cost； (prim ) graph，m )； 返回0； }
kruskal算法kruskal是一种可以在o(mlogm )时间内得到最小生成树的算法。 这主要基于贪婪的思想：
按照边权从小到大的顺序对边进行排序，制作无边图t。
选择从未被选中过的边权最小的边。
当这一边的2个顶点位于t的连接块不同时，将其追加到图t中，如果相同则跳过。
重复和直到图t相连。
实际上，在此仅维持连接性，而实际上不需要制作图t，也能够通过并行检查组进行维持。
在这里，使用旁边的桌子而不是链表进行操作。
# include stdio.h # definem axe 100 # define max v100 typedef struct { int vex 1； //边的开始顶点int vex2； //边尾的顶点int weight； //边缘权重(}Edge； voidkruskal(edgee[]，int n，int e ) intI，j，m1，m2，sn1，sn2，k，sum=0； int vset[n 1]； //借用辅助数组vset[i]判断某边是否添加了最小生成树集//将各顶点视为连接成分，集数组的初始化for(I=1； i=n； I//初始化辅助数组vset[i]=i的k=1； //表示当前结构的最小生成树的第k条边，初始值为1 j=0； //E中的边下标，初始值为0while(ke ) /生成的边数小于e时继续循环(m1=e(j ).vex1； m2=E[j].vex2； //一边的两个邻接点sn1=vset[m1]； sn2=vset[m2]； //分别得到两个顶点所属的集合号if(sn1 )！=sn2 ) /两个顶点属于不同的集合，这一边是最小生成树的一边(//闭合电路printf(v%d-v%d=%d(n )，m1，m2，E[j].weight )； sum=E[j].weight； k； //生成边数为if(k=n ) break； for(I=1； i=n； I//将两个集合统一编号if(vset[I]==sn2 )//集合编号sn2变更为sn1vset[i]=sn1； (j )； //扫描下一边} printf ('最小权重之和=%dn '，sum )； (/)以下称为快语(edgearr )、int low、int high )、{ int key； Edge lowx； lowx=arr[low]； key=arr[low].weight； while(lowhigh ) (while ) lowhighArr[high].weight=key ) high--； if(lowhigh ) arr[low ]=arr[high]； wile (lowhigharr [ low ].weight=key ) low； if(lowhigh ) arr[high--]=arr[low]； } arr[low]=lowx； 返回低； }voidquick_sort(edgearr[]，int start，int end ) {int pos； if(startend ) ) pos=fun(arr，start，end )； quick_sort(ARR，start，pos-1 )； quick_sort(arr，pos 1，end )； }}int main () {Edge E[MAXE]； int nume，numn； //Freopen(1.txt )、(r )、stdin )； //文件输入printf (输入顶数和边数：(n )； scanf('%d%d )、numn和nume )； for(intI=0； inume； I ) scanf('%d%d )、E[i].vex1、E[i].vex2、E[i].weight )； quick_sort(e，0，nume-1 )； kruskal(e，numn，nume )； }