????本篇文章介绍业界的一些经典算法。如果算法较长，会省略掉Kotlin版本。
(1)最大子序列和算法
????这里给出四种最大子序列和算法。它们的时间复杂度依次降低。
????第一种，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
}
????第三种，采用分治思想实现。Java版本：
public static int maxSubSum3(int[] a) {
return maxSumRec(a, 0, a.length - 1);
}
/**
* O(N logN)
* 分治思想：最大子序列和位于：（1）输入数据的左半部分；（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）输入数据的左半部分；（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]是负值，那么它不可能代表最优序列的起点，因为任何包含a[i]作为起点的子序列都可以通过用a[i+1]来得到改进；类似的，任何负的子序列不可能是最优子序列的前缀，原理相同.
????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)编码是为了解决如何构造一种特殊的编码树而设计的编码方案。在介绍它之前，先来了解一下文件压缩。
????这里说的文件压缩，是指无损压缩，可以解压还原。对于一些比较大的文件，如果可以无损压缩它，不仅能节省存储空间，进行网络传输时还能更快。一种想法是采用变长编码，出现频繁的字符采用较短的编码，从而达到压缩的目的。实现这种想法所采用的数据结构是满二叉树(若不是，通过增加或删除非叶节点来满足)，树中只有叶子节点有数据(字符)。从根节点开始，通往每个叶子节点时，用0表示左分支，1表示右分支，这样就可以得到相应的路径，这个路径就是该字符的编码。这里有一个关键问题是：任何字符的编码，不能是其他字符编码的前缀，否则就分不清了。哈夫曼编码就是满足所有条件的一种解决方案。
????主要思路：假设字符个数为C，开始时，每个字符都看作是包含一个元素的树，所有的字符就组成了一个森林；一颗树的权等于它所有的树叶频率之和；任意选取最小权的树T1、T2，将它们合并为一个新树，T1、T2作为新树的叶子节点；将这样的过程进行(C-1)次，就得到了Huffman编码树。
????举例说明，假设一个文件由“天”、“地”、“人”三字组成(乱序)，出现次数分别为3w、2w、1w，三字对应的Huffman编码依次是“1”、"01"、“00”(比特，位)。如果以一个汉字占2字节来计算，那么压缩前需要的空间：12w字节= 117 KB。压缩后的空间：10w 比特 = 12 KB。可以看到，效果明显。只要解压缩一方知道编码方案，就可以解压还原了。
????Java实现：
/**
* 霍夫曼算法
*/
public class Hufman {
//huffman编码方案
static Map<Character, String> huffmanCodes = new HashMap<>();
class Node implements Comparable<Node> {
Character data;//存放字符
int weight; //权值
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;
}
}
/**
* 从输入中，构造所有的节点
*
* @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;
}
/**
* 创建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);
}
/**
* 为每个叶子节点，创建huffman编码
*
* @param node 节点
* @param doneCode 已完成的huffman编码，用于拼接
*/
void createHuffmanCode(Node node, String doneCode) {
if (node != null) {
if (node.data == null) { //非叶节点
createHuffmanCode(node.leftChild, doneCode +"0");
createHuffmanCode(node.rightChild, doneCode +"1");
} else { //叶子节点
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}
????本示例中，是可以处理常用中文字符的。或者说，可以处理位于BMP(基本多文种平面)中的中文汉字，数量大概有2W+，是一些常用的汉字。对于其他平面的汉字，是不支持的。emoji等因为不在BMP中，所以也不支持。
????汉字的数量远超英文字符，有7W+，常用的有2W+。所以，对于包含很多汉字的大文件来说，霍夫曼树是非常庞大的。算法的耗时估计不容乐观。但考虑到这个算法是1955年提出的，只考虑英文字母的情况下，最多26+26=52字符加上标点符号，还是非常合适的。
????Huffman编码到现在还没有过时，gzip压缩算法就是将它和另外一个压缩算法LZ77组合起来的。LZ77算法是1977年提出的，L、Z分别代表2个作者，这里不做扩充了。
????上面说到，本示例中可以处理中文。网上、书上不少版本，是不支持处理中文的。这里做一些说明。请看构造节点时getNodes()方法里的这一句：
char[] chars = content.toCharArray();
???? 后面的处理都是基于char类型的，Java中的char类型，占2个字节，包含了BMP中所有的字符。所以，它能处理常见的中文字符，但不能处理非BMP字符。
???? 如果将上面这一句，改为byte[]的方式，后续的也做相应修改，那么就不能处理任何中文字符了，如下：
byte[] bytes = content.getBytes();
???? 在网络传输的场景中，一般都处理的字节byte，此时，如果想处理常见中文字符，那么可以将InputStream转换为InputStreamReader，然后以char的方式处理。
???? 让我们再进一步，如果确实要处理非BMP字符，该怎么修改？在一些emoji表情的场景和非常见汉字，还是可能遇到的。这里简单说一下思路。
???? 在基于char的处理上，对获取的每个char，做一下判断。Character中有个方法isHighSurrogate()，可以判断当前char是否是高位代理，如果是，表明这个char字符是非BMP平面某个字符的一半，接着可以获取下个字符，然后将两者组合成一个新字符。当然，此时不能再用char来表示，因为超出了char的表示范围，而必须用字符串String。所以相应的数据类型也要改变。组成新的字符串方式如下：
???? char highSur = ...;
???? char lowSur = ...;
???? char[] chars = {highSur,lowSur};
???? String highLowStr = new String(chars);
????注意，高位在前，低位在后。
????从上面的过程可以知道，每个压缩文件对应的霍夫曼编码都不一样。类似这种特点的编码称为动态编码，有动即有静，静态编码是指保持不变的编码。静态编码是更常见的，如UTF-8、UTF-16、GBK等。霍夫曼编码也有静态版的，但适用性就没那么强了。
????霍夫曼编码属于“贪婪算法”这一类型，它的特点是分阶段地工作，“眼下能拿到的就拿”，形成局部最优。在构造霍夫曼树时，每次都选择权值最小的2个树进行合并，获得局部最优解，直至构造完成。
(3)Dijkstra算法
????Dijkstra(迪克斯特拉)算法是图论中一种解决单源最短路径问题的算法，是贪婪算法中的一种。
????主要思想：从源点S出发，按阶段进行，每个阶段，选择一个邻接新顶点(未被访问过)，使得S到它的距离最短。
????本小节将介绍两种实现方式，一种是使用邻接矩阵，一种是使用优先队列。
????先来看看邻接矩阵的方式，使用了《09_算法基本概念》中的图结构。Java版本如下：
/**
* Dijkstra算法
*/
public class Dijkstra {
//一般的图结构
class Graph {
static final int NUM = 10; //图的最大顶点数
char[] vertex = new char[NUM]; //顶点集合
int vertexNum;//实际顶点数量
int[][] edgeWeight = new int[NUM][NUM]; //邻接矩阵,含权
boolean[] isTrav = new boolean[NUM]; //是否访问的标志
}
/***
* 在未访问的连通顶点中，找到一个距离最小的，返回下标。
*
* 只看这个方法的话，是不能确定找到的这个顶点与已选择的顶点是连通的。
* 但结合上文来看，初始化时，已设置了源点到自身的距离是0，也即distArray数组中有一项是0。
* 而这个原点并未设置成已访问的，所以这个方法在第一次调用时返回的下标就是源点下标。
* 从下文来看，随后会更新与该顶点有连通的顶点距离放到distArray数组中，
* 后续对该方法的调用，其实就是在连通顶点中选择最小值。
*
* @param graph 图
* @param distArray 已选择的顶点距离数组
* @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算法实现
*
* @param srcVertex 源顶点
* @param graph 图结构
*/
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);
}
/**
* 构造一个图
* @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;
}
}
????上面算法构造的图如下：
????输出结果：
源点是：A
顶点????到源点的最短距离
A???????0
B???????1
C???????3
D???????5
E???????5
F???????14
????再来介绍优先队列的方式。在上面的代码中，找到一个与已访问顶点的最小连通顶点，是通过方法minDist()来实现的。而获取最小者，这非常符合优先队列的特点。优先队列是删除最小者，但删除的同时，也获得了这个最小者。因此，可以通过优先队列来处理。Java版本：
/**
* PriorityQueue实现Dijkstra算法
*/
public class DijkstraPQ {
/**
* 节点Node，如A、B、C等
*/
static class Node implements Comparator<Node> {
char aChar; //顶点名称
int weight; //权值
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;//顶点总数
List<List<Node>> adjList;//邻接矩阵，改用List来表示，上面是用二维数组
List<Character> charList;//所有的节点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)); //将源点加入优先队列
int srcIndex = getNodeIndex(srcVertex);
distArray[srcIndex] = 0; //源点到自身的权值为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);
}
}
????邻接矩阵的数据，仍然是基于上面的构造图。输出结果也和上面是一致的。
????List<List<>>表示的邻接矩阵，开始不那么容易理解。以这条语句为例来进行说明：
adjList.get(0).add(new Node('B',1));
它表示顶点'A'到顶点'B'的连接(有方向)，权值是1；等价的二维数组表示法：edgeWeight[0][1] = 1;
顶点是按照一定的顺序确定好的。0对应着'A'，'B'对应着1。
adjList.get(1).add(new Node('A',1));
这行代码表示'B'到'A'有一条连接，权值也是1。等价的二维数组表示法：edgeWeight[1][0] = 1;
这是因为使用的构造图是无方向的，正反都得来一次。
????List<List<>>形式表示的邻接矩阵，在表示有向图时非常方便。一个Node代表着一条带箭头的边。而表示无向图时，显然二维数组要更方便，沿着对角线(左上到右下)是完全对称的。这两种表示方式可以相互替换，稍加改动即可。
????此外，基于优先队列的这种特点，前面一小节(2)霍夫曼编码在选取两个权值最小的树时，也可以考虑使用优先队列来实现，不过在此就不展开了。
(4)Prim算法
????Prim算法是图论中找出最小生成树的一种算法。最小生成树的概念可以去《09_算法基本概念》复习一遍。
????基本思想：它和Dijstra算法有很大的相似性；初始时，随机选择一个顶点作为最小生成树的根；接着选择到生成树权值最小的连通顶点，这一过程和Dijstra算法一样；直到所有的顶点都处理完为止。
????Java实现：
/**
* Prim算法：最小生成树算法
*/
public class Prim {
//一般的图结构
class Graph {
static final int NUM = 10; //图的最大顶点数
char[] vertex = new char[NUM]; //顶点集合
int vertexNum;//实际顶点数量
int gType = 0; //无向图
int[][] edgeWeight = new int[NUM][NUM]; //邻接矩阵,含权
boolean[] isTrav = new boolean[NUM]; //是否访问的标志
}
/**
* prim算法
*
* @param graph 原始图
* @return 最小生成树组成的图
*/
Graph prim(Graph graph) {
Graph resultG = new Graph(); //目标最小生成树，用图结构表示
resultG.vertex = graph.vertex; //最终顶点是一样的
resultG.vertexNum = graph.vertexNum; //最终顶点数量也是一样的
int[] distArray = new int[graph.vertexNum]; //各未选顶点到最小生成树的最小距离
int[] mstIndexArray = new int[graph.vertexNum];//各未选顶点连接到最小生成树顶点的下标
for (int i = 0; i < distArray.length; i++) { //初始值设为最大
distArray[i] = Integer.MAX_VALUE;
}
//任选一点作为起始顶点
distArray[0] = 0;//到自己的距离为0
for (int i = 0; i < graph.vertexNum; i++) {
//找到一个权值最小的顶点
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权值");
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权值");
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]);
}
}
}
}
/**
* 构造一个图
*
* @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;
}
}
????输出结果：
顶点对??????????权值
A <------> B????1
A <------> C????3
B <------> D????4
C <------> E????2
E <------> F????9
顶点对??????????权值
A <------> B????1
A <------> C????3
B <------> D????4
C <------> E????2
E <------> F????9
????这里输出了二次，结果都一样。主要是为了对比，前一次是使用各顶点连接到最小生成树的顶点下标数组来输出的；后一次是使用prim()方法的返回值，即用图结构表示的最小生成树，然后在此基础上输出的，这个返回值也可以不需要，只是为了获得一颗最小生成树而已。
????它和Dijkstra算法的主要区别一是需要多记录各顶点到生成树的顶点下标，其次是更新未选顶点的距离时，只需权值即可，不再加上已选顶点的距离。对比如下：
dijkstra算法，需要加上已选顶点距离：
distArray[j] = distArray[minIndex] + graph.edgeWeight[minIndex][j];
而prim算法，只需要计算权值：
distArray[j] = graph.edgeWeight[minIndex][j];
????此外，既然是树，那么如果想用树结构来表示呢？也是可以的。转换如下：
/**
* 将图结构表示的最小生成树，转为树结构表示的
*
* @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;//根节点没有父节点，权值置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有连接
Node iNode = allNodes[i];
Node jNode = allNodes[j];
jNode.weight = graph.edgeWeight[i][j];
iNode.addChildNode(jNode);//添加为子节点
}
}
}
return allNodes[0];
}
class Node {
char aChar; //节点名
List<Node> childNodes; //所有的孩子节点
int weight;//到父节点的权值
public Node(char aChar) {
childNodes = new ArrayList<Node>();
this.aChar = aChar;
}
public void addChildNode(Node childNode) {
childNodes.add(childNode);
}
}
????需要注意的是，这个最小生成树不一定是常见的二叉树。每个节点的子节点数是不定的。
(5)Kruskal算法
????Kruskal算法也是一种找出最小生成树的算法。
????主要思想：依次选一条权值最小的边，如果没有产生回路，就加入到最小生成树中；如果产生回路，执行下一次循环；这个过程执行(n-1)次，就获得了需要的最小生成树。
????分析：可以看到，选择新的一条边时，是否形成了循环，就是关键所在；这里需要用到“不相交集”的概念，在开始时，将所有节点都看作互不相交的子集，每个节点的父节点是自身；如果从 i 到 j 有一条边，那么将 i 和 j合并成一个集合，并使得 i 是 j 的父亲节点；处理后续的边时，只要两节点的父节点不同，说明它们不在同一个集合里，就不会形成回路。
????Java实现：
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
/**
* 使用优先队列的Kruskal算法
*/
public class KruskalPQ {
//一般的图结构
class Graph {
static final int NUM = 10; //图的最大顶点数
char[] vertex = new char[NUM]; //顶点集合
int vertexNum;//实际顶点数量
int gType = 0; //0表示无向图，1表示有向图
int[][] edgeWeight = new int[NUM][NUM]; //邻接矩阵,含权
boolean[] isTrav = new boolean[NUM]; //是否访问的标志
}
/**
* 图中的边
*/
class Edge {
int srcIndex; //起始位置
int endIndex; //结束位置
int weight; //权值
}
class Subset { // 不相交集
int fatherIndex;//父节点的下标
int rank; //合并两个不相交集时的依据
}
PriorityQueue<Edge> priorityQueue;
public KruskalPQ() {
priorityQueue = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
}
/**
* 找到index= i的节点的父节点
*
* @param subsets
* @param i
* @return
*/
int find(Subset[] subsets, int i) {
if (subsets[i].fatherIndex != i) { //不相等，说明当前节点设置了父节点，继续查找父节点
subsets[i].fatherIndex = find(subsets, subsets[i].fatherIndex);
return subsets[i].fatherIndex;
} else {
return i; //相等，返回自身
}
}
/**
* 将x、y节点合并到一个集合，使得它们的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(); //目标最小生成树，用图结构表示
resultG.vertex = g.vertex; //最终顶点是一样的
resultG.vertexNum = g.vertexNum; //最终顶点数量也是一样的
addAllEdges(g); //添加所有的边
Subset[] subsets = new Subset[g.vertexNum];
for (int i = 0; i < subsets.length; i++) {
Subset tmpSubset = new Subset();
tmpSubset.fatherIndex = i; //初始时，fatherIndex设置为自己
tmpSubset.rank = 0;
subsets[i] = tmpSubset;
}
List<Edge> selectedEdgeList = new ArrayList<>();//最小生成树选择的边
for (int i = 0; i < g.vertexNum - 1; i++) {
Edge smallEdge = priorityQueue.remove(); //获得权值最小的一条边
int x = find(subsets, smallEdge.srcIndex);
int y = find(subsets, smallEdge.endIndex);
if (x != y) {//不相等，说明不存在环
selectedEdgeList.add(smallEdge);
resultG.edgeWeight[smallEdge.srcIndex][smallEdge.endIndex] = smallEdge.weight;
union(subsets, x, y);
}
}
System.out.println("(边)顶点对\t\t\t\t权值");
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);
}
}
}
}
/**
* 构造一个图
*
* @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权值");
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]);
}
}
}
}
}
????输出：
(边)顶点对????????权值
A <------> B??????1
C <------> E??????2
A <------> C??????3
B <------> D??????4
E <------> F??????9
顶点对???????????权值
A <------> B??????1
A <------> C??????3
B <------> D??????4
C <------> E??????2
E <------> F??????9
????结果是一致，只是输出顺序不同而已。上面的依据每次选择的最小边输出，下面则是依据图的顶点顺序输出。
????此外，这里非常适合使用PriorityQueue，每次只需要选择权值最小的边，而不管这条边的顶点是否与已选顶点连通，这一点是与Prim算法非常不同的一个地方。如果不使用PriorityQueue，那么每次选最小边时，就需要重新排序了。
????Over ！