[ Alg info ] Borůvka's algorithm (MST)

來源自 這裡 
Preface: 
Borůvka's algorithm 用在圖形演算法中來找出 MST (minimum spanning tree), 再使用這個演算法有個要求是所有 edge 上的 權重必須是 distinct. 底下是這個演算法的典故: 

The algorithm was rediscovered by Choquet in 1938;[4] again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki[5] in 1951; and again by Sollin [6] in 1965. Because Sollin was the only computer scientist in this list living in an English speaking country, this algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature.

Pseudocode: 
底下為此演算法的 Pseudo code: 
 

簡單說明如下: 

1. 使用一個 List T 紀錄該 Graph 的所有 Component, 初始值為每一個 Vertex 都當作一個 Component.
2. 使用一個 While loop 處理這個 List 直到這個 List 只剩下一個 Component.
2.1. 從該 List 依序取出 Component. 並使用一個初始 set S 紀錄接下來處理過程中最小權重的 edge
2.2. 接著處理取出 Component 中的每一個 vertex, 接著找出每個 vertex 連接的 edge 中權重最低的加入到 set S.
2.3. 從 set S 中取出權重最低的 edge 並加入到 Component. (該 edge 上的 vertex 也會被加到 Component, 而包含該 vertex 的 Component 則會與處理的 Component 進行 merge)
2.4. 將被合併的 Component 從 List T 移除.
3. 當 List T 中只剩下一個 Component, 則該 Component 則會是 MST!

Complexity: 
Borůvka's algorithm can be shown to take O(log V) iterations of the outer loop until it terminates, and therefore to run in time O(E log V), where E is the number of edges, and V is the number of vertices in G. In planar graphs, and more generally in families of graphs closed under graph minor operations, it can be made to run in linear time, by removing all but the cheapest edge between each pair of components after each stage of the algorithm. 

Example: 

1. 上面第一列為初始狀態, 即將每個 Vertex 視為一個 Component. 
2. 上面第二列為第一次 Iteration, 從每個 Component 找出權重最低的 edge 並加到該 Component. 最後合併完剩下兩個 Component: {ABDF} 與 {CEG}. 
3. 上面第三列為第二次 Iteration, 即從 {ABDF} 與 {CEG} 中找出權重最低的 edge, 即 E(B,E)=10. 並合併兩個 Component 後只剩下一個 Component {ABCDEFG}. 

Implementation: 
根據上面演算法, 下面使用 Java 進行實作: 
- Vertex.java : Graph 中的 Vertex 類別 

view plaincopy to clipboardprint?

1. package map;  
2.   
3. import java.util.Set;  
4.   
5. public class Vertex implements Comparable{  
6.     public String name;  
7.     public Set edgeSet=new TreeSet();  
8.       
9.     public Vertex(String n){this.name = n;}  
10.       
11.     public void addEdge(Vertex to, int cost)  
12.     {  
13.         addEdge(to, cost, false);  
14.     }  
15.       
16.     public void addEdge(Vertex to, int cost, boolean isDir)  
17.     {  
18.         edgeSet.add(new Edge(isDir, this, to, cost));  
19.     }  
20.       
21.     @Override  
22.     public boolean equals(Object o)  
23.     {  
24.         if(o instanceof Vertex)  
25.         {  
26.             Vertex v = (Vertex)o;  
27.             return this.name.equals(v.name);  
28.         }  
29.         return false;  
30.     }  
31.   
32.     @Override  
33.     public int compareTo(Vertex o) {  
34.         return name.compareTo(o.name);  
35.     }  
36. }  

- Edge.java : Graph 中用來記錄 edge 訊息 

view plaincopy to clipboardprint?

1. package map;  
2.   
3. public class Edge implements Comparable{  
4.     public boolean isDirect = false;  
5.     public Vertex from;  
6.     public Vertex to;  
7.     public int cost;  
8.       
9.     public Edge(Vertex f, Vertex t, int cost){this.from = f; this.to = t;this.cost=cost;}  
10.     public Edge(boolean isDir, Vertex f, Vertex t, int cost){this(f,t,cost); isDirect=isDir;}  
11.       
12.     @Override  
13.     public boolean equals(Object o)  
14.     {  
15.         if(o instanceof Edge)  
16.         {  
17.             Edge e = (Edge)o;  
18.             if(isDirect)  
19.             {  
20.                 return from.equals(e.from) && to.equals(e.to);  
21.             }  
22.             else  
23.             {  
24.                 return from.equals(e.from) && to.equals(e.to) ||  
25.                        from.equals(e.to) && to.equals(e.from);  
26.             }  
27.         }  
28.         return false;  
29.     }  
30.       
31.     @Override  
32.     public int hashCode()  
33.     {  
34.         return from.hashCode()+to.hashCode()+cost;  
35.     }  
36.       
37.     @Override  
38.     public String toString()  
39.     {  
40.         if(isDirect) return String.format("%s->%s (%d)", from.name, to.name, cost);  
41.         else return String.format("%s-%s (%d)", from.name, to.name, cost);  
42.     }  
43.       
44.     @Override  
45.     public int compareTo(Edge o) {  
46.         int i = from.name.compareTo(o.from.name);  
47.         if(i==0)  
48.         {  
49.             return to.name.compareTo(o.to.name);  
50.         }  
51.         return i;  
52.     }  
53. }  

