最小生成樹之Kruskal演算法?

Tags: 演算法, 頂點,

/**

* 檢測是否產生迴路

如果存在迴路，則必存在一個子圖，是一個環路。環路中所有頂點的度>=2。

n演算法：

第一步：刪除所有度<=1的頂點及相關的邊，並將另外與這些邊相關的其它頂點的度減一。

第二步：將度數變為1的頂點排入佇列，並從該佇列中取出一個頂點重複步驟一。

如果最後還有未刪除頂點，則存在環，否則沒有環。

n演算法分析：

由於有m條邊，n個頂點。

i)如果m>=n，則根據圖論知識可直接判斷存在環路。（證明：如果沒有環路，則該圖必然是k棵樹 k>=1。根據樹的性質，邊的數目m = n-k。k>=1，所以：m

ii)如果m

* @param this

* @return

publicboolean isGraphHasCircle() {

//若圖中沒有頂點，或者只有一個頂點則沒有迴路

if(this.getPointList() == null this.getPointList().size() < 2){

returnfalse;

}

if(this.getEdgeList().size() > this.getPointList().size()){

returntrue;

}

Graph g = this.clone();

int pointsLeftCount = g.getPointList().size();

while(pointsLeftCount > 0){

//一次遍歷如沒有刪除一個度小於2的點，則結束迴圈

boolean endFlag = true;

Point pointForRemove = null;

for (Point p : g.getPointList()) {

//計算頂點的度

if(g.getCountForPoint(p) <= 1){

//為了規避最後一個頂點被刪除是的併發異常採用標記刪除

pointForRemove = p;

//刪除之後從新遍歷頂點

endFlag = false;

break;

}

if(endFlag){

break;

}else{

g.removePoint(pointForRemove);

List edgeForRemoveList = new ArrayList ();

for (EdgeWithWeight e : g.getEdgeList()) {

if(e.isPointInEdge(pointForRemove)){

edgeForRemoveList.add(e);

}

for (EdgeWithWeight edgeWithWeight : edgeForRemoveList) {

g.removeEdge(edgeWithWeight);

}

pointsLeftCount = g.getPointList().size();

}

if(g.getPointList().size() > 0){

returntrue;

}else{

returnfalse;

}

/**

* 計算頂點的度

* @param p

* @return

privateint getCountForPoint(Point p) {

int count = 0;

for (EdgeWithWeight e : this.getEdgeList()) {

if(e.isPointInEdge(p)){

count = count + 1;

}

return count;

}

/**

* @param args

publicstaticvoid main(String[] args) {

}

Prim演算法調整

Java程式碼

package com.zas.test.tree;

/**

* Prim演算法實現的是找出一個有權重連通圖中的最小生成樹，即：具有最小權重且連線到所有結點的樹。

* @author zas

publicclass Prim {

//一個要找最小生成樹的圖

Graph graph;

public Prim(Graph graph) {

super();

this.graph = graph;

}

public Graph getGraph() {

return graph;

}

publicvoid setGraph(Graph graph) {

this.graph = graph;

}

/**

* 首先以一個結點作為最小生成樹的初始結點，然後以迭代的方式找出與最小生成樹中各結點權重最小邊，

* 並加入到最小生成樹中。加入之後如果產生迴路則跳過這條邊，選擇下一個結點。

* 當所有結點都加入到最小生成樹中之後，就找出了連通圖中的最小生成樹了。

* @return

public Graph prim() {

Graph minTree = new Graph();

for (Point p : graph.getPointList()) {

minTree.addPoint(p);

//獲得該點的最小權重邊

EdgeWithWeight edge = getMinWeightEdgeForPoit(p, minTree);

if(null != edge){

//新增該邊到最小生成樹

minTree.addEdge(edge);

//檢測是否產生迴路

if(minTree.isGraphHasCircle()){

minTree.removeEdge(edge);

}

return minTree;

}

/**

* 獲取權重最小邊

* @param p

* @param minTree

* @return

private EdgeWithWeight getMinWeightEdgeForPoit(Point p, Graph minTree) {

EdgeWithWeight e = null;

for (EdgeWithWeight edge : graph.getEdgeList()) {

if(!minTree.isEdgeInGraph(edge)){

if(edge.isPointInEdge(p)){

if(e == null){

e = edge;

}else{

if(e.compareTo(edge) == -1){

e = edge;

}

return e;

}

/**

* @param args

publicstaticvoid main(String[] args) {

//構建一個圖

Graph graph = new Graph();

Point a = new Point("A");

Point b = new Point("B");

Point c = new Point("C");

Point d = new Point("D");

Point e = new Point("E");

Point f = new Point("F");

graph.addPoint(a);

graph.addPoint(b);

graph.addPoint(c);

graph.addPoint(d);

graph.addPoint(e);

graph.addPoint(f);

//所有邊權重相同

graph.addEdge(new EdgeWithWeight(a, b, new Weight()));

graph.addEdge(new EdgeWithWeight(a, c, new Weight()));

graph.addEdge(new EdgeWithWeight(a, d, new Weight()));

graph.addEdge(new EdgeWithWeight(b, c, new Weight()));

graph.addEdge(new EdgeWithWeight(b, e, new Weight()));

graph.addEdge(new EdgeWithWeight(c, d, new Weight()));

graph.addEdge(new EdgeWithWeight(c, e, new Weight()));

graph.addEdge(new EdgeWithWeight(c, f, new Weight()));

graph.addEdge(new EdgeWithWeight(d, f, new Weight()));

graph.addEdge(new EdgeWithWeight(e, f, new Weight()));

Prim prim = new Prim(graph);

Graph minTree = prim.prim();

System.out.println(minTree);

Graph graphWithWeight = new Graph();

graphWithWeight.addPoint(a);

graphWithWeight.addPoint(b);

graphWithWeight.addPoint(c);

graphWithWeight.addPoint(d);

graphWithWeight.addPoint(e);

graphWithWeight.addPoint(f);

graphWithWeight.addEdge(new EdgeWithWeight(a, b, new Weight(6)));

graphWithWeight.addEdge(new EdgeWithWeight(a, c, new Weight(1)));

graphWithWeight.addEdge(new EdgeWithWeight(a, d, new Weight(5)));

graphWithWeight.addEdge(new EdgeWithWeight(b, c, new Weight(5)));

graphWithWeight.addEdge(new EdgeWithWeight(b, e, new Weight(3)));

graphWithWeight.addEdge(new EdgeWithWeight(c, d, new Weight(7)));

graphWithWeight.addEdge(new EdgeWithWeight(c, e, new Weight(5)));

graphWithWeight.addEdge(new EdgeWithWeight(c, f, new Weight(4)));

graphWithWeight.addEdge(new EdgeWithWeight(d, f, new Weight(2)));

graphWithWeight.addEdge(new EdgeWithWeight(e, f, new Weight(6)));

Prim primForWeigtTree = new Prim(graphWithWeight);

Graph minTreeForWeightTree = primForWeigtTree.prim();

System.out.println(minTreeForWeightTree);

}

Kruskal演算法實現

Java程式碼

package com.zas.test.tree;

import java.util.ArrayList;

import java.util.List;

/**

* Kruskal演算法思想不同於Prim演算法，

* Kruskal演算法是一種按照連通網中邊的權值的遞增順序構造最小生成樹的演算法。

* @author zas

publicclass Kruskal {

//一個要找最小生成樹的圖

Graph graph;

public Kruskal() {

super();

}

public Kruskal(Graph graph) {

super();

this.graph = graph;

}

public Graph getGraph() {

return graph;

}

publicvoid setGraph(Graph graph) {

this.graph = graph;

}

/**

* Kruskal演算法的基本步驟 :

* 假設G=(V,E)是一個具有n個頂點的連通網，T=(U,TE)是G的最小生成樹。

* 令集合U的初值為U=V，即包含有G中全部頂點，集合TE的初值為TE={}。

* 然後，將圖G中的邊按權值從小到大的順序依次選取，若選取的邊使生成樹T不形成迴路，則把它併入TE中，保留作為T的一條邊；

* 若選取的邊使生成樹T形成迴路，則將其捨棄，如此進行下去，直到TE中包含有n-1條邊為止，此時的T即為最小生成樹。

* @return

public Graph kruskal() {

Graph minTree = new Graph();

//將所有頂點加入最小生成樹

for (Point p : this.getGraph().getPointList()) {

minTree.addPoint(p);

}

//對原圖的邊按權值從小到大排序

List edgeList = sortByEdgeAsc(this.graph.getEdgeList());

//加入 n - 1條最小權值邊

for (int i = 0; i < edgeList.size(); i++) {

EdgeWithWeight edge = edgeList.get(i);

minTree.addEdge(edge);

//是否含有環

if(minTree.isGraphHasCircle()){

minTree.removeEdge(edge);

}

//結束條件

if(minTree.getEdgeList().size() == minTree.getPointList().size() - 1){

break;

}

return minTree;

}

/**

* 對邊按權值從小到大排序

* @param edgeList

* @return

private List sortByEdgeAsc(List graphEdgeList) {

//克隆一下，防止影響到原圖

List edgeList = new ArrayList ();

for (EdgeWithWeight edgeWithWeight : graphEdgeList) {

edgeList.add(edgeWithWeight);

}

//暫時採用選擇排序，如果資料規模大、有效能要求可改進

int selectedIndex = 0;

EdgeWithWeight edgeForSwap = null;

for (int i = 0; i < edgeList.size(); i++) {

selectedIndex = i;

for (int j = i + 1; j < edgeList.size(); j++) {

if(edgeList.get(j).compareTo(edgeList.get(selectedIndex)) == 1){

selectedIndex = j;

}

if(selectedIndex != i){

//交換

edgeForSwap = edgeList.get(selectedIndex);

edgeList.set(selectedIndex, edgeList.get(i));

edgeList.set(i, edgeForSwap);

}

return edgeList;

}

/**

* @param args

publicstaticvoid main(String[] args) {

//構建一個圖

Graph graph = new Graph();

Point a = new Point("A");

Point b = new Point("B");

Point c = new Point("C");

Point d = new Point("D");

Point e = new Point("E");

Point f = new Point("F");

graph.addPoint(a);

graph.addPoint(b);

graph.addPoint(c);

graph.addPoint(d);

graph.addPoint(e);

graph.addPoint(f);

// 所有邊權重相同

graph.addEdge(new EdgeWithWeight(a, b, new Weight()));

graph.addEdge(new EdgeWithWeight(a, c, new Weight()));

graph.addEdge(new EdgeWithWeight(a, d, new Weight()));

graph.addEdge(new EdgeWithWeight(b, c, new Weight()));

graph.addEdge(new EdgeWithWeight(b, e, new Weight()));

graph.addEdge(new EdgeWithWeight(c, d, new Weight()));

graph.addEdge(new EdgeWithWeight(c, e, new Weight()));

graph.addEdge(new EdgeWithWeight(c, f, new Weight()));

graph.addEdge(new EdgeWithWeight(d, f, new Weight()));

graph.addEdge(new EdgeWithWeight(e, f, new Weight()));

Kruskal kruskal = new Kruskal(graph);

Graph minTree = kruskal.kruskal();