fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.HashSet;
  4. import java.util.List;
  5. import java.util.Set;
  6.  
  7. public class Main {
  8.  
  9. 	public static void main(String[] args) {
  10. 		// Wikipediaのサンプルグラフ
  11. 		Kruskal.Graph g = new Kruskal.Graph(
  12. 			new int[][]{
  13. 				{0, 1, 7},
  14. 				{0, 3, 5},
  15. 				{1, 2, 8},
  16. 				{1, 3, 9},
  17. 				{1, 4, 7},
  18. 				{2, 4, 5},
  19. 				{3, 4, 15},
  20. 				{3, 5, 6},
  21. 				{4, 5, 8},
  22. 				{4, 6, 9},
  23. 				{5, 6, 11},
  24. 			}
  25. 		);
  26.  
  27. 		int cost = 0;
  28. 		Kruskal k = new Kruskal();
  29. 		for(Kruskal.Edge e : k.getMinimumSpanningTreeEdges(g)) {
  30. 			System.out.println(e.u + ", " + e.v + ", " + e.c);
  31. 			cost += e.c;
  32. 		}
  33. 		System.out.println("cost : " + cost);
  34. 	}
  35. }
  36.  
  37. class Kruskal {
  38.  
  39. 	public List<Edge> getMinimumSpanningTreeEdges(Graph graph) {
  40. 		List<Edge> result = new ArrayList<Edge>();
  41. 		List<Edge> edges = graph.getEdges();
  42. 		Collections.sort(edges);
  43. 		UnionFindTree uft = new UnionFindTree(Collections.max(graph.getVertexes())+1);
  44. 		for(Edge e : edges) {
  45. 			if(!uft.belongsToSameTree(e.u, e.v)) {
  46. 				uft.unite(e.u, e.v);
  47. 				result.add(e);
  48. 			}
  49. 		}
  50. 		return result;
  51. 	}
  52.  
  53. 	public static class Graph {
  54. 		private final Set<Integer> vertexes;
  55. 		private final List<Edge> edges;
  56.  
  57. 		public Graph() {
  58. 			this.vertexes = new HashSet<Integer>();
  59. 			this.edges = new ArrayList<Edge>();
  60. 		}
  61.  
  62. 		public Graph(int[][] edges) {
  63. 			this();
  64. 			for(int[] e : edges) {
  65. 				addEdge(e[0], e[1], e[2]);
  66. 			}
  67. 		}
  68.  
  69. 		public void addEdge(int u, int v, int c) {
  70. 			vertexes.add(u);
  71. 			vertexes.add(v);
  72. 			edges.add(new Edge(u, v, c));
  73. 		}
  74.  
  75. 		public List<Edge> getEdges() {
  76. 			return new ArrayList<Edge>(edges);
  77. 		}
  78.  
  79. 		public Set<Integer> getVertexes() {
  80. 			return new HashSet<Integer>(vertexes);
  81. 		}
  82. 	}
  83.  
  84. 	public static class Edge implements Comparable<Edge> {
  85. 		public final int u;
  86. 		public final int v;
  87. 		public final int c;
  88.  
  89. 		public Edge(int u, int v, int c) {
  90. 			this.u = u;
  91. 			this.v = v;
  92. 			this.c = c;
  93. 		}
  94.  
  95. 		@Override
  96. 		public int compareTo(Edge e) {
  97. 			return c - e.c;
  98. 		}
  99. 	}
  100.  
  101. 	private class UnionFindTree {
  102. 		private final Element[] elements;
  103.  
  104. 		public UnionFindTree(int n) {
  105. 			elements = new Element[n];
  106. 			for(int i=0; i<n; i++) {
  107. 				elements[i] = new Element(i);
  108. 			}
  109. 		}
  110.  
  111. 		public boolean belongsToSameTree(int x, int y) {
  112. 			return findRootElement(elements[x]).equals(findRootElement(elements[y]));
  113. 		}
  114.  
  115. 		public void unite(int x, int y) {
  116. 			link(findRootElement(elements[x]), findRootElement(elements[y]));
  117. 		}
  118.  
  119. 		private Element findRootElement(Element x) {
  120. 			Element element = x;
  121. 			while (!element.isRoot()) {
  122. 				element = elements[element.parent];
  123. 			}
  124. 			return element;
  125. 		}
  126.  
  127. 		private void link(Element x, Element y) {
  128. 			if(x.value == y.value) {
  129. 				return;
  130. 			}
  131. 			if(x.rank < y.rank) {
  132. 				x.parent = y.value;
  133. 			}
  134. 			else {
  135. 				y.parent = x.value;
  136. 				if(x.rank == y.rank) {
  137. 					x.rank++;
  138. 				}
  139. 			}
  140. 		}
  141.  
  142. 		private class Element {
  143. 			final int value;
  144. 			int parent;
  145. 			int rank;
  146.  
  147. 			private Element(int v) {
  148. 				value = v;
  149. 				parent = v;
  150. 				rank = 0;
  151. 			}
  152.  
  153. 			boolean isRoot() {
  154. 				return parent == value;
  155. 			}
  156. 		}
  157. 	}
  158.  
  159. }
  160.  
Success #stdin #stdout 0.05s 213440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0, 3, 5
2, 4, 5
3, 5, 6
0, 1, 7
1, 4, 7
4, 6, 9
cost : 39
https://ideone.com/3vtvW
language:
Java (HotSpot 12)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!