给大家介绍一下普利姆算法,
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。
那么它到底是个什么东西?
首先,我们要知道这个算法是跟图这个数据结构有关的,而我们要通过这个算法得到再这个图中,如何在经历所有点的情况下,有着最短路径。
给大家举个例子,看下面这张图:
在这个图中,我们可以看到这个图中一共有七个顶点,十一条边。
每个点之间的数字代表着两个点之间的距离。
为了解决这一问题,我们首先要先把眼前的图转换成邻接矩阵,
class MGraph{int verxs;char [] data;int [][] weight;public MGraph(int verxs){this.verxs= verxs;data=new char[verxs];weight=new int[verxs][verxs];}}
上面这个代码代表着构建了一个图类,把图的顶点和各类数据构造出来。
而我们要完成这个事情,就要用到最小二叉树,因此,我们要构造一个最小二叉树的相关类。在这个类中,首先,我们要通过图的各类数据传入,来完成邻接矩阵。
public void createGraph(MGraph mGraph,int verxs,char[]data,int [][]weight){for(int i=0,j=0;i<verxs;i++){mGraph.data[i]=data[i];for(j=0;j<verxs;j++){mGraph.weight[i][j]=weight[i][j];}}}
接下来,就到了算法的核心步骤。我们要对邻接矩阵进行遍历。
比如说,我们从A点开始,那么我们有两种选择,一种是A-D,一种是A-B,很明显,前者的距离小于后者,因此我们选D。接下来,我们以A和D为起点往后找,有A-B,D-B,D-E,D-F,我们选取最小值,所以选择了D-F。以此类推,下一次我们就选择了以A,D,F为起点来往后找,依次遍历,直到边的数量等于点的数量减一即可。
public void prim(MGraph mGraph,int v){int[]visited = new int[mGraph.verxs];visited[v]=1;int h1=-1;int h2=-1;int minWeight=10000;for(int k=1;k<mGraph.verxs;k++){for(int i=0;i<mGraph.verxs;i++){for(int j=0;j<mGraph.verxs;j++){if(visited[i]==1 && visited[j]==0 && mGraph.weight[i][j]<minWeight){minWeight=mGraph.weight[i][j];h1=i;h2=j;}}}System.out.println("边<"+mGraph.data[h1]+","+mGraph.data[h2]+">权值"+minWeight);minWeight=10000;visited[h2]=1;}}
接下来我们对代码进行测试,
@Testpublic void test() {char[] data = {'a','b','c','d','e','f','g'};int verxs= data.length;int [][]weight={{10000,7,10000,5,10000,10000,10000},{7,10000,8,9,10000,10000,10000},{10000,8,10000,10000,5,10000,10000},{5,9,10000,10000,15,6,10000},{10000,7,5,15,10000,8,9},{10000,10000,10000,6,8,10000,11},{10000,10000,10000,10000,9,11,10000}};MGraph mGraph = new MGraph(verxs);Mintree mintree = new Mintree();mintree.createGraph(mGraph,verxs,data,weight);mintree.prim(mGraph,0);}
运行结果如下: