????本篇文章介紹業(yè)界的一些經(jīng)典算法。如果算法較長，會省略掉Kotlin版本。
(1)最大子序列和算法
????這里給出四種最大子序列和算法。它們的時間復(fù)雜度依次降低。
????第一種，Java版本：
/**
* O(N的三次方)
*/
public static int maxSubSum1(int[] a) {
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int thisSum = 0;
for (int k = i; k <= j; k++) {
thisSum += a[k];
}
if (maxSum < thisSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
????Kotlin版本：
fun maxSubSum1(a: IntArray): Int {
var maxSum = 0
for (i in a.indices) {
for (j in i until a.size) {
var thisSum = 0
for (k in i..j) {
thisSum += a[k]
}
if (maxSum < thisSum) {
maxSum = thisSum
}
}
}
return maxSum
}
????第二種，Java版本
/**
* O(N的二次方)
*/
public static int maxSubSum2(int[] a) {
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
int thisSum = 0;
for (int j = i; j < a.length; j++) {
thisSum += a[j];
if (maxSum < thisSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
????Kotlin版本：
/**
* O(N的二次方)
*/
fun maxSubSum2(a: IntArray): Int {
var maxSum = 0
for (i in a.indices) {
var thisSum = 0
for (j in i until a.size) {
thisSum += a[j]
if (maxSum < thisSum) {
maxSum = thisSum
}
}
}
return maxSum
}
????第三種，采用分治思想實現(xiàn)。Java版本：
public static int maxSubSum3(int[] a) {
return maxSumRec(a, 0, a.length - 1);
}
/**
* O(N logN)
* 分治思想：最大子序列和位于：（1）輸入數(shù)據(jù)的左半部分；（2）右半部分；（3）跨越中部位于左右兩半部分之間。
* 左右部分可以遞歸求解
*/
public static int maxSumRec(int[] a, int left, int right) {
int maxSum = 0;
if (left == right) {
if (a[left] > maxSum) {
maxSum = a[left];
}
return maxSum;
}
int middle = (left + right) / 2;
int maxLeftSum = maxSumRec(a, left, middle);
int maxRightSum = maxSumRec(a, middle + 1, right);
int leftSum = 0, tmpLeftSum = 0;
for (int i = middle; i >= 0; i--) {
tmpLeftSum += a[i];
if (tmpLeftSum > leftSum) {
leftSum = tmpLeftSum;
}
}
int rightSum = 0, tmpRightSum = 0;
for (int i = middle + 1; i <= right; i++) {
tmpRightSum += a[i];
if (rightSum < tmpRightSum) {
rightSum = tmpRightSum;
}
}
if (maxLeftSum > maxRightSum) {
maxSum = maxLeftSum;
} else {
maxSum = maxRightSum;
}
if (maxSum < (leftSum + rightSum)) {
maxSum = leftSum + rightSum;
}
return maxSum;
}
????Kotlin版本：
fun maxSubSum3(a: IntArray): Int {
return maxSumRec(a, 0, a.size - 1)
}
/**
* O(N logN)
* 分治思想：最大子序列和位于：（1）輸入數(shù)據(jù)的左半部分；（2）右半部分；（3）跨越中部位于左右兩半部分之間。
* 左右部分可以遞歸求解
*/
fun maxSumRec(a: IntArray, left: Int, right: Int): Int {
var maxSum = 0
if (left == right) {
if (a[left] > maxSum) {
maxSum = a[left]
}
return maxSum
}
val middle = (left + right) / 2
val maxLeftSum = maxSumRec(a, left, middle)
val maxRightSum = maxSumRec(a, middle + 1, right)
var leftSum = 0
var tmpLeftSum = 0
for (i in middle downTo 0) {
tmpLeftSum += a[i]
if (tmpLeftSum > leftSum) {
leftSum = tmpLeftSum
}
}
var rightSum = 0
var tmpRightSum = 0
for (i in middle + 1..right) {
tmpRightSum += a[i]
if (rightSum < tmpRightSum) {
rightSum = tmpRightSum
}
}
maxSum = if (maxLeftSum > maxRightSum) {
maxLeftSum
} else {
maxRightSum
}
if (maxSum < leftSum + rightSum) {
maxSum = leftSum + rightSum
}
return maxSum
}
????第四種，主要思想：不需要知道具體的最佳子序列在哪里；如果a[i]是負值，那么它不可能代表最優(yōu)序列的起點，因為任何包含a[i]作為起點的子序列都可以通過用a[i+1]來得到改進；類似的，任何負的子序列不可能是最優(yōu)子序列的前綴，原理相同.
????Java版本：
/**
* O(N)
*/
public static int maxSubSum4(int[] a) {
int maxSum = 0;
int thisSum = 0;
for (int i = 0; i < a.length; i++) {
thisSum += a[i];
if (thisSum > maxSum) {
maxSum = thisSum;
} else if (thisSum < 0) {
thisSum = 0;
}
}
return maxSum;
}
????Kotlin版本：
fun maxSubSum4(a: IntArray): Int {
var maxSum = 0
var thisSum = 0
for (i in a.indices) {
thisSum += a[i]
if (thisSum > maxSum) {
maxSum = thisSum
} else if (thisSum < 0) {
thisSum = 0
}
}
return maxSum
}
(2) 霍夫曼編碼
????霍夫曼編碼(Huffman)編碼是為了解決如何構(gòu)造一種特殊的編碼樹而設(shè)計的編碼方案。在介紹它之前，先來了解一下文件壓縮。
????這里說的文件壓縮，是指無損壓縮，可以解壓還原。對于一些比較大的文件，如果可以無損壓縮它，不僅能節(jié)省存儲空間，進行網(wǎng)絡(luò)傳輸時還能更快。一種想法是采用變長編碼，出現(xiàn)頻繁的字符采用較短的編碼，從而達到壓縮的目的。實現(xiàn)這種想法所采用的數(shù)據(jù)結(jié)構(gòu)是滿二叉樹(若不是，通過增加或刪除非葉節(jié)點來滿足)，樹中只有葉子節(jié)點有數(shù)據(jù)(字符)。從根節(jié)點開始，通往每個葉子節(jié)點時，用0表示左分支，1表示右分支，這樣就可以得到相應(yīng)的路徑，這個路徑就是該字符的編碼。這里有一個關(guān)鍵問題是：任何字符的編碼，不能是其他字符編碼的前綴，否則就分不清了。哈夫曼編碼就是滿足所有條件的一種解決方案。
????主要思路：假設(shè)字符個數(shù)為C，開始時，每個字符都看作是包含一個元素的樹，所有的字符就組成了一個森林；一顆樹的權(quán)等于它所有的樹葉頻率之和；任意選取最小權(quán)的樹T1、T2，將它們合并為一個新樹，T1、T2作為新樹的葉子節(jié)點；將這樣的過程進行(C-1)次，就得到了Huffman編碼樹。
????舉例說明，假設(shè)一個文件由“天”、“地”、“人”三字組成(亂序)，出現(xiàn)次數(shù)分別為3w、2w、1w，三字對應(yīng)的Huffman編碼依次是“1”、"01"、“00”(比特，位)。如果以一個漢字占2字節(jié)來計算，那么壓縮前需要的空間：12w字節(jié)= 117 KB。壓縮后的空間：10w 比特 = 12 KB?？梢钥吹?，效果明顯。只要解壓縮一方知道編碼方案，就可以解壓還原了。
????Java實現(xiàn)：
/**
* 霍夫曼算法
*/
public class Hufman {
//huffman編碼方案
static Map<Character, String> huffmanCodes = new HashMap<>();
class Node implements Comparable<Node> {
Character data;//存放字符
int weight; //權(quán)值
Node leftChild; //左孩子
Node rightChild; //右孩子
public Node(Character data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
/**
* 從輸入中，構(gòu)造所有的節(jié)點
*
* @param content
* @return
*/
List<Node> getNodes(String content) {
List<Node> nodeList = new ArrayList<>();
if (content != null && content.length() > 0) {
char[] chars = content.toCharArray();
Map<Character, Integer> nodeWeightMap = new HashMap<>();
for (char charTmp : chars) {
Integer count = nodeWeightMap.get(charTmp);
if (count == null) {
nodeWeightMap.put(charTmp, 1);
} else {
nodeWeightMap.put(charTmp, ++count);
}
}
Set<Character> keySet = nodeWeightMap.keySet();
for (Character key : keySet) {
Node node = new Node(key, nodeWeightMap.get(key));
nodeList.add(node);
}
}
return nodeList;
}
/**
* 創(chuàng)建Huffman樹
*
* @param nodeList
* @return
*/
Node createHuffmanTree(List<Node> nodeList) {
while (nodeList.size() > 1) {
Collections.sort(nodeList);
Node left = nodeList.remove(0);
Node right = nodeList.remove(0);
Node parent = new Node(null, left.weight + right.weight);
parent.leftChild = left;
parent.rightChild = right;
nodeList.add(parent);
}
return nodeList.get(0);
}
/**
* 為每個葉子節(jié)點，創(chuàng)建huffman編碼
*
* @param node 節(jié)點
* @param doneCode 已完成的huffman編碼，用于拼接
*/
void createHuffmanCode(Node node, String doneCode) {
if (node != null) {
if (node.data == null) { //非葉節(jié)點
createHuffmanCode(node.leftChild, doneCode +"0");
createHuffmanCode(node.rightChild, doneCode +"1");
} else { //葉子節(jié)點
huffmanCodes.put(node.data, doneCode);
}
}
}
public static void main(String[] args) {
Hufman hufman = new Hufman();
String content = "aabbbbbbccc中中中中???????";
List<Node> nodeList = hufman.getNodes(content);
Node rootNode = hufman.createHuffmanTree(nodeList);
hufman.createHuffmanCode(rootNode, "");
System.out.println(huffmanCodes);
}
}
????輸出編碼方案：
{?=11, a=010, b=10, c=011, 中=00}
????本示例中，是可以處理常用中文字符的?；蛘哒f，可以處理位于BMP(基本多文種平面)中的中文漢字，數(shù)量大概有2W+，是一些常用的漢字。對于其他平面的漢字，是不支持的。emoji等因為不在BMP中，所以也不支持。
????漢字的數(shù)量遠超英文字符，有7W+，常用的有2W+。所以，對于包含很多漢字的大文件來說，霍夫曼樹是非常龐大的。算法的耗時估計不容樂觀。但考慮到這個算法是1955年提出的，只考慮英文字母的情況下，最多26+26=52字符加上標點符號，還是非常合適的。
????Huffman編碼到現(xiàn)在還沒有過時，gzip壓縮算法就是將它和另外一個壓縮算法LZ77組合起來的。LZ77算法是1977年提出的，L、Z分別代表2個作者，這里不做擴充了。
????上面說到，本示例中可以處理中文。網(wǎng)上、書上不少版本，是不支持處理中文的。這里做一些說明。請看構(gòu)造節(jié)點時getNodes()方法里的這一句：
char[] chars = content.toCharArray();
???? 后面的處理都是基于char類型的，Java中的char類型，占2個字節(jié)，包含了BMP中所有的字符。所以，它能處理常見的中文字符，但不能處理非BMP字符。
???? 如果將上面這一句，改為byte[]的方式，后續(xù)的也做相應(yīng)修改，那么就不能處理任何中文字符了，如下：
byte[] bytes = content.getBytes();
???? 在網(wǎng)絡(luò)傳輸?shù)膱鼍爸?，一般都處理的字?jié)byte，此時，如果想處理常見中文字符，那么可以將InputStream轉(zhuǎn)換為InputStreamReader，然后以char的方式處理。
???? 讓我們再進一步，如果確實要處理非BMP字符，該怎么修改？在一些emoji表情的場景和非常見漢字，還是可能遇到的。這里簡單說一下思路。
???? 在基于char的處理上，對獲取的每個char，做一下判斷。Character中有個方法isHighSurrogate()，可以判斷當前char是否是高位代理，如果是，表明這個char字符是非BMP平面某個字符的一半，接著可以獲取下個字符，然后將兩者組合成一個新字符。當然，此時不能再用char來表示，因為超出了char的表示范圍，而必須用字符串String。所以相應(yīng)的數(shù)據(jù)類型也要改變。組成新的字符串方式如下：
???? char highSur = ...;
???? char lowSur = ...;
???? char[] chars = {highSur,lowSur};
???? String highLowStr = new String(chars);
????注意，高位在前，低位在后。
????從上面的過程可以知道，每個壓縮文件對應(yīng)的霍夫曼編碼都不一樣。類似這種特點的編碼稱為動態(tài)編碼，有動即有靜，靜態(tài)編碼是指保持不變的編碼。靜態(tài)編碼是更常見的，如UTF-8、UTF-16、GBK等?；舴蚵幋a也有靜態(tài)版的，但適用性就沒那么強了。
????霍夫曼編碼屬于“貪婪算法”這一類型，它的特點是分階段地工作，“眼下能拿到的就拿”，形成局部最優(yōu)。在構(gòu)造霍夫曼樹時，每次都選擇權(quán)值最小的2個樹進行合并，獲得局部最優(yōu)解，直至構(gòu)造完成。
(3)Dijkstra算法
????Dijkstra(迪克斯特拉)算法是圖論中一種解決單源最短路徑問題的算法，是貪婪算法中的一種。
????主要思想：從源點S出發(fā)，按階段進行，每個階段，選擇一個鄰接新頂點(未被訪問過)，使得S到它的距離最短。
????本小節(jié)將介紹兩種實現(xiàn)方式，一種是使用鄰接矩陣，一種是使用優(yōu)先隊列。
????先來看看鄰接矩陣的方式，使用了《09_算法基本概念》中的圖結(jié)構(gòu)。Java版本如下：
/**
* Dijkstra算法
*/
public class Dijkstra {
//一般的圖結(jié)構(gòu)
class Graph {
static final int NUM = 10; //圖的最大頂點數(shù)
char[] vertex = new char[NUM]; //頂點集合
int vertexNum;//實際頂點數(shù)量
int[][] edgeWeight = new int[NUM][NUM]; //鄰接矩陣,含權(quán)
boolean[] isTrav = new boolean[NUM]; //是否訪問的標志
}
/***
* 在未訪問的連通頂點中，找到一個距離最小的，返回下標。
*
* 只看這個方法的話，是不能確定找到的這個頂點與已選擇的頂點是連通的。
* 但結(jié)合上文來看，初始化時，已設(shè)置了源點到自身的距離是0，也即distArray數(shù)組中有一項是0。
* 而這個原點并未設(shè)置成已訪問的，所以這個方法在第一次調(diào)用時返回的下標就是源點下標。
* 從下文來看，隨后會更新與該頂點有連通的頂點距離放到distArray數(shù)組中，
* 后續(xù)對該方法的調(diào)用，其實就是在連通頂點中選擇最小值。
*
* @param graph 圖
* @param distArray 已選擇的頂點距離數(shù)組
* @return
*/
int minDist(Graph graph, int[] distArray) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < graph.vertexNum; j++) {
if (!graph.isTrav[j] && distArray[j] <= min ) {
min = distArray[j];
minIndex = j;
}
}
return minIndex;
}
/**
* Dijkstra算法實現(xiàn)
*
* @param srcVertex 源頂點
* @param graph 圖結(jié)構(gòu)
*/
void dijkstra(char srcVertex, Graph graph) {
//各個頂點到源頂點的最小距離
int[] distArray = new int[graph.vertexNum];
//初始化
for (int i = 0; i < graph.vertexNum; i++) {
distArray[i] = Integer.MAX_VALUE;
}
//獲取源頂點的下標
int srcIndex = getSrcIndex(srcVertex, graph);
distArray[srcIndex] = 0;//到自己的距離永遠為0
for (int i = 0; i < graph.vertexNum - 1; i++) {
int uIndex = minDist(graph, distArray);
graph.isTrav[uIndex] = true;
//處理當前頂點的鄰接頂點，更新未選中頂點的距離
for (int j = 0; j < graph.vertexNum; j++) {
if (!graph.isTrav[j] && graph.edgeWeight[i][j] != 0 && distArray[uIndex] != Integer.MAX_VALUE
&& distArray[uIndex] + graph.edgeWeight[uIndex][j] < distArray[j] ) {
distArray[j] = distArray[uIndex] + graph.edgeWeight[uIndex][j];
}
}
}
//打印最小距離
printMinDist(distArray, srcVertex ,graph);
}
void printMinDist(int[] distArray, char srcVertex,Graph graph) {
System.out.println("源點是："+srcVertex);
System.out.println("頂點 \t到源點的最短距離");
for (int i = 0; i < distArray.length; i++)
System.out.println(graph.vertex[i] + " \t\t" + distArray[i]);
}
/**
* 找到指定頂點在圖中的下標index
*
* @param srcVertex
* @param graph
* @return
*/
int getSrcIndex(char srcVertex, Graph graph) {
int index = -1;
for (int i = 0; i < graph.vertexNum; i++) {
if (graph.vertex[i] == srcVertex) {
index = i;
break;
}
}
return index;
}
public static void main(String[] args) {
Dijkstra dijkstra = new Dijkstra();
char src = 'A';
Graph graph = dijkstra.createGraph(src);
dijkstra.dijkstra(src,graph);
}
/**
* 構(gòu)造一個圖
* @param src 頂點
* @return
*/
private Graph createGraph(char src) {
Graph graph = new Graph();
graph.vertexNum = 6;
graph.edgeWeight= new int[][]{
{0, 1, 3, 0, 0, 0},
{1, 0, 0, 4, 0, 0},
{3, 0, 0, 0, 2, 0},
{0, 4, 0, 0, 0, 10},
{0, 0, 2, 0, 0, 9},
{0, 0, 0, 10, 9, 0}};
graph.vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F'};
return graph;
}
}
????上面算法構(gòu)造的圖如下：
????輸出結(jié)果：
源點是：A
頂點????到源點的最短距離
A???????0
B???????1
C???????3
D???????5
E???????5
F???????14
????再來介紹優(yōu)先隊列的方式。在上面的代碼中，找到一個與已訪問頂點的最小連通頂點，是通過方法minDist()來實現(xiàn)的。而獲取最小者，這非常符合優(yōu)先隊列的特點。優(yōu)先隊列是刪除最小者，但刪除的同時，也獲得了這個最小者。因此，可以通過優(yōu)先隊列來處理。Java版本：
/**
* PriorityQueue實現(xiàn)Dijkstra算法
*/
public class DijkstraPQ {
/**
* 節(jié)點Node，如A、B、C等
*/
static class Node implements Comparator<Node> {
char aChar; //頂點名稱
int weight; //權(quán)值
public Node() {
}
public Node(char aChar, int weight) {
this.aChar = aChar;
this.weight = weight;
}
@Override
public int compare(Node node1, Node node2) {
return node1.weight - node2.weight;
}
}
int distArray[];
PriorityQueue<Node> priorityQueue;
Set<Character> visited;
int vertexNum;//頂點總數(shù)
List<List<Node>> adjList;//鄰接矩陣，改用List來表示，上面是用二維數(shù)組
List<Character> charList;//所有的節(jié)點list
public DijkstraPQ(int vertexNum) {
this.vertexNum = vertexNum;
distArray = new int[vertexNum];
visited = new HashSet<>();
priorityQueue = new PriorityQueue<Node>(vertexNum, new Node());
charList = new ArrayList<>();
}
void dijkstra(List<List<Node>> adjList, char srcVertex) {
this.adjList = adjList;
for (int i = 0; i < vertexNum; i++) {
distArray[i] = Integer.MAX_VALUE;
}
priorityQueue.add(new Node(srcVertex, 0)); //將源點加入優(yōu)先隊列
int srcIndex = getNodeIndex(srcVertex);
distArray[srcIndex] = 0; //源點到自身的權(quán)值為0
while (visited.size() != vertexNum) {
Node node = priorityQueue.remove(); //距離最小的Node
visited.add(node.aChar);
int index = getNodeIndex(node.aChar);
for (int i = 0; i < adjList.get(index).size(); i++) {
Node tmpNode = adjList.get(index).get(i);
int tmpIndex = getNodeIndex(tmpNode.aChar);
if (!visited.contains(tmpNode.aChar)) {
int newDist = distArray[index] + tmpNode.weight;
if (newDist < distArray[tmpIndex]) {
distArray[tmpIndex] = newDist;
}
priorityQueue.add(new Node(tmpNode.aChar, distArray[tmpIndex]));
}
}
}
printResults(srcVertex);
}
void printResults(char srcChar) {
System.out.println("源點是：" + srcChar);
System.out.println("頂點 \t到源點的最短距離");
for (int i = 0; i < distArray.length; i++)
System.out.println(charList.get(i) + " \t\t" + distArray[i]);
}
/**
* 獲取下標
*
* @return
*/
int getNodeIndex(char aChar) {
int index = -1;
for (int i = 0; i < charList.size(); i++) {
if (aChar == charList.get(i)) {
index = i;
break;
}
}
return index;
}
public static void main(String[] args) {
int num = 6;
char srcChar = 'A';
DijkstraPQ dijkstraTwo = new DijkstraPQ(6);
dijkstraTwo.charList.add('A');
dijkstraTwo.charList.add('B');
dijkstraTwo.charList.add('C');
dijkstraTwo.charList.add('D');
dijkstraTwo.charList.add('E');
dijkstraTwo.charList.add('F');
List<List<Node>> adjList = new ArrayList<List<Node>>();
for (int i = 0; i < num; i++) {
List<Node> item = new ArrayList<>();
adjList.add(item);
}
//鄰接矩陣
adjList.get(0).add(new Node('B',1));
adjList.get(0).add(new Node('C',3));
adjList.get(1).add(new Node('A',1));
adjList.get(1).add(new Node('D',4));
adjList.get(2).add(new Node('A',3));
adjList.get(2).add(new Node('E',2));
adjList.get(3).add(new Node('B',4));
adjList.get(3).add(new Node('F',10));
adjList.get(4).add(new Node('C',2));
adjList.get(4).add(new Node('F',9));
adjList.get(5).add(new Node('D',10));
adjList.get(5).add(new Node('E',9));
dijkstraTwo.dijkstra(adjList,srcChar);
}
}
????鄰接矩陣的數(shù)據(jù)，仍然是基于上面的構(gòu)造圖。輸出結(jié)果也和上面是一致的。
????List<List<>>表示的鄰接矩陣，開始不那么容易理解。以這條語句為例來進行說明：
adjList.get(0).add(new Node('B',1));
它表示頂點'A'到頂點'B'的連接(有方向)，權(quán)值是1；等價的二維數(shù)組表示法：edgeWeight[0][1] = 1;
頂點是按照一定的順序確定好的。0對應(yīng)著'A'，'B'對應(yīng)著1。
adjList.get(1).add(new Node('A',1));
這行代碼表示'B'到'A'有一條連接，權(quán)值也是1。等價的二維數(shù)組表示法：edgeWeight[1][0] = 1;
這是因為使用的構(gòu)造圖是無方向的，正反都得來一次。
????List<List<>>形式表示的鄰接矩陣，在表示有向圖時非常方便。一個Node代表著一條帶箭頭的邊。而表示無向圖時，顯然二維數(shù)組要更方便，沿著對角線(左上到右下)是完全對稱的。這兩種表示方式可以相互替換，稍加改動即可。
????此外，基于優(yōu)先隊列的這種特點，前面一小節(jié)(2)霍夫曼編碼在選取兩個權(quán)值最小的樹時，也可以考慮使用優(yōu)先隊列來實現(xiàn)，不過在此就不展開了。
(4)Prim算法
????Prim算法是圖論中找出最小生成樹的一種算法。最小生成樹的概念可以去《09_算法基本概念》復(fù)習一遍。
????基本思想：它和Dijstra算法有很大的相似性；初始時，隨機選擇一個頂點作為最小生成樹的根；接著選擇到生成樹權(quán)值最小的連通頂點，這一過程和Dijstra算法一樣；直到所有的頂點都處理完為止。
????Java實現(xiàn)：
/**
* Prim算法：最小生成樹算法
*/
public class Prim {
//一般的圖結(jié)構(gòu)
class Graph {
static final int NUM = 10; //圖的最大頂點數(shù)
char[] vertex = new char[NUM]; //頂點集合
int vertexNum;//實際頂點數(shù)量
int gType = 0; //無向圖
int[][] edgeWeight = new int[NUM][NUM]; //鄰接矩陣,含權(quán)
boolean[] isTrav = new boolean[NUM]; //是否訪問的標志
}
/**
* prim算法
*
* @param graph 原始圖
* @return 最小生成樹組成的圖
*/
Graph prim(Graph graph) {
Graph resultG = new Graph(); //目標最小生成樹，用圖結(jié)構(gòu)表示
resultG.vertex = graph.vertex; //最終頂點是一樣的
resultG.vertexNum = graph.vertexNum; //最終頂點數(shù)量也是一樣的
int[] distArray = new int[graph.vertexNum]; //各未選頂點到最小生成樹的最小距離
int[] mstIndexArray = new int[graph.vertexNum];//各未選頂點連接到最小生成樹頂點的下標
for (int i = 0; i < distArray.length; i++) { //初始值設(shè)為最大
distArray[i] = Integer.MAX_VALUE;
}
//任選一點作為起始頂點
distArray[0] = 0;//到自己的距離為0
for (int i = 0; i < graph.vertexNum; i++) {
//找到一個權(quán)值最小的頂點
int minIndex = minDist(graph, distArray);
graph.isTrav[minIndex] = true;
for (int j = 0; j < graph.vertexNum; j++) {
if (!graph.isTrav[j] && graph.edgeWeight[minIndex][j] != 0 && graph.edgeWeight[minIndex][j] < distArray[j]) {
distArray[j] = graph.edgeWeight[minIndex][j];
mstIndexArray[j] = minIndex;
resultG.edgeWeight[minIndex][j] = graph.edgeWeight[minIndex][j];
}
}
}
printResult(graph, mstIndexArray);
return resultG;
}
private void printResult(Graph graph, int[] mstIndexArray) {
System.out.println("頂點對\t\t\t\t權(quán)值");
for (int i = 0; i < graph.vertexNum; i++) {
int mstIndex = mstIndexArray[i];
if (i != mstIndex && graph.edgeWeight[i][mstIndex] != 0) {
System.out.println(graph.vertex[mstIndex] + " <------> " + graph.vertex[i] + "\t\t" + graph.edgeWeight[i][mstIndex]);
}
}
}
/**
* 在未訪問的連通頂點中，找到一個距離最小的，返回下標。
*
* @param graph 源圖
* @return
*/
private int minDist(Graph graph, int[] distArray) {
int min = Integer.MAX_VALUE;
int minIndex = -1;
for (int j = 0; j < graph.vertexNum; j++) {
if (!graph.isTrav[j] && distArray[j] <= min) {
min = distArray[j];
minIndex = j;
}
}
return minIndex;
}
public static void main(String[] args) {
Prim prim = new Prim();
Graph graph = prim.createGraph();
Graph resultG = prim.prim(graph);
System.out.println("頂點對\t\t\t\t權(quán)值");
for (int i = 0; i < resultG.vertexNum; i++) {
for (int j = i + 1; j < resultG.vertexNum; j++) {
if (resultG.edgeWeight[i][j] != 0) {
System.out.println(resultG.vertex[i] + " <------> " + resultG.vertex[j] + "\t\t" + resultG.edgeWeight[i][j]);
}
}
}
}
/**
* 構(gòu)造一個圖
*
* @return
*/
Graph createGraph() {
Graph graph = new Graph();
graph.vertexNum = 6;
graph.edgeWeight = new int[][]{
{0, 1, 3, 0, 0, 0},
{1, 0, 0, 4, 0, 0},
{3, 0, 0, 0, 2, 0},
{0, 4, 0, 0, 0, 10},
{0, 0, 2, 0, 0, 9},
{0, 0, 0, 10, 9, 0}};
graph.vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F'};
return graph;
}
}
????輸出結(jié)果：
頂點對??????????權(quán)值
A <------> B????1
A <------> C????3
B <------> D????4
C <------> E????2
E <------> F????9
頂點對??????????權(quán)值
A <------> B????1
A <------> C????3
B <------> D????4
C <------> E????2
E <------> F????9
????這里輸出了二次，結(jié)果都一樣。主要是為了對比，前一次是使用各頂點連接到最小生成樹的頂點下標數(shù)組來輸出的；后一次是使用prim()方法的返回值，即用圖結(jié)構(gòu)表示的最小生成樹，然后在此基礎(chǔ)上輸出的，這個返回值也可以不需要，只是為了獲得一顆最小生成樹而已。
????它和Dijkstra算法的主要區(qū)別一是需要多記錄各頂點到生成樹的頂點下標，其次是更新未選頂點的距離時，只需權(quán)值即可，不再加上已選頂點的距離。對比如下：
dijkstra算法，需要加上已選頂點距離：
distArray[j] = distArray[minIndex] + graph.edgeWeight[minIndex][j];
而prim算法，只需要計算權(quán)值：
distArray[j] = graph.edgeWeight[minIndex][j];
????此外，既然是樹，那么如果想用樹結(jié)構(gòu)來表示呢？也是可以的。轉(zhuǎn)換如下：
/**
* 將圖結(jié)構(gòu)表示的最小生成樹，轉(zhuǎn)為樹結(jié)構(gòu)表示的
*
* @param graph 圖
* @return 樹
*/
Node convert(Graph graph) {
Node[] allNodes = new Node[graph.vertexNum];
for (int i = 0; i < graph.vertexNum; i++) {
Node tmpNode = new Node(graph.vertex[i]);
if (i==0){
tmpNode.weight = 0;//根節(jié)點沒有父節(jié)點，權(quán)值置0
}
allNodes[i] = tmpNode;
}
for (int i = 0; i < graph.vertexNum - 1; i++) {
for (int j = i + 1; j < graph.vertexNum; j++) {
if (graph.edgeWeight[i][j] != 0) {//i到j(luò)有連接
Node iNode = allNodes[i];
Node jNode = allNodes[j];
jNode.weight = graph.edgeWeight[i][j];
iNode.addChildNode(jNode);//添加為子節(jié)點
}
}
}
return allNodes[0];
}
class Node {
char aChar; //節(jié)點名
List<Node> childNodes; //所有的孩子節(jié)點
int weight;//到父節(jié)點的權(quán)值
public Node(char aChar) {
childNodes = new ArrayList<Node>();
this.aChar = aChar;
}
public void addChildNode(Node childNode) {
childNodes.add(childNode);
}
}
????需要注意的是，這個最小生成樹不一定是常見的二叉樹。每個節(jié)點的子節(jié)點數(shù)是不定的。
(5)Kruskal算法
????Kruskal算法也是一種找出最小生成樹的算法。
????主要思想：依次選一條權(quán)值最小的邊，如果沒有產(chǎn)生回路，就加入到最小生成樹中；如果產(chǎn)生回路，執(zhí)行下一次循環(huán)；這個過程執(zhí)行(n-1)次，就獲得了需要的最小生成樹。
????分析：可以看到，選擇新的一條邊時，是否形成了循環(huán)，就是關(guān)鍵所在；這里需要用到“不相交集”的概念，在開始時，將所有節(jié)點都看作互不相交的子集，每個節(jié)點的父節(jié)點是自身；如果從 i 到 j 有一條邊，那么將 i 和 j合并成一個集合，并使得 i 是 j 的父親節(jié)點；處理后續(xù)的邊時，只要兩節(jié)點的父節(jié)點不同，說明它們不在同一個集合里，就不會形成回路。
????Java實現(xiàn)：
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
/**
* 使用優(yōu)先隊列的Kruskal算法
*/
public class KruskalPQ {
//一般的圖結(jié)構(gòu)
class Graph {
static final int NUM = 10; //圖的最大頂點數(shù)
char[] vertex = new char[NUM]; //頂點集合
int vertexNum;//實際頂點數(shù)量
int gType = 0; //0表示無向圖，1表示有向圖
int[][] edgeWeight = new int[NUM][NUM]; //鄰接矩陣,含權(quán)
boolean[] isTrav = new boolean[NUM]; //是否訪問的標志
}
/**
* 圖中的邊
*/
class Edge {
int srcIndex; //起始位置
int endIndex; //結(jié)束位置
int weight; //權(quán)值
}
class Subset { // 不相交集
int fatherIndex;//父節(jié)點的下標
int rank; //合并兩個不相交集時的依據(jù)
}
PriorityQueue<Edge> priorityQueue;
public KruskalPQ() {
priorityQueue = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
}
/**
* 找到index= i的節(jié)點的父節(jié)點
*
* @param subsets
* @param i
* @return
*/
int find(Subset[] subsets, int i) {
if (subsets[i].fatherIndex != i) { //不相等，說明當前節(jié)點設(shè)置了父節(jié)點，繼續(xù)查找父節(jié)點
subsets[i].fatherIndex = find(subsets, subsets[i].fatherIndex);
return subsets[i].fatherIndex;
} else {
return i; //相等，返回自身
}
}
/**
* 將x、y節(jié)點合并到一個集合，使得它們的fatherIndex相同
*
* @param subsets
* @param x
* @param y
*/
void union(Subset[] subsets, int x, int y) {
int xRoot = find(subsets, x);
int yRoot = find(subsets, y);
if (subsets[xRoot].rank < subsets[yRoot].rank) {
subsets[xRoot].fatherIndex = yRoot;
} else if (subsets[xRoot].rank > subsets[yRoot].rank) {
subsets[yRoot].fatherIndex = xRoot;
} else { //如果rank相等，使其中一個成為root，rank加1
subsets[yRoot].fatherIndex = xRoot;
subsets[xRoot].rank++;
}
}
Graph kruskal(Graph g) {
Graph resultG = new Graph(); //目標最小生成樹，用圖結(jié)構(gòu)表示
resultG.vertex = g.vertex; //最終頂點是一樣的
resultG.vertexNum = g.vertexNum; //最終頂點數(shù)量也是一樣的
addAllEdges(g); //添加所有的邊
Subset[] subsets = new Subset[g.vertexNum];
for (int i = 0; i < subsets.length; i++) {
Subset tmpSubset = new Subset();
tmpSubset.fatherIndex = i; //初始時，fatherIndex設(shè)置為自己
tmpSubset.rank = 0;
subsets[i] = tmpSubset;
}
List<Edge> selectedEdgeList = new ArrayList<>();//最小生成樹選擇的邊
for (int i = 0; i < g.vertexNum - 1; i++) {
Edge smallEdge = priorityQueue.remove(); //獲得權(quán)值最小的一條邊
int x = find(subsets, smallEdge.srcIndex);
int y = find(subsets, smallEdge.endIndex);
if (x != y) {//不相等，說明不存在環(huán)
selectedEdgeList.add(smallEdge);
resultG.edgeWeight[smallEdge.srcIndex][smallEdge.endIndex] = smallEdge.weight;
union(subsets, x, y);
}
}
System.out.println("(邊)頂點對\t\t\t\t權(quán)值");
for (Edge edge : selectedEdgeList) {
System.out.println(g.vertex[edge.srcIndex] + " <------> " + g.vertex[edge.endIndex] + "\t\t" + g.edgeWeight[edge.srcIndex][edge.endIndex]);
}
return resultG;
}
//將所有的邊加入到PriorityQueue中
private void addAllEdges(Graph g) {
int limit = 0;
for (int i = 0; i < g.vertexNum-1; i++) {
if (g.gType == 0) { //無向圖，只處理一半
limit = i + 1;
}
for (int j = limit; j < g.vertexNum; j++) {
if (g.edgeWeight[i][j] != 0) {
Edge edge = new Edge();
edge.weight = g.edgeWeight[i][j];
edge.srcIndex = i;
edge.endIndex = j;
priorityQueue.add(edge);
}
}
}
}
/**
* 構(gòu)造一個圖
*
* @return
*/
Graph createGraph() {
Graph graph = new Graph();
graph.vertexNum = 6;
graph.edgeWeight = new int[][]{
{0, 1, 3, 0, 0, 0},
{1, 0, 0, 4, 0, 0},
{3, 0, 0, 0, 2, 0},
{0, 4, 0, 0, 0, 10},
{0, 0, 2, 0, 0, 9},
{0, 0, 0, 10, 9, 0}};
graph.vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F'};
return graph;
}
public static void main(String[] args) {
KruskalPQ kruskalPQ = new KruskalPQ();
Graph graph = kruskalPQ.createGraph();
Graph resultG = kruskalPQ.kruskal(graph);
System.out.println("頂點對\t\t\t\t權(quán)值");
for (int i = 0; i < resultG.vertexNum; i++) {
for (int j = i + 1; j < resultG.vertexNum; j++) {
if (resultG.edgeWeight[i][j] != 0) {
System.out.println(resultG.vertex[i] + " <------> " + resultG.vertex[j] + "\t\t" + resultG.edgeWeight[i][j]);
}
}
}
}
}
????輸出：
(邊)頂點對????????權(quán)值
A <------> B??????1
C <------> E??????2
A <------> C??????3
B <------> D??????4
E <------> F??????9
頂點對???????????權(quán)值
A <------> B??????1
A <------> C??????3
B <------> D??????4
C <------> E??????2
E <------> F??????9
????結(jié)果是一致，只是輸出順序不同而已。上面的依據(jù)每次選擇的最小邊輸出，下面則是依據(jù)圖的頂點順序輸出。
????此外，這里非常適合使用PriorityQueue，每次只需要選擇權(quán)值最小的邊，而不管這條邊的頂點是否與已選頂點連通，這一點是與Prim算法非常不同的一個地方。如果不使用PriorityQueue，那么每次選最小邊時，就需要重新排序了。
????Over ！
