12. 图的进阶

12. 图的进阶

12.1 有向图

在实际生活中，很多应用相关的图都是有方向性的，最直观的就是网络，可以从A页面通过链接跳转到B页面，那么a和b连接的方向是a->b,但不能说是b->a,此时我们就需要使用有向图来解决这一类问题，它和我们之前学习的无向图，最大的区别就在于连接是具有方向的，在代码的处理上也会有很大的不同。

12.1.1 有向图的定义及相关术语

定义：

有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。

出度：

由某个顶点指出的边的个数称为该顶点的出度。

入度：

指向某个顶点的边的个数称为该顶点的入度。

有向路径：

由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。

有向环：

一条至少含有一条边，且起点和终点相同的有向路径。

一副有向图中两个顶点v和w可能存在以下四种关系：

1. 没有边相连；

2. 存在从v到w的边v—>w;

3. 存在从w到v的边w—>v;

4. 既存在w到v的边，也存在v到w的边，即双向连接；

理解有向图是一件比较简单的，但如果要通过眼睛看出复杂有向图中的路径就不是那么容易了。

12.1.2 有向图API设计

在api中设计了一个反向图，其因为有向图的实现中，用adj方法获取出来的是由当前顶点v指向的其他顶点，如果能得到其反向图，就可以很容易得到指向v的其他顶点。

12.1.3 有向图实现

