数据结构与算法——基础篇（三）
二叉排序树——BST——Binary Sort(Search) Tree
二叉排序树的出现是为了解决数组的查询快，但是插入删除满；而链表的插入删除快，但查询慢而引出的一种查询和插入删除都相对较快的一种数据结构。
介绍
二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点。
思路分析
插入和遍历思路分析
插入就是按照左子节点的值比当前节点的值小，右子节点的值比当前节点的值大的规则来对节点进行递归比较插入，而遍历只需要按照普通的前序、中序、后序遍历即可。
删除思路分析
代码示例
一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9)
public class Node {
private int value;
private Node left;
private Node right;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Node(int value) {
this.value = value;
}
/**
* 查找要删除的节点，返回该节点，找不到返回null
*不考虑值相同的情况
* @param value 希望删除节点的值
* @return
*/
public Node searchNode(int value) {
//值相同则找到
if (this.value == value) {
return this;
}
//查找的值小于当前节点的值，则向左子树递归查找
if (this.value > value) {
//左子节点为空则不存在，返回null
if (this.left == null) {
return null;
} else {
return this.left.searchNode(value);
}
//查找的值大于当前节点的值，则向右子树递归查找（不可能等于了，如果等于就已经在第一个判断中返回了）
} else {
if (this.right == null) {
return null;
} else {
return this.right.searchNode(value);
}
}
}
/**
* 查找要删除的父节点的值
* @param value 要查找的节点的值
* @return 返回查找节点的父节点，找不到返回null
*/
public Node searchParent(int value) {
//判断当前节点是否为要删除节点的父节点，是则返回当前节点
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
}
//查找的节点的值小于当前节点的值，且左子节点不为空，则递归向左子树查找
if (this.value > value && this.left != null) {
return this.left.searchParent(value);
} else {
//查找的节点的值大于当前节点的值，且右子节点不为空，则递归向左子树查找
if (this.right != null) {
return this.right.searchParent(value);
}
}
//其他情况则没有找到父节点，返回null
return null;
}
/**
* 按照二叉排序树规则添加元素
* 递归添加节点，需要满足二叉排序树的要求
*
* @param node
*/
public void add(Node node) {
if (node == null) {
System.out.println("新增节点为空！");
return;
}
//当前节点的值大于新增节点的值，把新增节点的值放到该节点的左边，需要递归比较添加，直到放到合适的位置
if (this.value > node.value) {
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
/**
* 中序遍历
*/
public void inOrder() {
if (this.left != null) {
this.left.inOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.inOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
//二叉排序树（只考虑值都不同的情况）
public class BinarySortTree {
private Node root;
/**
* 查找节点
*
* @param value
* @return
*/
public Node searchNode(int value) {
if (root == null) {
return null;
}
return root.searchNode(value);
}
/**
* 查找要查找节点的父节点
*
* @param value
* @return
*/
public Node searchParent(int value) {
if (root == null) {
return null;
}
return root.searchParent(value);
}
/**
* 添加元素
*
* @param node
*/
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
/**
* 中序遍历
*/
public void inOrder() {
if (root == null) {
System.out.println("没有可中序遍历的节点");
} else {
root.inOrder();
}
}
public void deleteNode(int value) {
if (root == null) {
System.out.println("二叉排序树为空，没有可删除的节点");
return;
}
//查找要删除的节点
Node targetNode = searchNode(value);
if (targetNode == null) {
System.out.println("找不到对应可删除的节点");
return;
}
//判断要删除节点是否为根节点且没有子节点
if (targetNode == root && targetNode.getLeft() == null && targetNode.getRight() == null) {
root = null;
return;
}
//查找要删除节点的父节点
Node parent = searchParent(value);
//1要删除的节点为叶子节点
if (targetNode.getRight() == null && targetNode.getLeft() == null) {
//判断要删除节点是在左右哪个子节点置空
//要删除的节点是父节点的左子节点
if (parent.getLeft() != null && parent.getLeft().getValue() == value) {
parent.setLeft(null);
} else if (parent.getRight() != null && parent.getRight().getValue() == value) {
parent.setRight(null);
}
//要删除的节点为父节点，且有左右子节点,则找到右子节点中最小的那个节点的值（最右子节点向左遍历寻找最小值）替换到目标节点的值，并删除该最小的节点
//或者找到目标节点的左节点中最大的值，并删除该最大的节点
} else if (targetNode.getRight() != null && targetNode.getLeft() != null) {
// int min = deleteRightMin(targetNode.getRight());
// targetNode.setValue(min);
int max = deleteLeftMax(targetNode.getLeft());
targetNode.setValue(max);
return;
//要删除的节点为父节点，且只有一个左子节点或者右子节点
} else {
//左子节点不为空
if (targetNode.getLeft() != null) {
//判断要删除节点是在左右哪个子节点
if (parent != null && parent.getLeft().getValue() == value) {
parent.setLeft(targetNode.getLeft());
} else if (parent != null && parent.getRight().getValue() == value){
parent.setRight(targetNode.getLeft());
} else {
//要删除的节点没有父节点则为根节点，直接赋值root即可,解决根节点只有一个子节点的情况导致的空指针问题
root = targetNode.getLeft();
}
//右子节点不为空
} else {
//判断要删除节点是在左右哪个子节点
if (parent != null && parent.getLeft().getValue() == value) {
parent.setLeft(targetNode.getRight());
} else if (parent != null && parent.getRight().getValue() == value){
parent.setRight(targetNode.getRight());
} else {
//要删除的节点没有父节点则为根节点，直接赋值root即可
root = targetNode.getRight();
}
}
}
}
/**
* 删除右子节点的最小的节点，并返回该最小节点的值
* @param node 传入的节点
* @return 以node为根节点的子树的这颗二叉排序树的最小节点的值
*/
private int deleteRightMin(Node node){
Node tempNode = node;
while (tempNode.getLeft() != null) {
tempNode = tempNode.getLeft();
}
deleteNode(tempNode.getValue());
return tempNode.getValue();
}
/**
* 删除左子节点的最大的节点，并返回该最大节点的值
* @param node 传入的节点
* @return 以node为根节点的子树的这颗二叉排序树的最大节点的值
*/
private int deleteLeftMax(Node node){
Node tempNode = node;
while (tempNode.getRight() != null) {
tempNode = tempNode.getRight();
}
deleteNode(tempNode.getValue());
return tempNode.getValue();
}
}
public class BinarySortTreeTest {
public static void main(String[] args) {
BinarySortTree binarySortTree = new BinarySortTree();
// int[] arr = {7, 3, 10, 12, 5, 1, 9,2};
int[] arr = {7, 13};
//添加节点
for (int i : arr) {
binarySortTree.add(new Node(i));
}
System.out.println(" 中序遍历删除前二叉排序树:");
binarySortTree.inOrder();
//测试删除叶子节点
// binarySortTree.deleteNode(2);
// binarySortTree.deleteNode(5);
// binarySortTree.deleteNode(9);
// binarySortTree.deleteNode(12);
//测试删除只有一个叶子节点的父节点
// binarySortTree.deleteNode(1);
//测试删除有两个子节点的父节点
// binarySortTree.deleteNode(7);
// binarySortTree.deleteNode(3);
binarySortTree.deleteNode(7);
System.out.println(" 中序遍历删除后二叉排序树:");
binarySortTree.inOrder();
}
/**
* 中序遍历删除前二叉排序树:
* Node{value=1}
* Node{value=2}
* Node{value=3}
* Node{value=5}
* Node{value=7}
* Node{value=9}
* Node{value=10}
* Node{value=12}
* 中序遍历删除后二叉排序树:
* Node{value=1}
* Node{value=2}
* Node{value=3}
* Node{value=5}
* Node{value=9}
* Node{value=10}
* Node{value=12}
*/
}
平衡二叉树——AVL树
解决二叉排序树在极端情况下退化为链表的问题。
平衡二叉树首先是一颗二叉排序树，这是前提。
基本介绍
- 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
- 具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL(算法)、替罪羊树、Treap、伸展树等。
左旋转——【右子树高度 - 左子树高度>1】
什么时候进行左旋转
左旋转即当AVL树在进行添加或者删除节点操作的时候，首先我们会按照二叉排序树的添加规则进行数据的添加或者删除，但是，在完成添加或者删除的时候，会对该二叉平衡树进行计算左右两个子树的高度差是否满足不超过1，并且左右两个子树都是一棵平衡二叉树，如果不满足，且右边的高度减去左边的高度大于1，这时候就要进行左旋转，使其满足平衡二叉树的规则。
左旋操作思路
本质就是让根节点的右子节点成为新的根节点，而原来的根节点作为新的根节点的左子节点，以达到平衡的目的。
思路分析
右旋转——【左子树高度 - 右子树高度>1】
跟左旋转相反。
双旋转——单旋转不能完成平衡二叉树的转换
在某些情况下单纯的左右旋转并不能完成平衡二叉树的转换。
int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL树.
int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL树
如下图所示：
思路分析，针对这种需要进行右旋转的树，还需要先判断其左子树的右子树高度是否比该左子树的左子树高度高，如果高的话，就要先对这个左子节点先进行左旋转操作，也就是让高度偏向左边，再来做整棵树的右旋转才能有效。
代码示例——左旋转、右旋转、双旋转
public class Node {
private int value;
private Node left;
private Node right;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public Node(int value) {
this.value = value;
}
//返回当前节点的高度，以该节点作为根节点的树的高度
public int height() {
return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1;
}
//返回左子树的高度
public int leftHeight() {
if (this.left == null) {
return 0;
}
return this.left.height();
}
//返回右子树的高度
public int rightHeight() {
if (this.right == null) {
return 0;
}
return this.right.height();
}
/**
* 查找要删除的节点，返回该节点，找不到返回null
* 不考虑值相同的情况
*
* @param value 希望删除节点的值
* @return
*/
public Node searchNode(int value) {
//值相同则找到
if (this.value == value) {
return this;
}
//查找的值小于当前节点的值，则向左子树递归查找
if (this.value > value) {
//左子节点为空则不存在，返回null
if (this.left == null) {
return null;
} else {
return this.left.searchNode(value);
}
//查找的值大于当前节点的值，则向右子树递归查找（不可能等于了，如果等于就已经在第一个判断中返回了）
} else {
if (this.right == null) {
return null;
} else {
return this.right.searchNode(value);
}
}
}
/**
* 查找要删除的父节点的值
*
* @param value 要查找的节点的值
* @return 返回查找节点的父节点，找不到返回null
*/
public Node searchParent(int value) {
//判断当前节点是否为要删除节点的父节点，是则返回当前节点
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
}
//查找的节点的值小于当前节点的值，且左子节点不为空，则递归向左子树查找
if (this.value > value && this.left != null) {
return this.left.searchParent(value);
} else {
//查找的节点的值大于当前节点的值，且右子节点不为空，则递归向左子树查找
if (this.right != null) {
return this.right.searchParent(value);
}
}
//其他情况则没有找到父节点，返回null
return null;
}
/**
* 按照二叉排序树规则添加元素
* 递归添加节点，需要满足二叉排序树的要求
*
* @param node
*/
public void add(Node node) {
if (node == null) {
System.out.println("新增节点为空！");
return;
}
//当前节点的值大于新增节点的值，把新增节点的值放到该节点的左边，需要递归比较添加，直到放到合适的位置
if (this.value > node.value) {
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
//添加完节点后判断是否需要进行左旋转或者右旋转进行平衡
//当 当前节点的右子树的高度减去当前节点的左子树的高度大于1时，进行左旋
if (this.rightHeight() - this.leftHeight() > 1) {
//当 当前节点的右子树的左子树的高度大于当前节点的右子树的右子树的高度
if (this.right.leftHeight() > this.right.rightHeight()) {
//先对右子节点进行右旋转
this.right.rotateRight();
}
//无论上面条件满足与否都要进行左旋转
rotateLeft();
return;
}
//当 当前节点的左子树的高度减去当前节点的右子树的高度大于1时，进行右旋转
if (this.leftHeight() - this.rightHeight()> 1) {
//当 当前节点的左子树的右子树的高度大于当前节点的左子树的左子树的高度
if (this.left.rightHeight()>this.left.leftHeight()) {
//则需要对当前节点的左子节点进行左旋，让其节点高度偏向左边，这样再进行右旋就不会出现平衡不了的情况
this.left.rotateLeft();
}
//进行右旋转
rotateRight();
}
}
/**
* 左旋转方法
*/
private void rotateLeft() {
//以当前节点的值创建一个新节点
Node newNode = new Node(value);
//把当前节点的左子节点设置为新节点的左子节点
newNode.left = this.left;
//把当前节点的右子节点的左子节点设置为新节点的右子节点
newNode.right = this.right.left;
//把当前节点的值替换为右子节点的值
this.value = this.right.value;
//把新节点设置为当前节点的左子树
this.left = newNode;
//把当前节点的右子节点的右子节点设置为当前节点的右子节点
this.right = this.right.right;
}
/**
* 右旋转，本质上就是让当前节点的左节点作为父节点，而当前节点变成其右节点，而其左节点还是原来的节点的左节点
*/
private void rotateRight() {
Node newNode = new Node(value);
newNode.left = this.left.right;
newNode.right = this.right;
this.value = this.left.value;
this.left = this.left.left;
this.right = newNode;
}
/**
* 中序遍历
*/
public void inOrder() {
if (this.left != null) {
this.left.inOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.inOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
//AVL平衡二叉树是建立在二叉排序树的基础上
public class AVLTree {
private Node root;
//返回
public int height() {
if (root == null) {
return 0;
}
return root.height();
}
public int leftHeight(){
if (root == null) {
return 0;
}
return root.leftHeight();
}
public int rightHeight(){
if (root == null) {
return 0;
}
return root.rightHeight();
}
/**
* 查找节点
*
* @param value
* @return
*/
public Node searchNode(int value) {
if (root == null) {
return null;
}
return root.searchNode(value);
}
/**
* 查找要查找节点的父节点
*
* @param value
* @return
*/
public Node searchParent(int value) {
if (root == null) {
return null;
}
return root.searchParent(value);
}
/**
* 添加元素
*
* @param node
*/
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
/**
* 中序遍历
*/
public void inOrder() {
if (root == null) {
System.out.println("没有可中序遍历的节点");
} else {
root.inOrder();
}
}
public void deleteNode(int value) {
if (root == null) {
System.out.println("二叉排序树为空，没有可删除的节点");
return;
}
//查找要删除的节点
Node targetNode = searchNode(value);
if (targetNode == null) {
System.out.println("找不到对应可删除的节点");
return;
}
//判断要删除节点是否为根节点且没有子节点
if (targetNode == root && targetNode.getLeft() == null && targetNode.getRight() == null) {
root = null;
return;
}
//查找要删除节点的父节点
Node parent = searchParent(value);
//1要删除的节点为叶子节点
if (targetNode.getRight() == null && targetNode.getLeft() == null) {
//判断要删除节点是在左右哪个子节点置空
//要删除的节点是父节点的左子节点
if (parent.getLeft() != null && parent.getLeft().getValue() == value) {
parent.setLeft(null);
} else if (parent.getRight() != null && parent.getRight().getValue() == value) {
parent.setRight(null);
}
//要删除的节点为父节点，且有左右子节点,则找到右子节点中最小的那个节点的值（最右子节点向左遍历寻找最小值）替换到目标节点的值，并删除该最小的节点
//或者找到目标节点的左节点中最大的值，并删除该最大的节点
} else if (targetNode.getRight() != null && targetNode.getLeft() != null) {
// int min = deleteRightMin(targetNode.getRight());
// targetNode.setValue(min);
int max = deleteLeftMax(targetNode.getLeft());
targetNode.setValue(max);
return;
//要删除的节点为父节点，且只有一个左子节点或者右子节点
} else {
//左子节点不为空
if (targetNode.getLeft() != null) {
//判断要删除节点是在左右哪个子节点
if (parent != null && parent.getLeft().getValue() == value) {
parent.setLeft(targetNode.getLeft());
} else if (parent != null && parent.getRight().getValue() == value){
parent.setRight(targetNode.getLeft());
} else {
//要删除的节点没有父节点则为根节点，直接赋值root即可,解决根节点只有一个子节点的情况导致的空指针问题
root = targetNode.getLeft();
}
//右子节点不为空
} else {
//判断要删除节点是在左右哪个子节点
if (parent != null && parent.getLeft().getValue() == value) {
parent.setLeft(targetNode.getRight());
} else if (parent != null && parent.getRight().getValue() == value){
parent.setRight(targetNode.getRight());
} else {
//要删除的节点没有父节点则为根节点，直接赋值root即可
root = targetNode.getRight();
}
}
}
}
/**
* 删除右子节点的最小的节点，并返回该最小节点的值
* @param node 传入的节点
* @return 以node为根节点的子树的这颗二叉排序树的最小节点的值
*/
private int deleteRightMin(Node node){
Node tempNode = node;
while (tempNode.getLeft() != null) {
tempNode = tempNode.getLeft();
}
deleteNode(tempNode.getValue());
return tempNode.getValue();
}
/**
* 删除左子节点的最大的节点，并返回该最大节点的值
* @param node 传入的节点
* @return 以node为根节点的子树的这颗二叉排序树的最大节点的值
*/
private int deleteLeftMax(Node node){
Node tempNode = node;
while (tempNode.getRight() != null) {
tempNode = tempNode.getRight();
}
deleteNode(tempNode.getValue());
return tempNode.getValue();
}
}
public class AVLTreeTest {
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
// //左旋测试
// int[] leftRotateArr = {4, 3, 6, 5, 7, 8};
// for (int i : leftRotateArr) {
// avlTree.add(new Node(i));
// }
/* //右旋测试
int[] rightRotateArr = {10,12, 8, 9, 7, 6};
for (int i : rightRotateArr) {
avlTree.add(new Node(i));
}*/
//双旋转测试
int[] rotateArr = {10, 11, 7, 6, 8, 9};
for (int i : rotateArr) {
avlTree.add(new Node(i));
}
avlTree.inOrder();
System.out.println("树的高度："+avlTree.height());
System.out.println("左子树的高度："+avlTree.leftHeight());
System.out.println("右子树的高度："+avlTree.rightHeight());
}
/**
* Node{value=6}
* Node{value=7}
* Node{value=8}
* Node{value=9}
* Node{value=10}
* Node{value=11}
* 树的高度：3
* 左子树的高度：2
* 右子树的高度：2
*/
}
图——多对多——Graph
图的出现是为了解决多对多关系
线性表局限于一个直接前驱和一个直接后继的关系，树也只能有一个直接前驱也就是父节点。
当我们需要表示多对多的关系时， 这里我们就用到了图。
基本介绍
图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。生活中比如地铁交汇的线路图等。
图的表示方式
图的表示方式有两种：二维数组表示（邻接矩阵）；数组加链表表示（邻接表）。
邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。
邻接表
邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失。
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。
图遍历介绍
深度优先遍历用递归，广度优先遍历用队列。
所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略:
- 深度优先遍历
- 广度优先遍历。
图的深度优先遍历——DFS——Depth-First-Search
深度优先遍历基本思想
图的深度优先搜索(Depth First Search) 。
深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
显然，深度优先搜索是一个递归的过程。
深度优先遍历算法步骤
- 访问初始结点v，并标记结点v为已访问。
- 查找结点v的第一个邻接结点w。
- 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
- 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
- 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
图的广度优先遍历——BFS——Breadth-First-Search
广度优先遍历基本思想
图的广度优先搜索(Breadth First Search) 。
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。
广度优先遍历算法步骤
-
访问初始结点v并标记结点v为已访问。
-
结点v入队列
-
当队列非空时，继续执行，否则算法结束。
-
出队列，取得队头结点u。
-
查找结点u的第一个邻接结点w。
-
若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
6.2 结点w入队列
6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
代码示例
对下图进行深度优先遍历和广度优先遍历
//图，邻接矩阵实现
public class Graph {
//存储顶点的集合
private List<String> vertexList;
//邻接矩阵，用来存储边
private int[][] edges;
//记录一共有多少条边
private int numOfEdges;
private boolean[] isVisited;
public Graph(int n) {
//初始化矩阵
this.vertexList = new ArrayList<>(n);
this.edges = new int[n][n];
this.numOfEdges = 0;
this.isVisited = new boolean[n];
}
/**
* 插入顶点
*
* @param vertex
*/
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
/**
* 插入边关系
*
* @param v1 边关系顶点对应的下标，也就是vertexList集合上的元素对应的下标
* @param v2 边关系顶点对应的下标
* @param weight 权值，默认不带权的为1
*/
public void insertEdge(int v1, int v2, int weight) {
//如果是无向图则对邻接矩阵的两个顶点的关系都要添加，有向图则只添加一条
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
//返回顶点的总数
public int getNumOfVertex() {
return vertexList.size();
}
//返回边的总数
public int getNumOfEdges() {
return numOfEdges;
}
//返回顶点下标index对应的顶点名称
public String getValueByIndex(int index) {
return vertexList.get(index);
}
//返回顶点下标为v1,v2对应的边的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
//显示图对应的邻接矩阵
public void showGraph() {
Arrays.stream(edges).forEach((ints -> System.out.println(Arrays.toString(ints))));
}
/**
* 得到顶点下标为index的第一个邻接顶点的下标
*
* @param index
* @return 存在返回第一个邻接顶点的下标，否则返回-1
*/
public int getFirstNeighbor(int index) {
for (int i = 0; i < vertexList.size(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
/**
* 根据前一个邻接顶点的下标来获取下一个邻接顶点(注意还是在顶点下标为index的基础上去找他的下一个邻接顶点)
*
* @param index 顶点下标为index
* @param v2 顶点下标为index的顶点的当前邻接顶点的下标
* @return 返回顶点下标为index的下一个邻接顶点下标
*/
public int getNextNeighbor(int index, int v2) {
//v2+1的意思是当前的邻接顶点在v2这个位置，继续从这里出发寻找下一个
for (int i = v2 + 1; i < vertexList.size(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
//清空已访问标记
public void clearIsVisited() {
this.isVisited = new boolean[vertexList.size()];
System.out.println();
}
/**
* 深度优先遍历
*
* @param index 待遍历顶点，从0开始
*/
private void dfs(int index) {
//首先访问该顶点，在控制台打印出来
System.out.print(getValueByIndex(index) + "->");
//标记已访问
this.isVisited[index] = true;
int w = getFirstNeighbor(index);
while (w != -1) {
if (!isVisited[w]) {
dfs(w);
} else {
w = getNextNeighbor(index, w);
}
}
}
/**
* 重载深度优先遍历
*/
public void dfs() {
System.out.println("深度优先遍历： ");
//在这里进行遍历是因为对于非连通图来说，并不是通过一个结点就一定可以遍历所有结点的。
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(i);
}
}
}
/**
* 重载广度优先遍历
*/
public void bfs() {
System.out.println("广度优先遍历： ");
//避免非连通图情况，在进入遍历前先判断是否被遍历
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
bfs(i);
}
}
}
/**
* 广度优先遍历
*
* @param index 待遍历顶点，从0开始
*/
private void bfs(int index) {
//从队列头取出来的顶点对应下标，用于进行广度优先遍历时获取下一个邻接顶点
int u;
//队列头顶点的下一个邻接顶点
int w;
//存储顶点的访问顺序用户广度优先遍历，因为广度优先遍历是先把入队列的顶点所拥有关联关系的节点都遍历了才会再遍历下一个入队列的顶点，
// 也就是说先遍历与自己直接关联再遍历间接关联的直接关联顶点
LinkedList<Integer> queue = new LinkedList<>();
//输出顶点信息
System.out.print(getValueByIndex(index) + "->");
//标记已访问
this.isVisited[index] = true;
//将节点加入队列
queue.addLast(index);
while (!queue.isEmpty()) {
//取出队列的头结点下标
u = queue.removeFirst();
//获取顶点u的第一个邻接顶点下标
w = getFirstNeighbor(u);
while (w != -1) {
//如果找到且未访问过，则打印出来，并标记已访问，添加该顶点到队列尾中
if (!isVisited[w]) {
System.out.print(getValueByIndex(w) + "->");
this.isVisited[w] = true;
queue.addLast(w);
}
//如果已被访问，继续获取顶点u的邻接节点知道找不到为止
//这里体现出广度优先遍历，因为我们还是找顶点u的邻接节点，而不是拿下一个顶点往下继续寻找
w = getNextNeighbor(u, w);
}
}
}
}
/**
* [0, 1, 1, 0, 0, 0, 0, 0]
* [1, 0, 0, 1, 1, 0, 0, 0]
* [1, 0, 0, 0, 0, 1, 1, 0]
* [0, 1, 0, 0, 0, 0, 0, 1]
* [0, 1, 0, 0, 0, 0, 0, 1]
* [0, 0, 1, 0, 0, 0, 1, 0]
* [0, 0, 1, 0, 0, 1, 0, 0]
* [0, 0, 0, 1, 1, 0, 0, 0]
* 深度优先遍历：
* 1->2->4->8->5->3->6->7->
* 广度优先遍历：
* 1->2->3->4->5->6->7->8->
*/
public class GraphTest {
public static void main(String[] args) {
String[] strings ={"1","2","3","4","5","6","7","8"};
Graph graph = new Graph(strings.length);
//添加顶点
for (String vertex: strings) {
graph.insertVertex(vertex);
}
//添加边关系
graph.insertEdge(0,1,1);
graph.insertEdge(0,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(1,4,1);
graph.insertEdge(2,5,1);
graph.insertEdge(2,6,1);
graph.insertEdge(3,7,1);
graph.insertEdge(4,7,1);
graph.insertEdge(5,6,1);
graph.showGraph();
graph.dfs();
graph.clearIsVisited();
graph.bfs();
}
}
常用10种算法
二分查找算法(非递归)——要求有序
二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找
二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7)
代码示例
数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找， 要求使用非递归的方式完成
public class BinarySearchNonRecursion {
public static void main(String[] args) {
int[] arr = {1, 3, 8, 10, 11, 67, 100};
System.out.println(binarySearchNonRecursion(arr, 12));
}
public static int binarySearchNonRecursion(int[] arr, int target) {
if (arr == null || arr.length == 0) {
return -1;
}
int left = 0;
int right = arr.length - 1;
int mid = (left + right) / 2;
//注意这里继续查找条件是: <=,因为会有left == right刚好找到的时候
while (left <= right) {
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
//向左找
right = mid - 1;
mid = (left + right) / 2;
} else {
//向右找
left = mid + 1;
mid = (left + right) / 2;
}
}
return -1;
}
}
分治算法——Divide-and-Conquer
介绍
分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
分治算法可以求解的一些经典问题
- 二分搜索
- 大整数乘法
- 棋盘覆盖
- 归并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
基本步骤
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。
- 合并：将各个子问题的解合并为原问题的解。
分治(Divide-and-Conquer(P))算法设计模式
汉诺塔
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
64片黄金圆盘需要移动2^64-1=18446744073709551615次。
假如每秒钟一次，共需多长时间呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
思路分析
如果是有一个盘， A->C
如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘（除最下面的一个盘外的所有盘看成一个整体）
先把 最上面的盘 A->B
把最下边的盘 A->C
把B塔的所有盘 从 B->C
代码示例
/**
* 第1个盘从A移动到C
* 第2个盘从A移动到B
* 第1个盘从C移动到B
* 第3个盘从A移动到C
* 第1个盘从B移动到A
* 第2个盘从B移动到C
* 第1个盘从A移动到C
*/
public class HanoiTower {
public static void main(String[] args) {
hanoiTower(3,"A","B","C");
}
/**
* 汉诺塔
* @param num 移动盘数
* @param a A柱
* @param b B柱(相当于temp,移动时借助的柱子)
* @param c C柱
*/
public static void hanoiTower(int num, String a, String b, String c) {
if (num == 1) {
System.out.println("第" + num + "个盘从" + a + "移动到" + c);
} else {
//先把 最上面的盘 A->B,借助C
hanoiTower(num - 1, a, c, b);
//把最下边的盘 A->C
System.out.println("第" + num + "个盘从" + a + "移动到" + c);
//把B塔的所有盘 从 B->C ，借助A
hanoiTower(num - 1, b, a, c);
}
}
}
动态规划算法——Dynamic Programming——DP
介绍
动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
动态规划可以通过填表的方式来逐步推进，得到最优解。
背包问题
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。
- 01背包：01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。
- 完全背包：每种物品有无限件可用，也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……取[V/c]件等很多种 。
无限背包可以转化为01背包。
思路分析
利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果：
(1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0
(2) 当w[i]> j 时：v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略。
(3) 当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
// 当 准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:
v[i-1][j]： 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值
v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的最大值
当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
代码示例
背包问题：有一个背包，容量为4磅 ， 现有如下物品：
要求达到的目标为装入的背包的总价值最大，并且重量不超出要求装入的物品不能重复。
| 物品 | 重量 | 价格 |
|---|---|---|
| 吉他(G) | 1 | 1500 |
| 音响(S) | 4 | 3000 |
| 电脑(L) | 3 | 2000 |
//动态规划算法——背包问题——01背包
public class KnapsackProblem {
/**
* 当背包重量为4时，最大价值情况下，打印都要哪些物品放入背包：
* 第3个物品放入了背包
* 第1个物品放入了背包
* 打印背包的最优价值：
* [0, 0, 0, 0, 0]
* [0, 1500, 1500, 1500, 1500]
* [0, 1500, 1500, 1500, 3000]
* [0, 1500, 1500, 2000, 3500]
*/
public static void main(String[] args) {
//物品的重量
int[] goodsWeights = {1, 4, 3};
//物品的价值
int[] goodsValues = {1500, 3000, 2000};
//背包容量
int knapsackCapcity = 4;
knapsackProblem(goodsWeights,goodsValues,knapsackCapcity);
}
public static void knapsackProblem(int[] goodsWeights, int[] goodsValues, int knapsackCapcity) {
//物品的个数
int goodsNums = goodsWeights.length;
//用于存放当有多少个物品对应背包有多大容量时，背包中装入的物品所能达到的最大价值是多少
//v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
//加1是为了避开数组是0开始，让我们能从第1个商品第1磅开始
int[][] maxValue = new int[goodsNums + 1][knapsackCapcity + 1];
//记录放入商品的情况
int[][] path = new int[goodsNums + 1][knapsackCapcity + 1];
//初始化第一行、第一列为0
//将第一列值为0 ,因为我们第一个for循环是每一行的数组，
for (int i = 0; i < maxValue.length; i++) {
maxValue[i][0] = 0;
//这里注意如果二维数组的行列不是相同长度的话不能这样设置，否则会导致设置值有问题
// maxValue[0][i] = 1;
}
//将第一行值为0
for (int i = 0; i < maxValue[0].length; i++) {
maxValue[0][i] = 0;
}
for (int i = 1; i < maxValue.length; i++) {
for (int j = 1; j < maxValue[i].length; j++) {
//goodsWeights[i - 1]是因为我们是从1开始的，而我们的重量数组是从0开始的
//如果商品重量比容量为j的背包大，那就不需要比较直接拿上一个物品的比较结果即可
if (goodsWeights[i - 1] > j) {
maxValue[i][j] = maxValue[i - 1][j];
} else {
// maxValue[i][j] = Math.max(maxValue[i - 1][j], goodsValues[i - 1] + maxValue[i - 1][j - goodsWeights[i - 1]]);
if (goodsValues[i - 1] + maxValue[i - 1][j - goodsWeights[i - 1]] > maxValue[i - 1][j]) {
maxValue[i][j] = goodsValues[i - 1] + maxValue[i - 1][j - goodsWeights[i - 1]];
//标记物品被装入背包
path[i][j] = 1;
} else {
maxValue[i][j] = maxValue[i - 1][j];
}
}
}
}
System.out.printf("当背包重量为%d时，最大价值情况下，打印都要哪些物品放入背包：
",knapsackCapcity);
int x = path.length - 1;
//注意这里拿的是行的值
int y = path[0].length - 1;
while (x > 0 && y > 0) {
if (path[x][y] == 1) {
System.out.printf("第%s个物品放入了背包
", x);
//减去当前放入背包的商品的重量，去上面查找
y = y - goodsWeights[x - 1];
}
x--;
}
System.out.println("打印背包的最优价值：");
Arrays.stream(maxValue).forEach(ints -> System.out.println(Arrays.toString(ints)));
}
}
暴力匹配算法——字符串匹配问题
应用场景-字符串匹配问题
字符串匹配问题：：
有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串 str2="尚硅谷你尚硅你"
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
思路分析
如果用暴力匹配的思路，并假设现在str1匹配到 i 位置，子串str2匹配到 j 位置，则有:
- 如果当前字符匹配成功（即str1[i] == str2[j]），则i++，j++，继续匹配下一个字符
- 如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
- 用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!)
代码实现
//暴力匹配
public class ViolentMatch {
public static void main(String[] args) {
String s1 ="我是一我是一只我是一只我是一只我是一只小蜜蜂，飞到花丛中";
String s2 ="我是一只小蜜蜂";
int i = violentMatch(s1, s2);
if (i !=-1) {
System.out.println("匹配下标为："+i);
}else {
System.out.println("匹配不到！");
}
//匹配下标为：15
}
public static int violentMatch(String s1, String s2) {
char[] s1Arr = s1.toCharArray();
char[] s2Arr = s2.toCharArray();
int i = 0;
int j = 0;
while (i < s1Arr.length && j < s2Arr.length) {
if (s1Arr[i] == s2Arr[j]) {
i++;
j++;
} else {
i = i - (j - 1);
j = 0;
}
}
if (j == s2Arr.length) {
return i - j;
} else {
return -1;
}
}
}
KMP算法——字符串匹配问题
介绍
- KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
- Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法.
- KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间
思路分析
KMP算法的本质就是在暴力匹配的基础上，去发现其实有一些之前已经匹配过的字段，其实是可以跳过不匹配的，这样就可以节约了很多匹配的次数。而对于可以跳过匹配的字符则是通过对匹配的子串进行部分匹配值表的建立，从而当两个字符串的字符不匹配时，根据部分匹配值表进行跳跃，而不是只是加一位继续匹配。而部分匹配值表则是根据该子串从0到总子串长时的前缀与后缀的最大相同值来构建的。拿字符串“AABBAAA”的部分匹配值表就是【0，1，0，0，1，2，2】
代码示例
public class KMP {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
int[] next = getKMPNext(str2);
System.out.println("子串的部分匹配值表" + Arrays.toString(next));
System.out.println("字符串匹配位置为：" + kmpSearch(str1, str2, next));
//子串的部分匹配值表[0, 0, 0, 0, 1, 2, 0]
//字符串匹配位置为：15
}
/**
* kmp搜索
* @param str1 待匹配字符串
* @param str2 子串
* @param next 子串对应的部分匹配表
* @return 返回第一个匹配到的位置，-1表示没有匹配到
*/
public static int kmpSearch(String str1, String str2, int[] next) {
for (int i = 0, j = 0; i < str1.length(); i++) {
//调整j的位置，这是与暴力算法简单加1不同的地方
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
//字符匹配相同则j+1继续往下匹配
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
//当j大小str2的长度时表示匹配成功
if (j == str2.length()) {
return i - j + 1;
}
}
return -1;
}
/**
* 获取部分匹配值表
* @param str
* @return
*/
public static int[] getKMPNext(String str) {
//创建一个next数组保存部分匹配值，大小与str长度相同
int[] next = new int[str.length()];
//长度为1时的部分匹配值为0，因为前缀和后缀最大相等部分不存在。
next[0] = 0;
for (int i = 1, j = 0; i < str.length(); i++) {
//当前缀和后缀不存在相等部分时调整j的位置
while (j > 0 && str.charAt(i) != str.charAt(j)) {
j = next[j - 1];
}
//相等则部分匹配值就+1
if (str.charAt(i) == str.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
贪心算法——接近最优解
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。
介绍
-
贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
-
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。
思路分析
穷举法实现——组合太多
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算10个子集。
| 广播台数量n | 子集总数2ⁿ | 需要的时间 |
|---|---|---|
| 5 | 32 | 3.2秒 |
| 10 | 1024 | 102.4秒 |
| 32 | 4294967296 | 13.6年 |
| 100 | 1.26*100³º | 4x10²³年 |
贪心算法实现——接近最优解
- 使用贪婪算法，效率高:目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:
- 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
- 将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
- 重复第1步直到覆盖了全部的地区
代码示例
场景
public class Greedy {
//[K1, K2, K3, K5]
public static void main(String[] args) {
//初始化数据，创建电台对应的覆盖地区及总的地区集合
HashMap<String, HashSet> hashMap = new HashMap<>();
HashSet<String> hashSet = new HashSet<>();
hashSet.add("北京");
hashSet.add("上海");
hashSet.add("天津");
hashMap.put("K1", hashSet);
HashSet<String> hashSet1 = new HashSet<>();
hashSet1.add("北京");
hashSet1.add("广州");
hashSet1.add("深圳");
hashMap.put("K2", hashSet1);
HashSet<String> hashSet2 = new HashSet<>();
hashSet2.add("成都");
hashSet2.add("上海");
hashSet2.add("杭州");
hashMap.put("K3", hashSet2);
HashSet<String> hashSet3 = new HashSet<>();
hashSet3.add("上海");
hashSet3.add("天津");
hashMap.put("K4", hashSet3);
HashSet<String> hashSet4 = new HashSet<>();
hashSet4.add("杭州");
hashSet4.add("大连");
hashMap.put("K5", hashSet4);
//所有地区
HashSet<String> all = new HashSet<>();
all.addAll(hashSet);
all.addAll(hashSet1);
all.addAll(hashSet2);
all.addAll(hashSet3);
all.addAll(hashSet4);
HashSet<String> maxSet = new HashSet<>();
//添加路径，贪心算法的选择路径（选择的电台）
HashSet<String> path = new HashSet<>();
//当覆盖地区不为0时表示还有地区没被覆盖
while (all.size() > 0) {
HashMap<String, Object> maxKey = new HashMap<>();
maxKey.clear();
maxSet.clear();
for (String key : hashMap.keySet()) {
HashSet<String> tempSet = hashMap.get(key);
//与未被覆盖地区取交集，如果电台key为空或者其覆盖的地区小于遍历出来的这个电台则替换
//目的是每次都要取得最佳的选择，这也是贪心算法的核心所在，虽然这样处理不一定是最优解，
// 但肯定是无限接近最优解的一种方法
tempSet.retainAll(all);
if (tempSet.size() > 0 && (!maxKey.containsKey("maxKey") || (Integer) maxKey.get("maxKeySize") < tempSet.size())) {
maxKey.put("maxKey", key);
maxKey.put("maxKeySize", tempSet.size());
maxSet.addAll(tempSet);
}
}
//存在选择电台则添加到选择的路径中
if (maxKey.containsKey("maxKey")) {
path.add((String) maxKey.get("maxKey"));
//清除本次已覆盖的地区
all.removeAll(maxSet);
}
}
System.out.println(path);
}
}
普里姆算法——Prim——MSP——修路问题——最小生成树——最短路径算法
最小生成树——MST——Minimum Cost Spanning Tree
求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法.
修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。
- 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
- N个顶点，一定有N-1条边
- 包含全部顶点
- N-1条边都在图中
介绍
普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。
普利姆的算法如下:
- 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
- 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1
- 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited[vj]=1
- 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边
思路分析
参考下方的思路图，本质就是从某一个顶点出发，去找该顶点临近的最短路径的两个顶点的权值，权值最小的就是最短路径；然后再从这两个顶点出发，去寻找所能找到的与这两个顶点相邻的最短的路径，找到的权值最小的就是本轮的最短路径，并得到最短路径对应的顶点，以此类推，再从这三个顶点出发，去寻找还未关联的顶点中最短的那条路径是哪条对应的哪个顶点，直到连接所有的顶点，这时候假设有n个顶点，那么总的就将找到n-1条边，他们的加权值就是最短路径，也就是该最小生成树的权值。
代码示例
场景
//修路问题是多对多的图
public class Graph {
//顶点的个数
private int vertexNum;
//顶点名称
private String[] data;
//边数据，邻接矩阵表示
private int[][] weights;
public int getVertexNum() {
return vertexNum;
}
public void setVertexNum(int vertexNum) {
this.vertexNum = vertexNum;
}
public String[] getData() {
return data;
}
public void setData(String[] data) {
this.data = data;
}
public int[][] getWeights() {
return weights;
}
public void setWeights(int[][] weights) {
this.weights = weights;
}
public Graph(int vertexNum) {
this.vertexNum = vertexNum;
this.data = new String[vertexNum];
this.weights = new int[vertexNum][vertexNum];
}
//显示村庄的邻接矩阵
public void showGraph(){
for (int[] weight : weights) {
System.out.println(Arrays.toString(weight));
}
}
//初始化村庄图
public static Graph initializeGraph(String[] data, int[][] weights) {
Graph graph = new Graph(data.length);
for (int i = 0; i < data.length; i++) {
graph.data[i] = data[i];
for (int j = 0; j < data.length; j++) {
graph.weights[i][j] = weights[i][j];
}
}
return graph;
}
}
public class Prim {
public static void main(String[] args) {
String[] data = new String[]{"A", "B", "C", "D", "E", "F", "G"};
//邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
int[][] weight = new int[][]{
{10000, 5, 7, 10000, 10000, 10000, 2},
{5, 10000, 10000, 9, 10000, 10000, 3},
{7, 10000, 10000, 10000, 8, 10000, 10000},
{10000, 9, 10000, 10000, 10000, 4, 10000},
{10000, 10000, 8, 10000, 10000, 5, 4},
{10000, 10000, 10000, 4, 5, 10000, 6},
{2, 3, 10000, 10000, 4, 6, 10000},};
Graph graph = Graph.initializeGraph(data, weight);
graph.showGraph();
Prim.prim(graph,0);
}
/**
* 普里姆算法求最小生成树，修路问题
*
* @param graph
* @param v
*/
public static void prim(Graph graph, int v) {
//定义一个顶点已被访问标记数组
int[] visited = new int[graph.getVertexNum()];
//先把传进来的顶点v标记为已访问
visited[v] = 1;
//记录本轮两个最短连接的顶点的下标
int v1 = -1;
int v2 = -1;
//因为n个顶点对应最短连接是n-1条边，因此只要遍历搜索n-1次去获取n-1条边即可
for (int i = 1; i < graph.getVertexNum(); i++) {
//初始化本轮最短路径的值以作比较
int minWeight = 10000;
for (int j = 0; j < graph.getVertexNum(); j++) {
for (int k = 0; k < graph.getVertexNum(); k++) {
//visited[j] == 1 表示已访问的顶点 ， visited[k] == 0表 示还未被访问的顶点
//这里求的就是一轮遍历下来，已被访问的顶点到未被访问的顶点中距离最短的两个顶点的下标的位置及其权值
if (visited[j] == 1 && visited[k] == 0 && graph.getWeights()[j][k] < minWeight) {
//替换最短权值和顶点
v1 = j;
v2 = k;
minWeight = graph.getWeights()[j][k];
}
}
}
//打印本轮最小
System.out.println("边<" + graph.getData()[v1] + "," + graph.getData()[v2] + "> 权值:" + minWeight);
//标记未被访问的最短距离顶点为已访问
visited[v2] = 1;
}
}
/**
* [10000, 5, 7, 10000, 10000, 10000, 2]
* [5, 10000, 10000, 9, 10000, 10000, 3]
* [7, 10000, 10000, 10000, 8, 10000, 10000]
* [10000, 9, 10000, 10000, 10000, 4, 10000]
* [10000, 10000, 8, 10000, 10000, 5, 4]
* [10000, 10000, 10000, 4, 5, 10000, 6]
* [2, 3, 10000, 10000, 4, 6, 10000]
* 边<A,G> 权值:2
* 边<G,B> 权值:3
* 边<G,E> 权值:4
* 边<E,F> 权值:5
* 边<F,D> 权值:4
* 边<A,C> 权值:7
*/
}
克鲁斯卡尔算法——Kruskal——公交站问题——最小生成树——最短路径算法
介绍
- 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
- 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
- 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
思路分析
首先就是对所有边的权值进行大小排序，然后从小到大添加到最小生成树中，添加时判断是否形成了回路，如果形成回路则不能用，继续寻找下一条边， 直到所有顶点都包含进去。
代码示例
克鲁斯卡尔最佳实践-公交站问题
看一个公交站问题：
有北京有新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通
各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里
问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
public class Kruskal {
private int edgeNum; //边的个数
private char[] vertexs; //顶点数组
private int[][] matrix; //邻接矩阵
//使用 INF 表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//克鲁斯卡尔算法的邻接矩阵
int matrix[][] = {
/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ { 0, 12, INF, INF, INF, 16, 14},
/*B*/ { 12, 0, 10, INF, INF, 7, INF},
/*C*/ { INF, 10, 0, 3, 5, 6, INF},
/*D*/ { INF, INF, 3, 0, 4, INF, INF},
/*E*/ { INF, INF, 5, 4, 0, 2, 8},
/*F*/ { 16, 7, 6, INF, 2, 0, 9},
/*G*/ { 14, INF, INF, INF, 8, 9, 0}};
//大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.
//创建KruskalCase 对象实例
Kruskal kruskalCase = new Kruskal(vertexs, matrix);
//输出构建的
kruskalCase.print();
kruskalCase.kruskal();
}
/**
*邻接矩阵为:
*
* 0 12 2147483647 2147483647 2147483647 16 14
* 12 0 10 2147483647 2147483647 7 2147483647
* 2147483647 10 0 3 5 6 2147483647
* 2147483647 2147483647 3 0 4 2147483647 2147483647
* 2147483647 2147483647 5 4 0 2 8
* 16 7 6 2147483647 2 0 9
* 14 2147483647 2147483647 2147483647 8 9 0
* 图的边的集合=[EData [<A, B>= 12], EData [<A, F>= 16], EData [<A, G>= 14], EData [<B, C>= 10], EData [<B, F>= 7], EData [<C, D>= 3], EData [<C, E>= 5], EData [<C, F>= 6], EData [<D, E>= 4], EData [<E, F>= 2], EData [<E, G>= 8], EData [<F, G>= 9]] 共12
* 最小生成树为
* EData [<E, F>= 2]
* EData [<C, D>= 3]
* EData [<D, E>= 4]
* EData [<B, F>= 7]
* EData [<E, G>= 8]
* EData [<A, B>= 12]
*/
//构造器
public Kruskal(char[] vertexs, int[][] matrix) {
//初始化顶点数和边的个数
int vlen = vertexs.length;
//初始化顶点, 复制拷贝的方式
this.vertexs = new char[vlen];
for(int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边, 使用的是复制拷贝的方式
this.matrix = new int[vlen][vlen];
for(int i = 0; i < vlen; i++) {
for(int j= 0; j < vlen; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
//统计边的条数
for(int i =0; i < vlen; i++) {
for(int j = i+1; j < vlen; j++) {
if(this.matrix[i][j] != INF) {
edgeNum++;
}
}
}
}
public void kruskal() {
int index = 0; //表示最后结果数组的索引
int[] ends = new int[edgeNum]; //用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
//创建结果数组, 保存最后的最小生成树
EData[] rets = new EData[edgeNum];
//获取图中 所有的边的集合 ， 一共有12边
EData[] edges = getEdges();
System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12
//按照边的权值大小进行排序(从小到大)
sortEdges(edges);
//遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入
for(int i=0; i < edgeNum; i++) {
//获取到第i条边的第一个顶点(起点)
int p1 = getPosition(edges[i].start); //p1=4
//获取到第i条边的第2个顶点
int p2 = getPosition(edges[i].end); //p2 = 5
//获取p1这个顶点在已有最小生成树中的终点
int m = getEnd(ends, p1); //m = 4
//获取p2这个顶点在已有最小生成树中的终点
int n = getEnd(ends, p2); // n = 5
//是否构成回路
if(m != n) { //没有构成回路
ends[m] = n; // 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]
rets[index++] = edges[i]; //有一条边加入到rets数组
}
}
//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
//统计并打印 "最小生成树", 输出 rets
System.out.println("最小生成树为");
for(int i = 0; i < index; i++) {
System.out.println(rets[i]);
}
}
//打印邻接矩阵
public void print() {
System.out.println("邻接矩阵为:
");
for(int i = 0; i < vertexs.length; i++) {
for(int j=0; j < vertexs.length; j++) {
System.out.printf("%12d", matrix[i][j]);
}
System.out.println();//换行
}
}
/**
* 功能：对边进行排序处理, 冒泡排序
* @param edges 边的集合
*/
private void sortEdges(EData[] edges) {
for(int i = 0; i < edges.length - 1; i++) {
for(int j = 0; j < edges.length - 1 - i; j++) {
if(edges[j].weight > edges[j+1].weight) {//交换
EData tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
/**
*
* @param ch 顶点的值，比如'A','B'
* @return 返回ch顶点对应的下标，如果找不到，返回-1
*/
private int getPosition(char ch) {
for(int i = 0; i < vertexs.length; i++) {
if(vertexs[i] == ch) {//找到
return i;
}
}
//找不到,返回-1
return -1;
}
/**
* 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组
* 是通过matrix 邻接矩阵来获取
* EData[] 形式 [['A','B', 12], ['B','F',7], .....]
* @return
*/
private EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];
for(int i = 0; i < vertexs.length; i++) {
for(int j=i+1; j <vertexs.length; j++) {
if(matrix[i][j] != INF) {
edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges;
}
/**
* 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同
* @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
* @param i : 表示传入的顶点对应的下标
* @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解
*/
private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
while(ends[i] != 0) {
i = ends[i];
}
return i;
}
}
public class EData {
char start; //边的一个点
char end; //边的另外一个点
int weight; //边的权值
//构造器
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
//重写toString, 便于输出边信息
@Override
public String toString() {
return "EData [<" + start + ", " + end + ">= " + weight + "]";
}
}
迪杰斯特拉算法
待补充
弗洛伊德算法
待补充
马踏棋盘算法
待补充
参考文献
[图形化数据结构](https://www.cs.usfca.edu/~galles/visualization/Algorithms.