- Component.java: 用來表示連接多個 Vertex 的 sub graph 

view plaincopy to clipboardprint?

1. package map;  
2.   
3. import java.util.HashMap;  
4.   
5. public class Component {  
6.     public String name="";  
7.     public HashMap vertexMap = new HashMap();  
8.     public Set edgeToProcess = new TreeSet();  
9.       
10.     public Component(Vertex v){addVertex(v);}  
11.       
12.     public void addVertex(Vertex v)  
13.     {  
14.         vertexMap.put(v.name, new Vertex(v.name));  
15.         edgeToProcess.addAll(v.edgeSet);  
16.         name = name+v.name;  
17.     }  
18.       
19.     @Override  
20.     public boolean equals(Object o)  
21.     {  
22.         if(o instanceof Component)  
23.         {  
24.             Component c = (Component)o;  
25.             return name.equals(c.name);  
26.         }  
27.         return false;  
28.     }  
29.       
30.     public boolean intersect(Set set){  
31.         for(Vertex v:set) if(vertexMap.containsKey(v.name)) return true;  
32.         return false;  
33.     }  
34.       
35.     public void connect(Edge e, Component oc)  
36.     {  
37.         if(e.isDirect)  
38.         {  
39.             vertexMap.get(e.from.name).addEdge(oc.vertexMap.get(e.to.name), e.cost);  
40.         }  
41.         else  
42.         {  
43.             vertexMap.get(e.from.name).addEdge(oc.vertexMap.get(e.to.name), e.cost);  
44.             oc.vertexMap.get(e.to.name).addEdge(vertexMap.get(e.from.name), e.cost);  
45.         }  
46.         vertexMap.putAll(oc.vertexMap);  
47.         edgeToProcess.addAll(oc.edgeToProcess);  
48.         Iterator iter = edgeToProcess.iterator();  
49.         while(iter.hasNext())  
50.         {             
51.             if(vertexMap.containsKey(iter.next().to.name)) iter.remove();  
52.         }  
53.         StringBuffer nameBuf = new StringBuffer();        
54.         for(Vertex v:vertexMap.values()) nameBuf.append(v.name);  
55.         name = nameBuf.toString();  
56.     }  
57.       
58.     @Override  
59.     public String toString(){     
60.         StringBuffer outBuf = new StringBuffer();  
61.         for(Vertex from:vertexMap.values())  
62.         {  
63.             outBuf.append(String.format("Vertex-%s:\n", from.name));  
64.             for(Edge e:from.edgeSet)  
65.             {  
66.                 outBuf.append(String.format("\t%s\n", e));  
67.             }  
68.         }  
69.         return outBuf.toString();  
70.     }  
71. }  

- Graph.java: 最後是用來代表 Graph 的類別, 可以呼叫上面的方法 getMST() 得到 Minimum spanning tree 

view plaincopy to clipboardprint?