package com.ynu.Java版算法.U12_图的进阶.T1_有向图;import java.util.LinkedList;
import java.util.Queue;/*** @author ybh* @date 2023.03.26 10:56*/
public class Digraph {// 记录顶点的数量private int V;// 边的数量private int E;// 邻接表private Queue<Integer>[] adj;public Digraph(int V) {this.V = V;E = 0;// 邻接表的大小应该和顶点数量相同this.adj = new Queue[V];// 初始化邻接表的空队列for (int i = 0; i < adj.length; i++) {adj[i] = new LinkedList<>();}}// 获取顶点数量public int getV() {return V;}//获取边的数目public int E() {return E;}//向有向图中添加一条边 v->wpublic void addEdge(int v, int w) {//由于有向图中边是有向的，v->w 边，只需要让w出现在v的邻接表中，而不需要让v出现在w的邻接表中//无向图的话两个都要加adj[v].add(w);//边的数目自增1E++;}//获取由v指出的边所连接的所有顶点public Queue<Integer> adj(int v) {return adj[v];}//该图的反向图private Digraph reverse() {//创建新的有向图对象Digraph r = new Digraph(V);//遍历0~V-1所有顶点,拿到每一个顶点vfor (int v = 0; v < V; v++) {//得到原图中的v顶点对应的邻接表,原图中的边为 v->w,则反向图中边为w->v;for (Integer w : adj(v)) {r.addEdge(w, v);}}return r;}}

12.2 拓扑排序

​ 在现实生活中，我们经常会同一时间接到很多任务去完成，但是这些任务的完成是有先后次序的。以我们学习java学科为例，我们需要学习很多知识，但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础，到jsp/servlet，到ssm，到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础，学习ssm框架前要掌握jsp/servlet之类才行。

为了简化问题，我们使用整数为顶点编号的标准模型来表示这个案例：

此时如果某个同学要学习这些课程，就需要指定出一个学习的方案，我们只需要对图中的顶点进行排序，让它转换为一个线性序列，就可以解决问题，这时就需要用到一种叫拓扑排序的算法。

拓扑排序：

给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。下列是一副拓扑排序后的示意图：

能进行拓扑排序的必然是一个无环的图。

12.2.1 检测有向图中的环

如果学习x课程前必须先学习y课程，学习y课程前必须先学习z课程，学习z课程前必须先学习x课程，那么一定是有问题了，我们就没有办法学习了，因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环：

因此，如果我们要使用拓扑排序解决优先级问题，首先得保证图中没有环的存在。

12.2.1.2 检测有向环的API设计

12.2.1.2 检测有向环实现

在API中添加了onStack[] 布尔数组，索引为图的顶点，当我们深度搜索时：

1. 如果当前顶点正在搜索，则把对应的onStack数组中的值改为true，标识进栈；
2. 如果当前顶点搜索完毕，则把对应的onStack数组中的值改为false，标识出栈；
3. 如果即将要搜索某个顶点，但该顶点已经在栈中，则图中有环；

代码：

package com.ynu.Java版算法.U12_图的进阶.T1_有向图;import java.util.LinkedList;
import java.util.Queue;/*** @author ybh* @date 2023.03.26 10:56*/
public class Digraph {// 记录顶点的数量private int V;// 边的数量private int E;// 邻接表private Queue<Integer>[] adj;public Digraph(int V) {this.V = V;E = 0;// 邻接表的大小应该和顶点数量相同this.adj = new Queue[V];// 初始化邻接表的空队列for (int i = 0; i < adj.length; i++) {adj[i] = new LinkedList<>();}}// 获取顶点数量public int V() {return V;}//获取边的数目public int E() {return E;}//向有向图中添加一条边 v->wpublic void addEdge(int v, int w) {//由于有向图中边是有向的，v->w 边，只需要让w出现在v的邻接表中，而不需要让v出现在w的邻接表中//无向图的话两个都要加adj[v].add(w);//边的数目自增1E++;}//获取由v指出的边所连接的所有顶点public Queue<Integer> adj(int v) {return adj[v];}//该图的反向图private Digraph reverse() {//创建新的有向图对象Digraph r = new Digraph(V);//遍历0~V-1所有顶点,拿到每一个顶点vfor (int v = 0; v < V; v++) {//得到原图中的v顶点对应的邻接表,原图中的边为 v->w,则反向图中边为w->v;for (Integer w : adj(v)) {r.addEdge(w, v);}}return r;}}package com.ynu.Java版算法.U12_图的进阶.T2_拓扑排序;import com.ynu.Java版算法.U12_图的进阶.T1_有向图.Digraph;/*** @author ybh* @date 2023.03.26 13:41*/
public class DirectedCycleTest {public static void main(String[] args) {// 创建有4个顶点的图Digraph digraph = new Digraph(4);digraph.addEdge(0,1);digraph.addEdge(1,2);digraph.addEdge(2,3);digraph.addEdge(3,0);DirectedCycle cycle = new DirectedCycle(digraph);System.out.println("图"+ (cycle.hasCycle()?"有环":"无环"));}
}

12.2.2 有向无环图基于深度优先的顶点排序

​ 如果要把图中的顶点生成线性序列其实是一件非常简单的事，之前我们学习并使用了多次深度优先搜索，我们会发现其实深度优先搜索有一个特点，那就是在一个连通子图上，每个顶点只会被搜索一次，如果我们能在深度优先搜索的基础上，添加一行代码，只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事。

12.2.2.1 顶点排序API设计

12.2.2.2 顶点排序实现

在API的设计中，我们添加了一个栈reversePost用来存储顶点，当我们深度搜索图时，每搜索完毕一个顶点，把该顶点放入到reversePost中，这样就可以实现顶点排序。

package com.ynu.Java版算法.U12_图的进阶.T2_拓扑排序.S2_深度优先顶点排序;import com.ynu.Java版算法.U12_图的进阶.T1_有向图.Digraph;import java.util.Queue;
import java.util.Stack;/*** @author ybh* @date 2023.03.26 17:25*/
public class DepthFirstOrder {//索引代表顶点，值表示当前顶点是否已经被搜索private boolean[] marked;//使用栈，存储顶点序列private Stack<Integer> reversePost;//创建一个检测环对象，检测图G中是否有环public DepthFirstOrder(Digraph digraph) {//创建一个和图的顶点数一样大小的marked数组this.marked = new boolean[digraph.V()];this.reversePost = new Stack<>();// 遍历搜索图的每个节点for (int i = 0; i < digraph.V(); i++) {if (!marked[i]){//如果当前顶点没有搜索过，则搜索dfs(digraph,i);}}}//基于深度优先搜索。private void dfs(Digraph digraph, int v) {//把当前顶点标记为已搜索marked[v] = true;//遍历v顶点的邻接表，得到每一个顶点wQueue<Integer> adj = digraph.adj(v);for (Integer w : adj) {//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点if (!marked[w]){dfs(digraph,w);}}//当前顶点已经搜索完毕，让当前顶点入栈reversePost.push(v);}//获取顶点线性序列public Stack<Integer> reversePost(){return reversePost;}
}

12.2.3 拓扑排序实现

前面已经实现了环的检测以及顶点排序，那么拓扑排序就很简单了，基于一幅图，先检测有没有环，如果没有环，则调用顶点排序即可。

API设计：

代码：

package com.ynu.Java版算法.U12_图的进阶.T2_拓扑排序.S2_深度优先顶点排序;import com.ynu.Java版算法.U12_图的进阶.T1_有向图.Digraph;import java.util.Queue;
import java.util.Stack;/*** @author ybh* @date 2023.03.26 17:25*/
public class DepthFirstOrder {//索引代表顶点，值表示当前顶点是否已经被搜索private boolean[] marked;//使用栈，存储顶点序列private Stack<Integer> reversePost;//创建一个检测环对象，检测图G中是否有环public DepthFirstOrder(Digraph digraph) {//创建一个和图的顶点数一样大小的marked数组this.marked = new boolean[digraph.V()];this.reversePost = new Stack<>();// 遍历搜索图的每个节点for (int i = 0; i < digraph.V(); i++) {if (!marked[i]){//如果当前顶点没有搜索过，则搜索dfs(digraph,i);}}}//基于深度优先搜索。private void dfs(Digraph digraph, int v) {//把当前顶点标记为已搜索marked[v] = true;//遍历v顶点的邻接表，得到每一个顶点wQueue<Integer> adj = digraph.adj(v);for (Integer w : adj) {//如果当前顶点w没有被搜索过，则递归搜索与w顶点相通的其他顶点if (!marked[w]){dfs(digraph,w);}}//当前顶点已经搜索完毕，让当前顶点入栈reversePost.push(v);}//获取顶点线性序列public Stack<Integer> reversePost(){return reversePost;}
}

12.3 加权无向图

持续学习中