二叉排序树——BST——Binary Sort(Search) Tree
二叉排序树的出现是为了解决数组的查询快，但是插入删除慢；而链表的插入删除快，但查询慢而引出的一种查询和插入删除都相对较快的一种数据结构。
介绍
二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点。
二叉排序树.png
思路分析
插入和遍历思路分析
插入就是按照左子节点的值比当前节点的值小，右子节点的值比当前节点的值大的规则来对节点进行递归比较插入，而遍历只需要按照普通的前序、中序、后序遍历即可。
删除思路分析
二叉排序树1.png
二叉排序树2.png
二叉排序树3.png
代码示例
一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 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树
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。取自这三个人的名字首字母。
解决二叉排序树在极端情况下退化为链表的问题。
平衡二叉树首先是一颗二叉排序树，这是前提。
AVL.png
基本介绍
- 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
- 具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL(算法)、替罪羊树、Treap、伸展树等。
左旋转——【右子树高度 - 左子树高度>1】
什么时候进行左旋转
左旋转即当AVL树在进行添加或者删除节点操作的时候，首先我们会按照二叉排序树的添加规则进行数据的添加或者删除，但是，在完成添加或者删除的时候，会对该二叉平衡树进行计算左右两个子树的高度差是否满足不超过1，并且左右两个子树都是一棵平衡二叉树，如果不满足，且右边的高度减去左边的高度大于1，这时候就要进行左旋转，使其满足平衡二叉树的规则。
左旋操作思路
本质就是让根节点的右子节点成为新的根节点，而原来的根节点作为新的根节点的左子节点，以达到平衡的目的。
思路分析
AVL1.png
AVL2.png
右旋转——【左子树高度 - 右子树高度>1】
跟左旋转相反。
AVL3.png
AVL4.png
双旋转——单旋转不能完成平衡二叉树的转换
在某些情况下单纯的左右旋转并不能完成平衡二叉树的转换。
int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL树.
int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL树
如下图所示：
AVL5.png
AVL.png
思路分析，针对这种需要进行右旋转的树，还需要先判断其左子树的右子树高度是否比该左子树的左子树高度高，如果高的话，就要先对这个左子节点先进行左旋转操作，也就是让高度偏向左边，再来做整棵树的右旋转才能有效。
代码示例——左旋转、右旋转、双旋转
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
图的出现是为了解决多对多关系
线性表局限于一个直接前驱和一个直接后继的关系，树也只能有一个直接前驱也就是父节点。
当我们需要表示多对多的关系时， 这里我们就用到了图。
基本介绍
图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。生活中比如地铁交汇的线路图等。
图.png
图2.png
图的表示方式
图的表示方式有两种：二维数组表示（邻接矩阵）；数组加链表表示（邻接表）。
邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。
图3.png
邻接表
邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失。
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。
图4.png
图遍历介绍
深度优先遍历用递归，广度优先遍历用队列。
所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略:
- 深度优先遍历
- 广度优先遍历。
图的深度优先遍历——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。
代码示例
对下图进行深度优先遍历和广度优先遍历
图5.png
//图，邻接矩阵实现
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();
}
}
