【資料結構】【圖論】【最小生成樹】Kruskal算法

一、Kruskal算法核心

1. Kruskal算法和Prime算法一樣也是計算最小生成樹的一種算法。考慮問題的出發點: 為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小。
2. 具體做法: 先構造一個隻含 n 個頂點的子圖 SG，然後從權值最小的邊開始，若它的添加不使SG 中産生回路，則在 SG 上加上這條邊，如此重複，直至加上 n-1 條邊為止。
3. 算法示範

 二、代碼實作（Java版）

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

class Edge {
	int node1;
	int node2;
	int edgeValue;
}

class MySort implements Comparator<Edge> {
	public int compare(Edge o1, Edge o2) {
		return o1.edgeValue > o2.edgeValue ? 1 : -1;
	}

}

public class Kruskal {
	static final int maxNodeValue = (1 << 31) - 1;

	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		Set<Edge> edges = new TreeSet<Edge>(new MySort());
		Map<Integer, Integer> preNode = new HashMap<Integer, Integer>();
		while (scanner.hasNext()) {
			int edgeCounts = scanner.nextInt();
			for (int i = 0; i < edgeCounts; i++) {
				int node1 = scanner.nextInt();
				int node2 = scanner.nextInt();
				int edgeValue = scanner.nextInt();
				Edge oldEdge = findOldEdge(node1, node2, edges);
				if (oldEdge != null) {
					if (oldEdge.edgeValue > edgeValue) {
						Edge edge = new Edge();
						edge.edgeValue = edgeValue;
						edge.node1 = node1;
						edge.node2 = node2;
						edges.add(edge);
					}
				} else {
					Edge edge = new Edge();
					edge.edgeValue = edgeValue;
					edge.node1 = node1;
					edge.node2 = node2;
					edges.add(edge);
				}
			}
			int cost = kruskal(edges, preNode);
			System.out.println(cost);
			edges.clear();
			preNode.clear();
		}
	}

	private static Edge findOldEdge(int node1, int node2, Set<Edge> edges) {
		Iterator<Edge> iterator = edges.iterator();
		while (iterator.hasNext()) {
			Edge edge = iterator.next();
			if ((edge.node1 == node1 && edge.node2 == node2) || (edge.node1 == node2 && edge.node2 == node1)) {
				return edge;
			}
		}
		return null;
	}

	public static int findRootNode(Integer node, Map<Integer, Integer> preNode) {
		while (preNode.get(node) != null) {
			node = preNode.get(node);
		}
		return node;
	}

	public static int kruskal(Set<Edge> edges, Map<Integer, Integer> preNode) {
		Iterator<Edge> it = edges.iterator();
		int cost = 0;
		while (it.hasNext()) {
			Edge edge = it.next();
			int node1 = edge.node1;
			int node2 = edge.node2;
			int edgeValue = edge.edgeValue;
			int node1_parent=findRootNode(node1, preNode) ;
			int node2_parent=findRootNode(node2, preNode);
			if (node1_parent!=node2_parent) {
				preNode.put(node1_parent, node2_parent);
				cost += edgeValue;
			}
		}
		return cost;
	}
}
           

 三、測試用例

輸入

11

1 2 19

1 5 14

1 7 18

2 3 5

2 4 7

2 5 12

3 4 3

4 5 8

4 6 21

5 7 16

6 7 27

輸出

67

 拓撲圖和算法篩選過程：

 四、ACM

題目連結：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2144

AC代碼：

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

class Edge {
	int node1;
	int node2;
	int edgeValue;
}

class MySort implements Comparator<Edge> {
	public int compare(Edge o1, Edge o2) {
		return o1.edgeValue > o2.edgeValue ? 1 : -1;
	}

}

public class Main{
	static final int maxNodeValue = (1 << 31) - 1;

	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		Set<Edge> edges = new TreeSet<Edge>(new MySort());
		Map<Integer, Integer> preNode = new HashMap<Integer, Integer>();
		while (scanner.hasNext()) {
			int nodeCounts = scanner.nextInt();
			int edgeCounts = scanner.nextInt();
			for (int i = 0; i < edgeCounts; i++) {
				int node1 = scanner.nextInt();
				int node2 = scanner.nextInt();
				int edgeValue = scanner.nextInt();
				Edge oldEdge = findOldEdge(node1, node2, edges);
				if (oldEdge != null) {
					if (oldEdge.edgeValue > edgeValue) {
						Edge edge = new Edge();
						edge.edgeValue = edgeValue;
						edge.node1 = node1;
						edge.node2 = node2;
						edges.add(edge);
					}
				} else {
					Edge edge = new Edge();
					edge.edgeValue = edgeValue;
					edge.node1 = node1;
					edge.node2 = node2;
					edges.add(edge);
				}
			}
			int cost = kruskal(edges, preNode);
			System.out.println(cost);
			edges.clear();
			preNode.clear();
		}
	}

	private static Edge findOldEdge(int node1, int node2, Set<Edge> edges) {
		Iterator<Edge> iterator = edges.iterator();
		while (iterator.hasNext()) {
			Edge edge = iterator.next();
			if ((edge.node1 == node1 && edge.node2 == node2) || (edge.node1 == node2 && edge.node2 == node1)) {
				return edge;
			}
		}
		return null;
	}

	public static int findRootNode(Integer node, Map<Integer, Integer> preNode) {
		while (preNode.get(node) != null) {
			node = preNode.get(node);
		}
		return node;
	}

	public static int kruskal(Set<Edge> edges, Map<Integer, Integer> preNode) {
		Iterator<Edge> it = edges.iterator();
		int cost = 0;
		while (it.hasNext()) {
			Edge edge = it.next();
			int node1 = edge.node1;
			int node2 = edge.node2;
			int edgeValue = edge.edgeValue;
			int node1_parent=findRootNode(node1, preNode) ;
			int node2_parent=findRootNode(node2, preNode);
			if (node1_parent!=node2_parent) {
				preNode.put(node1_parent, node2_parent);
				cost += edgeValue;
			}
		}
		return cost;
	}
}
           

        AC代碼和上面的代碼隻有一點不同，那就是輸入了節點的個數nodeCount，然而這個數在建立生成樹的過程中并沒有被使用到。