18、数据结构与算法 - 实战：图
1、基本介绍
线性表局限于一个直接前驱和一个直接后继的关系，树也只能有一个直接前驱，也就是父结点。当我们需要表示多对多的关系时，就会用到图这个结构。
图是一种数据结构，其中的结点也称为顶点，两个顶点之间的连接称为边。
2、图的常用概念
1、顶点（vertex）：即结点；
2、边（edge）：两个顶点之间的连线；
3、路径：一个顶点到另一个顶点直接的连线集合；
4、无向图
5、有向图
6、带权图
3、图的表示方式
图的表示方式主要有两种：二维数组表示（邻接矩阵）和链表表示（邻接表）。
3.1 邻接矩阵
邻接矩阵是表示图中顶点之间相邻关系的矩阵，对于N个顶点的图而言，矩阵是由row和col表示的1,…,N个点。
3.2 邻接表
上面邻接矩阵需要为每一个顶点都分配n个边空间，其实大部分的边都是不存在的，会造成空间的一定损失，而邻接表则只关心存在的边，不关心不存在的边，因此没有空间的浪费。
邻接表由数组+链表组成。
4、图的代码实现
代码中，图用邻接矩阵表示。
package cn.klb.datastructures.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/4/18 18:59
* @Modified By:
*/
public class Graph {
private ArrayList<String> vertexsList; // 存储图的顶点
private int[][] edges; // 存储图对应的邻接矩阵
private int numberOfEdges; // 图的边的个数
public Graph(int n) {
this.edges = new int[n][n];
this.vertexsList = new ArrayList<String>(n);
numberOfEdges = 0;
}
/**
* 显示图对应的邻接矩阵
*/
public void showGraph() {
for (int[] link : edges) {
System.out.println(Arrays.toString(link));
}
}
/**
* 返回顶点的个数
*
* @return
*/
public int getNumberOfVertexs() {
return this.vertexsList.size();
}
/**
* 获取图中边的个数
*
* @return
*/
public int getNumberOfEdges() {
return this.numberOfEdges;
}
/**
* 返回第 index 个顶点
*
* @param index
* @return
*/
public String getVertexsByIndex(int index) {
return vertexsList.get(index);
}
/**
* 获取顶点的索引
*
* @param vertexs
* @return
*/
public int getIndexByVertexs(String vertexs) {
for (int index = 0; index < vertexsList.size(); index++) {
if (vertexs.equals(vertexsList.get(index))) {
return index;
}
}
return -1;
}
/**
* 插入顶点
*
* @param vertex
*/
public void insertVertex(String vertex) {
vertexsList.add(vertex);
}
/**
* 对v1和v2进行连接，边的权值未weight
*
* @param v1
* @param v2
* @param weight
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numberOfEdges++;
}
/**
* 对v1和v2进行连接，边的权值未weight
*
* @param v1
* @param v2
* @param weight
*/
public void insertEdge(String v1, String v2, int weight) {
edges[getIndexByVertexs(v1)][getIndexByVertexs(v2)] = weight;
edges[getIndexByVertexs(v2)][getIndexByVertexs(v1)] = weight;
numberOfEdges++;
}
}
5、图的遍历
所谓图的遍历，即是对结点的访问。一个图由那么多个结点，如何遍历这些结点，需要特定的策略，一般有两种访问策略：深度优先和广度优先。
5.1 深度优先遍历
5.1.1 基本思想
图的深度优先搜索（Depth First Search），从初始访问顶点出发，访问它的第一个邻接顶点，然后再以这个被访问的邻接顶点作为初始顶点，又访问第一个邻接顶点。即每次访问完当前顶点后首先访问当前顶点的第一个邻接顶点。
可以看出，这个访问策略是优先纵向挖掘深入，而不是对一个顶点的所有邻接顶点进行横向访问。显然，深度优先遍历是一个递归的过程。
5.1.2 算法步骤
1、访问初始顶点v，并标记顶点v为已访问；
2、查找顶点v的第一个邻接顶点w；
3、若w存在且未被访问过，则对w进行深度优先遍历递归；若w不存在或者存在但被访问过了，则查找结点v的w邻接结点后的下一个邻接结点，重复步骤3。
比如上面这个图，深度优先遍历的结果是：{1，2，4，8，5，3，6，7}
5.1.3 代码实现
/**
* 对图进行深度优先遍历
*/
public void dfs() {
isVisited = new boolean[vertexsList.size()];
for (int i = 0; i < getNumberOfVertexs(); i++) {
if (!isVisited[i]) {
doDFS(isVisited, i);
}
}
}
/**
* 深度优先遍历算法
*
* @param isVisited
* @param i
*/
private void doDFS(boolean[] isVisited, int i) {
// 访问顶点，输出
System.out.print(getVertexsByIndex(i) + " ");
// 把这个点设置为已读
isVisited[i] = true;
// 找到顶点i的第一个邻接顶点
int w = getNextNeighbor(i, -1);
while (w != -1) {
if (!isVisited[w]) {
doDFS(isVisited, w);
}
// 如果w已经被访问过了,就继续找下一个邻接顶点
w = getNextNeighbor(i, w);
}
}
/**
* v2是v1的邻接顶点，返回v2之后的下一个邻接顶点
*
* @param v1
* @param v2
* @return
*/
public int getNextNeighbor(int v1, int v2) {
for (int i = v2 + 1; i < vertexsList.size(); i++) {
if (edges[v1][i] > 0) {
return i;
}
}
return -1;
}
5.2 广度优先遍历
5.2.1 基本思想
广度优先搜索（Broad First Search）类似于分层搜索过程，遍历过程需要使用一个队列以保存访问过的顶点的顺序，以便按这个顺序来访问这些顶点的邻接顶点。
5.2.2 算法步骤
1、访问初始顶点v并标记顶点v为以访问；
2、顶点v入队列；
3、当队列不为空时，算法继续往下执行；
4、取出队列头顶点u；
5、查找顶点u的第一个邻接顶点w;
6、若顶点w不存在，则转到步骤3，否则向下执行；
6.1、若顶点w未被访问，则访问顶点w并把w标记为以访问；
6.2、顶点w入队列；
6.3、查找顶点u继w后的下一个邻接顶点，转到步骤6。
比如上面这个图，广度优先遍历的结果是：{1，2，3，4，5，6，7，8}
5.2.3 代码实现
/**
* 执行广度优先遍历
*/
public void bfs() {
isVisited = new boolean[vertexsList.size()];
for (int i = 0; i < getNumberOfVertexs(); i++) {
if (!isVisited[i]) {
doBFS(isVisited, i);
}
}
}
/**
* 广度优先遍历算法
*
* @param isVisited
* @param i
*/
private void doBFS(boolean[] isVisited, int i) {
// 用一个链表模拟队列，用于记录顶点的访问顺序
LinkedList queue = new LinkedList();
int u; // 表示队列的头顶点对应下标(是顶点的下标，不是队列的下标)
int w; // 邻接顶点
// 访问顶点，输出顶点信息
System.out.print(getVertexsByIndex(i) + " ");
// 访问过后就设置为已访问
isVisited[i] = true;
// 把顶点加入到队列
queue.add(i);
// 只要队列不空，就继续
while (!queue.isEmpty()) {
// 获取队列头顶点下标
u = (Integer) queue.removeFirst();
// 得到第一个邻接顶点的下标 w
w = getNextNeighbor(u, -1);
// -1 表示找不到邻接顶点
while (w != -1) {
if (!isVisited[w]) {
// 如果第一个邻接顶点没有被访问过，则输出
System.out.print(getVertexsByIndex(w) + " ");
isVisited[w] = true;
// 入队
// 会发现入队的全是w的邻接顶点，意思就是w的邻接顶点先遍历完
// 然后取出队列里的元素变为新的 u
queue.addLast(w);
}
// 以u为前驱点，找w后面的下一个邻顶点
w = getNextNeighbor(u, w);
}
}
}