（JAVA）有向图与拓扑排序的实现原理与基本实现
1. 有向图
生活中，很多应用相关的图都是由方向性的，最直观的就是网络，可以从A页面通过连接跳转到B页面，那么a和b连接的方向是 a>b，但不能说b<a，此时我们就需要使用有向图来解决这一类问题。
1.1 有向图的定义及相关术语
1.1.1 定义
有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的灌顶啊
1.1.2 相关术语
出度：
- 由某个顶点指出的边的个数称为该顶点的出度
入度：
- 指向某个顶点的边的个数称为该顶点的入度
有向路径：
- 由一系列顶点组成，对于其中的某个顶点都存在一条有向边，从它指向序列中的下一个顶点
有向环：
- 一条至少含有一条边，且起点和终点相通的有向路径
一副有向图中两个顶点v和w可能存在以下四种关系：
- 没有边相连；
- 存在从v到w的边
- 存在从w到v的边
- 既存在w到v的边，也存在v到w的边，即双向链接
理解有向图是比较简单的，但如果要通过眼睛看出复杂有向图中的路径就不是那么容易了
1.2 有向图的API设计
| 类名 | Digraph |
|---|---|
| 构造方法 | Digraph(int V)：创建一个包含V个顶点但不包含边的有向图 |
| 成员方法 | 1. public int V()：获取图中顶点的数量 2. public int E()：获取图中边的数量 3. public void addEdge(int v,int w)：向有向图中添加一条边 4. public Queue<Integer> adj(int v)：获取由v指出的边所连接的所有顶点 5. private Digraph reverse()：该图的反向图 |
| 成员变量 | 1. private final int V：记录顶点数量 2. private int E：记录边数量 3. private Queue<Integer>[] adj：邻接表 |
在api中涉及了一个反向图，其因为有向图的实现中，用adj方法获取出来的是由当前顶点v指向的其他顶点，如果能得到其反向图，就可以很容易得到指向v的其他顶点
2. 拓扑排序
对图中的定的顶点进行排序，让它转换为一个线性序列，就可以解决问题，而这种将图中顶点转换的算法称为：拓扑算法
2.1 检测有向图中的环
如果学习x课程前必须先学习y课程，学习y课程必须先学习z课程，学习z课程前必须先学习x课程，那么一定是有问题了，我们就没办法学习了，因为这三个条件没有办法同时满足。这样三门课程的学习过程就组成了一个环：
因此，如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在
2.1.1 检测有向环的API设计
| 类名 | DirectedCycle |
|---|---|
| 构造方法 | DirectedCycle(Digraph G)：创建一个检测环对象，检测图G中是否有环 |
| 成员方法 | 1. private void dfs(Digraph G,int V)：基于深度优先搜索，检测图G中是否有环 2. public boolean hasCycle()：判断图中是否有环 |
| 成员变量 | 1. private boolean[] marked：索引代表顶点，值表示当前顶点是否已经被搜索 2. private boolean hasCycle：记录图中是否有环 3. private boolean[] onStack：索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上 |
2.1.2 检测有向环的实现
在API中添加了onStack[] 布尔数组，索引为图的顶点，当我们深度搜索时：
- 在如果当前顶点正在搜索，则把对于的onStack数组中的值改为true，标识压栈；
- 如果当前顶点搜索完毕，则把对于的onStack数组中的值改为false，标识弹栈；
- 如果即将要搜索某个顶点，但该顶点已经在栈中，则图中有环；
2.2 基于深度优先搜索的顶点排序
如果要把图中的顶点生成线性序列其实是一件非常简单的事。
深度优先搜索有一个特点，那就是在一个连通子图上，每个顶点只会被搜索一次，如果我们能在深度优先搜索的基础上，添加一行代码只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事
2.2.1 顶点排序API设计
| 类名 | DepthFirstOrder |
|---|---|
| 构造方法 | DepthFirstOrder(Digraph G)：创建一个顶点排序对象，生成顶点线性序列 |
| 成员方法 | 1. private void dfs(Digraph G,int V)：基于深度优先搜索，生成顶点线性序列 2. public Stack<Integer> reversePost()：获取顶点线性序列 |
| 成员变量 | 1. private boolean[] marked：索引代表顶点，值标识当前顶点是否已经被搜索 2. private Stack<Integer> reversePost：使用栈，存储顶点序列 |
2.2.2 顶点排序实现
在API的设计中，我们添加了一个栈erverrsePost用来存储顶点，当我们深度搜索图时，每搜索完一个顶点，把该顶点放入到reversePost中，这样就可以实现顶点排序
2.3 拓扑排序的实现
实现了环的检测以及顶点排序，那么拓扑排序就很简单了，基于一幅图，先检测有没有环，如果没有环，则调用顶点排序即可
2.3.1 API设计
| 类名 | TopoLogical |
|---|---|
| 构造方法 | TopoLogical(Digraph G)：构造拓扑排序对象 |
| 成员方法 | 1. public boolean isCycle()：判断图G是否有环 2. public Stack<Integer> order()：获取拓扑排序的所有顶点 |
| 成员变量 | 1. private Stack<Integer> order：顶点的拓扑排序 |
2.3.2 实现代码
package com.renecdemo.graph;
import java.util.Stack;
// 拓扑排序
public class TopoLogical {
private Stack<Integer> order;
public TopoLogical(Digraph G) {
// 创建一个检测有向环的对象
DirectedCycle cycle = new DirectedCycle(G);
if (!cycle.hasCycle()){
// 使用有向图的顶点排序进行排序，得到排序后的栈
DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
order = depthFirstOrder.reversePost();
}
}
public boolean isCycle(){
return order == null;
}
public Stack<Integer> order(){
return order;
}
}
顶点排序
public class DepthFirstOrder {
// 索引代表顶点，值标识当前顶点是否已经被搜索
private boolean[] marked;
// 使用栈，存储顶点序列
private Stack<Integer> reversePost;
// 初始化
public DepthFirstOrder(Digraph G) {
this.marked = new boolean[G.V()];
this.reversePost = new Stack<>();
// 遍历图中的每个顶点，让每个顶点作为入口，完成一次深度优先搜索
for (int v = 0; v < G.V(); v++) {
// 判断顶点是否被搜索，没有则深度优先搜索
if (!marked[v]){
dfs(G,v);
}
}
}
/**
* 深度优先搜索
* @param G 搜索所在的图
* @param v 搜索的顶点
*/
private void dfs(Digraph G,int v){
// 标记v顶点已搜索
marked[v] = true;
// 循环深度搜索顶点v
for (Integer w : G.adj(v)) {
if (!marked[w])
{
dfs(G,w);
}
}
// 每次搜索，搜索完成的顶点都压入栈中
reversePost.push(v);
}
/**
* 返回栈
*/
public Stack<Integer> reversePost(){
return reversePost;
}
}
3. 前置文章
- 浅入数据结构 “堆” - 实现和理论
- 开始熟悉 “二叉树” 的数据结构
- 队列 和 符号表 两种数据结构的实现
- 队列的进阶结构-优先队列
- 2-3树思想与红黑树的实现与基本原理
- B树和B+树的实现原理阐述
- 图的基本原理和API实现
4. ES8 如何使用?
快来看看这篇好文章吧~~！！
😊👉（全篇详细讲解）ElasticSearch8.7 搭配 SpringDataElasticSearch5.1 的使用
原文地址：https://blog.csdn.net/ZunXin_2580/article/details/142970425
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！