最小生成树 prim算法代码,Java代码库,德仔网

代码语言
代码分类
【Java】最小生成树 prim算法
作者:Dezai.CN / 发布于2011/5/27/ 605
prim算法是一种贪心算法，将全部的顶点划分为2个集合，每次总在2个集合之间中找最小的一条边，局部最优最终达到全局最优，这正是贪心的思想。
具体的描述参见相关书籍：
描述

从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：V_new = {x}，其中x为集合V中的任一节点（起始点），E_new = {}；
重复下列操作，直到V_new = V：
1. 在集合E中选取权值最小的边（u, v），其中u为集合V_new中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
2. 将v加入集合V_new中，将（u, v）加入集合E_new中；
输出：使用集合V_new和E_new来描述所得到的最小生成树。
<div>
<pre><div><span style="color: rgb(0,0,255)">private</span><span style="color: rgb(0,0,0)"> Edge getMinEdge(VNode[] VNodes){   </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">从分离的2个集合之间求出最小的边</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">        Edge min </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">null</span><span style="color: rgb(0,0,0)">;        </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">for(int i = 0;i < VNodes.length;i++)</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">        </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">0</span><span style="color: rgb(0,0,0)">;i </span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)"> size();i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)        {            </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(VNodes[i].getVisited() </span><span style="color: rgb(0,0,0)">&&</span><span style="color: rgb(0,0,0)"> hasEdge(VNodes[i]))</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">从true集合向false集合找</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">            {                Edge temp </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> getMinEdgeFrom(VNodes[i]);                </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(min </span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">null</span><span style="color: rgb(0,0,0)">)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">第一次的初始化min</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">                    min </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp;                </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(temp.getLen() </span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)"> min.getLen())                    min </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp;            }        }        </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> min;    }        </span><span style="color: rgb(0,0,255)">private</span><span style="color: rgb(0,0,0)">  </span><span style="color: rgb(0,0,255)">boolean</span><span style="color: rgb(0,0,0)"> hasEdge(VNode node){   </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">判断某个标记true的顶点跟另一个集合之间是否有边</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">        </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(node.getFirst() </span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">null</span><span style="color: rgb(0,0,0)">)            </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">false</span><span style="color: rgb(0,0,0)">;        </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">        {            Edge temp </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> node.getFirst();            </span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(temp </span><span style="color: rgb(0,0,0)">!=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">null</span><span style="color: rgb(0,0,0)">)            {                </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> index </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp.getEnd();                </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(VNodes[index].getVisited() </span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">false</span><span style="color: rgb(0,0,0)">)                    </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">true</span><span style="color: rgb(0,0,0)">;                </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)"> temp </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp.getNext();            }        }        </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">false</span><span style="color: rgb(0,0,0)">;    }            </span><span style="color: rgb(0,0,255)">private</span><span style="color: rgb(0,0,0)"> Edge getMinEdgeFrom(VNode node){ </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">如果有边（前提），求出这个顶点到对方集合的最小边</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">        Edge min </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">null</span><span style="color: rgb(0,0,0)">;        Edge temp </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> node.getFirst();                </span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(temp </span><span style="color: rgb(0,0,0)">!=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">null</span><span style="color: rgb(0,0,0)">)        {            </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> index </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp.getEnd();            </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(VNodes[index].getVisited() </span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">false</span><span style="color: rgb(0,0,0)">)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">说明此时的temp是到对方集合的一条边</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">            {                </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(min </span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">null</span><span style="color: rgb(0,0,0)">)                    min </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp;                </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(temp.getLen() </span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)"> min.getLen())                    min </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp;            }            temp </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> temp.getNext();        }        </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> min;    }    </span></div></pre>



然后添加一个图来测试一下：

<div class="cnblogs_code">
<pre><div><span style="color: rgb(0,0,255)">public</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">static</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> main(String[] args) {        </span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)"> TODO Auto-generated method stub</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">        UnDirectedGraph g </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">new</span><span style="color: rgb(0,0,0)"> UnDirectedGraph();                </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">1</span><span style="color: rgb(0,0,0)">;i </span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">7</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)            g.addVNode(</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)">V</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)"> i);        g.addEdge(</span><span style="color: rgb(0,0,0)">0</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">1</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">6</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">0</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">2</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">1</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">0</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">3</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">5</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">1</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">2</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">5</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">1</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">4</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">5</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">2</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">3</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">5</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">2</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">4</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">6</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">2</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">5</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">4</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">3</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">5</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">2</span><span style="color: rgb(0,0,0)">);        g.addEdge(</span><span style="color: rgb(0,0,0)">4</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">5</span><span style="color: rgb(0,0,0)">, </span><span style="color: rgb(0,0,0)">6</span><span style="color: rgb(0,0,0)">);</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">严蔚敏数据结构中的那个图</span><span style="color: rgb(0,128,0)"></span><span style="color: rgb(0,0,0)">                Edge[] edges </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> g.getEdges(</span><span style="color: rgb(0,0,0)">0</span><span style="color: rgb(0,0,0)">);        System.out.println(</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)">输出最小生成树的边</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)">);        </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">0</span><span style="color: rgb(0,0,0)">;i </span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)"> edges.length;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)        {            </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> start </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> edges[i].getStart();            </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> end </span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)"> edges[i].getEnd();            System.out.println(</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)">边： </span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)"> g.VNodes[start].getVNode() </span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)">---</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)"> g.VNodes[end].getVNode()                     </span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)">   长度：</span><span style="color: rgb(0,0,0)">"</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)"> edges[i].getLen());        }}</span></div></pre>
</div>

</div>
试试其它关键字
　生成树　
同语言下
可能有用的
Dezai.CN贡献的其它代码(4037)