1. package map;  
2.   
3. import java.util.ArrayList;  
4.   
5. public class Graph {  
6.     public boolean isDirect=false;  
7.     public TreeMap vtxMap = new TreeMap();  
8.       
9.     public void addVertex(int name){addVertex(String.valueOf(name));}  
10.     public void addVertex(String name)  
11.     {  
12.         vtxMap.put(name, new Vertex(name));  
13.     }  
14.       
15.     public boolean addEdge(int from, int to, int cost){return addEdge(String.valueOf(from),  
16.                                                                       String.valueOf(to),  
17.                                                                       cost);}  
18.     public boolean addEdge(String from, String to, int cost)  
19.     {  
20.         Vertex fv = vtxMap.get(from);  
21.         Vertex tv = vtxMap.get(to);  
22.         if(fv!=null && tv!=null)   
23.         {  
24.             if(isDirect)  
25.             {  
26.                 fv.addEdge(tv, cost, isDirect);  
27.             }  
28.             else  
29.             {  
30.                 fv.addEdge(tv, cost, isDirect);  
31.                 tv.addEdge(fv, cost, isDirect);  
32.             }  
33.             return true;  
34.         }  
35.         return false;  
36.     }  
37.       
38.     /** 
39.      * BD: Get Minimum Spanning Tree based on Kruskal's algorithm. 
40.      * Ref: 
41.      *   - wiki of Kruskal's algorithm: 
42.      *     http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm 
43.      * @return 
44.      */  
45.     public Component getMST()  
46.     {  
47.         List compList = new ArrayList();  
48.         Set compToAdd = new HashSet();  
49.         Set apSet = new HashSet(); // Keep already connected vertex   
50.                                                    // in each iteration.  
51.         HashMap vcMap = new HashMap();  
52.         for(Vertex v:vtxMap.values()) {  
53.             Component c = new Component(v);  
54.             compList.add(c);  
55.             vcMap.put(v, c);  
56.         }  
57.         int iterCnt = 1;  
58.         while(compList.size()>1)  
59.         {  
60.             System.out.printf("\t[Info] Iter%d (%d)...\n", iterCnt++, compList.size());  
61.             compToAdd.clear();  
62.             apSet.clear();  
63.             Object[] compArray = compList.toArray();  
64.             for(int i=0; i
65.             {  
66.                 Component c = (Component)compArray[i];  
67.                 if(c.intersect(apSet)) continue;  
68.                 Edge te = null; int mc=Integer.MAX_VALUE;  
69.                 for(Edge e:c.edgeToProcess)  
70.                 {  
71.                     if(e.cost
72.                     {  
73.                         mc = e.cost;  
74.                         te = e;  
75.                     }  
76.                 }  
77.                 Component tc = vcMap.get(te.to);  
78.                 if(tc!=c)  
79.                 {     
80.                     System.out.printf("\t[Info] Merge %s with %s (%s)...", c.name, tc.name, te);  
81.                     c.connect(te, tc);  
82.                     System.out.printf("%s\n", c.name);  
83.                     for(Vertex v:c.vertexMap.values())   
84.                     {  
85.                         vcMap.put(vtxMap.get(v.name), c);  
86.                         apSet.add(v);  
87.                     }  
88.                     //compToAdd.add(c);  
89.                     compList.remove(tc);  
90.                 }  
91.             }  
92.             /*compList.clear(); 
93.             for(Component c:vcMap.values()) compToAdd.add(c); 
94.             compList.addAll(compToAdd);*/  
95.         }  
96.         return compList.get(0);  
97.     }  
98.       
99.     @Override  
100.     public String toString()  
101.     {  
102.         StringBuffer outBuf = new StringBuffer();  
103.         for(Vertex from:vtxMap.values())  
104.         {  
105.             outBuf.append(String.format("Vertex-%s:\n", from.name));  
106.             for(Edge e:from.edgeSet)  
107.             {  
108.                 outBuf.append(String.format("\t%s\n", e));  
109.             }  
110.         }  
111.         return outBuf.toString();  
112.     }  
113.       
114.     public static void main(String args[])  
115.     {  
116.         Graph g = new Graph();  
117.         g.addVertex("A"); g.addVertex("B"); g.addVertex("C"); g.addVertex("D");  
118.         g.addVertex("E"); g.addVertex("F"); g.addVertex("G");  
119.         g.addEdge("A", "B", 7);  
120.         g.addEdge("A", "D", 4);  
121.         g.addEdge("B", "D", 9);  
122.         g.addEdge("B", "E", 10);  
123.         g.addEdge("B", "C", 11);  
124.         g.addEdge("C", "E", 5);  
125.         g.addEdge("D", "E", 15);  
126.         g.addEdge("D", "F", 6);  
127.         g.addEdge("E", "F", 12);  
128.         g.addEdge("E", "G", 8);  
129.         g.addEdge("F", "G", 13);  
130.         System.out.printf("\t[Info] Graph:\n%s\n", g);  
131.         Component c = g.getMST();  
132.         System.out.printf("\t[Info] MST:\n%s\n", c);  
133.     }  
134. }  

Other algorithms: 
Other algorithms for this problem include Prim's algorithm and Kruskal's algorithm. Fast parallel algorithms can be obtained by combining Prim's algorithm with Borůvka's.[8] 

A faster randomized minimum spanning tree algorithm based in part on Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected O(E) time.[9] The best known (deterministic) minimum spanning tree algorithm by Bernard Chazelle is also based in part on Borůvka's and runs in O(E α(E,V)) time, where α is the inverse of the Ackermann function.[10] These randomized and deterministic algorithms combine steps of Borůvka's algorithm, reducing the number of components that remain to be connected, with steps of a different type that reduce the number of edges between pairs of components. 

Supplement: 
* [ Data Structures with Java ] Section 25.6 : Minimum Spanning Tree 
* [ 資料結構 小學堂 ] 圖形結構 : 擴張樹 (Prim) 
* [ 資料結構 小學堂 ] 圖形結構 : 擴張樹 - 求最小成本擴張樹 (Kruskal 演算法)