摘要：1. 图 在现实生活中，有许多应用常见会包含很多点以及点点之间的连接，而这些应用场景可以用图这种数据结构来解决。 1.1 图的概述图的典
1. 图
在现实生活中，有许多应用常见会包含很多点以及点点之间的连接，而这些应用场景可以用图这种数据结构来解决。
1.1 图的概述图的典型例子有地图：
如果把城市看做是一个个的点，把道路看作是一条条的的连接，那么地图就是**“图”**这种数据结构
在这里插入图片描述电路图：
集成电路板其实就是由一个个触电组成的，并把触点与触点间通过线进行连接，这也是“图” 数据结构
在这里插入图片描述1.2 图的定义以及分类**定义：**图是由一组顶点和一组能够将两个顶点相连的边组成的。
在这里插入图片描述特殊的图：
自环：即一条连接一个顶点和其自身的边平行边，连接同一对顶点的两条边在这里插入图片描述图的分类：
按照连接两个顶点的边不同，可以把图分为以下两种：
**无向图：**边仅仅连接两个顶点，没有其他含义**有向图：**边不仅连接两个顶点，并且具有方向1.3 无向图1.3.1 图的相关术语相邻顶点：
当两个顶点通过一条边距相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点度：
某个顶点的度就是依附于该顶点的边的个数子图：
是一幅图的所有边的子集（包含这些边依附的顶点）组成的图路径：
是由边顺序连接的一系列顶点组成环：
是一条至少含有一条边且终点和起点相同的路径在这里插入图片描述连通图：
如果图中任意一个顶点都存在一条路径到达另一个顶点，那么这幅图就称为连通图连通子图：
一个非连通图由若干连通的部分组成，每个连通的部分都可以称作该图的连通子图在这里插入图片描述1.3.2 图的存储结构要表示一幅图，只需要表示清楚以下两部分内容即可：
图中所有顶点所有连接顶点的边常见的图的存储结构有两种：邻接矩阵和邻接表
1.3.2.1 邻接矩阵使用N*N的二维数组intN adj，把索引的值看作是顶点如果顶点v和顶点w相连，我们只需要将adjv和adjw的值设置为1，否则设置为0即可在这里插入图片描述1.3.2.2 邻接表使用一个大小为v的数组 Queuev adj，把索引看作是顶点每个索引处ajdv存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点在这里插入图片描述邻接矩阵的实现更加容易且易懂，但是临邻接矩阵所消耗的内存要比邻接表要多。 邻接表由于使用Queue来存储顶点，所以可以无限随时拓展而临界矩阵是一个二维数组，规定了指定的大小，因此邻接矩阵只能在某些时间要求大过空间要求时才会使用1.4 无向图的实现1.4.1 图的API 设计类名
Graph
构造方法
Graph(int v)：创建一个包含v个顶点但不包含边的图
成员方法
public int V：获取图中顶点的数量2. public int E：获取图 中边的数量3. public void addEdge(int v,int w)：向图中添加一条边v-w4. public Queue
private final int V：记录顶点数量2. private int E：记录边数量3. private Queue
private final int V;
private int E;
private Queue
public Graph(int V){
this.V = V;
this.E = 0;
this.adj = new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Queue
}
}
public int V(){
return V;
}
public int E(){
return E;
}
// 添加边
public void addEdge(int v,int w){
// 在无向图中，边是没有方向的
adj[v].enqueue(w);
adj[w].enqueue(v);
E++;
}
// 获取和顶点v相邻的所有顶点
public Queue
return adj[v];
}
// ####################### 深度优先搜索 ################## //
}1.5 图的搜索在很多情况下，我们需要遍历图， 得到图的一些信息，例如找出图中与指定的顶点相连的所有顶点，或者判定某个顶点与指定顶点是否相同，是非常常见的需求
有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索。
1.5.1 深度优先搜索所谓的深度优先搜索，指的是在搜索时，如果遇到一个节点既有子节点，又有兄弟节点，那么先找子节点，任何找兄弟节点
在这里插入图片描述API设计：类名
DepthFirstSearch
构造方法
DepthFirstSearch(Graph G,int s)：构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点
成员方法
private void dfs(Graph G,int V)：使用深度优先搜索找出G图中v顶点的所有相通顶点2. public boolean marked(int w)：判断w顶点与s顶点是否相通3. public int count()：获取与顶点s相通的所有顶点的总数成员变量
private boolean[] marked：索引代表顶点，指表示当前顶点是否已经被搜索2. private int count：记录有多少顶点与s顶点相通代码语言：javascript复制public class DepthFirstSearch {
private boolean[] marked;// 索引代表顶点，指表示当前顶点是否已经被搜索
public int count;// 记录有多少顶点与s顶点相通
/**
* 初始化构造
* @param G 图的对象
* @param s 顶点内容
*/
public DepthFirstSearch(Graph G,int s) {
this.marked = new boolean[G.V()];
this.count = 0;
// 使用深度优先搜索
dfs(G,s);
}
/**
* 使用深度优先搜索
* @param G
* @param v
*/
private void dfs(Graph G,int v){
// 把v顶点表示为已搜索
marked[v] = true;
// 查找每个顶点里的队列（相连节点）
for (Integer w: G.adj(v)) {
// 判断w顶点有没有被搜索过，如果没有被搜索过，则递归调用dfs方法
if (!marked[w]){
dfs(G,w);
}
};
// 相通数量+1；
count++;
}
public boolean marked(int w){
return marked[w];
}
public int count(){
return count;
}
}1.5.2 广度优先搜索所谓广度优先搜索指的是在搜索时，如果遇到一个节点既有子节点又有兄弟节点，那么先找兄弟节点，然后找子节点
在这里插入图片描述1.5.2.1 API设计类名
BreadthFirstSearch
构造方法
BreadthFirstSearch(Graph G,int s)：构造深度优先搜索对象，使用深度优先搜索找出G图中s顶点的所有相通顶点
成员方法
private void bfs(Graph G,int V)：使用深度优先搜索找出G图中v顶点的所有相通顶点2. public boolean marked(int w)：判断w顶点与s顶点是否相通3. public int count()：获取与顶点s相通的所有顶点的总数成员变量
private boolean[] marked：索引代表顶点，指表示当前顶点是否已经被搜索2. private int count：记录有多少顶点与s顶点相通3. private Queue
private boolean[] marked;// 索引代表顶点，指表示当前顶点是否已经被搜索
public int count;// 记录有多少顶点与s顶点相通
private Queue
/**
* 初始化构造
* @param G 图的对象
* @param s 顶点内容
*/
public BreadthFirstSearch(Graph G, int s) {
this.marked = new boolean[G.V()];
this.count = 0;
this.waitSeach = new Queue
bfs(G,s);
}
/**
* 使用广度优先搜索
* @param G
* @param v
*/
private void bfs(Graph G,int v){
// 把v顶点表示为已搜索
marked[v] = true;
waitSeach.enqueue(v);
/**
* 非真正意义上的广度优先搜索！
* 由于在31行添加元素，下方while进行循环，
* 找出弹出queue队列的最后顶点的邻接表，找到邻接表后，
* 直接递归了，第一次递归，找的是【最后顶点】的邻接表的第一个元素的再【邻接表】
* 所以从这方面来说还是深度优先搜索
*/
while (!waitSeach.isEmpty()){
// 弹出带搜索的顶点
Integer wait = waitSeach.dequeue();
// 遍历wait顶点的邻接表
for (Integer w : G.adj(wait)) {
// 判断邻接表中的顶点是否已经被搜索，没有被搜索，那么将继续进行递归调用搜索
if (!marked[w]){
bfs(G,w);
}
}
}
// 相通数量+1；
count++;
}
public boolean marked(int w){
return marked[w];
}
public int count(){
return count;
}
}1.6 路径查找在生活中，地图是经常使用的工具，通常我们会用它进行导航，输入一个触发城市，输入一个目的地城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市。这类问题翻译成专业问题就是：从s顶点到v顶点是否存在一条路径
在这里插入图片描述录入在上图上查找顶点0到顶点4的路径用红色标识处理啊，那么我们可以把该路径标识为 0-2-3-4
1.6.1 路径查找API设计类名
DepthFirstPaths
构造方法
DepthFirstPaths(Graph G,int s)：构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
成员方法
private void dfs(Graph G,int V)：使用深度优先搜索找出G图中v顶点的所有相通顶点2. public boolean hasPathTo(int v)：判断v顶点与s顶点是否存在路径3. public Stack
private boolean[] marked：所有代表顶点，指标识当前顶点是否已经被搜索2. private int s：起点3. private int[] edgeTo：索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点1.6.2 路径查找实现实现路径查找，最基本的操作还是得遍历并搜索图，所以，实现暂且基于深度优先搜索来完成。
在这里插入图片描述代码语言：javascript复制public class DepthFirstPaths {
private boolean[] marked;// 所有代表顶点，指标识当前顶点是否已经被搜索
private int[] edgeTo; // 索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
private int s;// 起点
//构造深度优先搜索对象，使用深度优先搜索找出G图中起点为s的所有路径
public DepthFirstPaths(Graph G,int s) {
this.marked = new boolean[G.V()];
this.s = s;
this.edgeTo = new int[G.V()];
// 使用深度优先搜索
dfs(G,s);
}
/**
* 使用深度优先搜索找出G图中v顶点的所有相通顶点
* @param G
* @param v
*/
private void dfs(Graph G,int v){
marked[v] = true;
// 遍历v的邻接表
for (Integer w : G.adj(v)) {
// 判断【邻接表顶点】是否已经被搜索，没有则递归
if (!marked[w]){
// 记录当前邻接表顶点可以通过哪个顶点到达
edgeTo[w] = v;
// 递归
dfs(G,w);
}
}
}
/**
* 判断v顶点与s顶点是否存在路径
* @param v
* @return
*/
public boolean hasPathTo(int v){
return marked[v];
}
/**
* 找出从起点s到顶点v的路径
* @param v 从起点s所要到达的顶点
*/
public Stack
// 判断v顶点是否可达，不可达直接返回null
if (!hasPathTo(v))
{
return null;
}
// 创建栈对象，保存路径中的所有顶点
Stack
// 通过循环，从顶点v开始，一直往前找，找到v对应可到达的顶点为止
for (int i =v;i != s;i = edgeTo[i]){
path.push(i);
}
// 存入起点
path.push(s);
return path;
}
}2. 前置文章浅入数据结构 “堆” - 实现和理论开始熟悉 “二叉树” 的数据结构队列 和 符号表 两种数据结构的实现队列的进阶结构-优先队列2-3树思想与红黑树的实现与基本原理B树和B+树的实现原理阐述3. ES8 如何使用?快来看看这篇好文章吧~~！！
😊👉（全篇详细讲解）ElasticSearch8.7 搭配 SpringDataElasticSearch5.1 的使用
