最小生成树文字总结.docxVIP

最小生成树文字总结 　　暑期集训之最小生成树总结　　关于最小生成树的算法实现总结　　——Kruskal算法和prim算法的实现　　Kruskal算法　　咱们先看一下Kruskal算法，此算法是并查集的经典运用，所以要深入了解这个算法，就得了解并查集。并查集的概念以及它的实现我就不再说了，简要介绍一下它几个基本的操作，主要就有三个：makeset(),findset(),Union_set()，就这三个基本的操作，下面看看代码实现。　　定义一个parent[MAX]数组，parent[i]用来保存元素i属于哪个集合，初始化为本身；再定义一个rank[MAX]数组，rank[i]用来保存的元素i的级别，初始化为0；　　makeset()函数：　　voidmakeset()//也相当于初始化，既是对parent[MAX]和rank[MAX]数组初始化{　　for(inti=0;irank[y])　　parent[y]=x;　　else{　　parent[x]=y;//两个相同是随便，但是后面的rank记得加加。　　rank[y]++;　　}　　}　　下面就看看Kruskal算法了：　　路径的定义：　　structLine//定义一个结构体，用来保存边　　{　　intx;　　inty;　　intw;　　booloperator　　#include　　#defineMAXXX00　　#defineMMAX502　　usingnamespacestd;　　structLine//定义一个结构体，用来保存边　　{　　intx;　　inty;　　intw;　　booloperatorrank[y])　　parent[y]=x;　　else{　　parent[x]=y;　　rank[y]++;　　}　　}　　intKruskal()　　{　　makeset();　　sort(line,line+edg);　　intcount=0;　　inti=0,tx,ty;　　intMax=-1;　　while(count最小生成树文字总结)储存载体上储存非线性的树结构，必须有标志指示出树的结构。因此，只要能区分根和子树，树可以采取各种方法来储存——多叉链表、左子女－右兄弟二叉链表、广义表、多维数组。由于操作的需求，储存方法并不是随意选取的。比如，在并查集的实现上，选取的是双亲链表。　　一个用途是做为逻辑判断，此时会常常听到一个名词——判定树。最常用的结构是二叉树，一个孩子代表true，一个孩子代表false。关于多叉判定树，有个例子是求8皇后的全部解——这个连高斯都算错了，我们比不上高斯，但是我们会让computer代劳。　　就像哲学界到现在还纠缠于物质和精神本源问题，实际上在树这里也是如此。有些情况下，并不能区分是做为储存来用还是做为判断来用，比如有哪些信誉好的足球投注网站树，既储存了数据，还蕴涵着判断。　　和后面的图相比，树更基本，也更常用。你可以不知道最短路径怎么求，却每时每刻都在和树打交道——看看你电脑里的文件夹吧。　　最后，附带一个求N皇后的全部解的程序。　　#include　　#defineN8　　intlayout[N];//布局　　intkey=0;　　intjudge(introw,intcol)//判断能否在放下　　{　　inti;　　for(i=0;irow;i++)　　{　　if(layout[i]==col)return0;//同一列　　if(i-layout[i]==row-col)return0;//同一条主对角线　　if(i+layout[i]==row+col)return0;//同一条副对角线　　}　　return1;　　}　　voidlay(introw)//在row行上放Queen　　{　　inti;　　if(row==N)//放完N个Queen输出布局　　{　　printf(\n%02d,++key);　　for(i=0;iN;i++)printf(%c%d,layout[i]+a,i+1);　　}　　else　　{　　for(i=0;iN;i++)//在i列上放Queen　　{　　layout[row]=i;　　if(judge(row,i))lay(row+1);　　}　　}　　}　　intmain()　　{　　lay(0);　　return0;　　}