【数据结构与算法】第十五、十六章：有向图、拓扑排序（检测环、顶点排序）

本文主要是介绍【数据结构与算法】第十五、十六章：有向图、拓扑排序（检测环、顶点排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

15、有向图

15.1、有向图的定义及相关术语

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

出度

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

指向某个顶点的边的个数称为该顶点的入度
有向路径

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

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

在这里插入图片描述

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

没有边相连
存在从v到w的边 v—>w
存在从w到v的边 w—>v
既存在w到v的边，也存在v到w的边，即双向连接

在这里插入图片描述

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

15.2、有向图API设计

在这里插入图片描述

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

package chapter15;import chapter03.Queue;/*** @author 土味儿* Date 2021/9/15* @version 1.0* 有向图*/
public class Digraph {/*** 顶点数量*/private final int vNum;/*** 边数量*/private int eNum;/*** 邻接表*/private Queue<Integer>[] adj;/*** 构造器** @param vNum*/public Digraph(int vNum) {// 初始化顶点数量this.vNum = vNum;// 初始化边数量this.eNum = 0;// 初始化邻接表this.adj = new Queue[vNum];// 初始化邻接表中的空队列for (int i = 0; i < vNum; i++) {this.adj[i] = new Queue<Integer>();}}/*** 得到顶点数量** @return*/public int getVNum() {return vNum;}/*** 得到边数量** @return*/public int geteNum() {return eNum;}/*** 添加一条边v-w** @param v* @param w*/public void addEdge(int v, int w) {// 因为是有向图，w加入到v的链表中this.adj[v].enQueue(w);//this.adj[w].enQueue(v);// 边数量加1eNum++;}/*** 获取顶点v指出的边的所有顶点** @param v* @return*/public Queue<Integer> adj(int v) {return this.adj[v];}/*** 该图的反向图** @return*/private Digraph reverse() {// 创建有向图对象Digraph r = new Digraph(vNum);// 遍历所有的顶点for (int v = 0; v < vNum; v++) {// 遍历当前顶点的邻接表for (Integer w : adj(v)) {// 在反向有向图中填加反向边r.addEdge(w,v);}}return r;}
}

16、拓扑排序

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

在这里插入图片描述

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

在这里插入图片描述

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

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

下列是一副拓扑排序后的示意图：

在这里插入图片描述

16.1、检测有向图中的环

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

在这里插入图片描述

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

1）检测有向环的API设计

在这里插入图片描述

2）检测有向环实现

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

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

在这里插入图片描述

package chapter16;import chapter14.Graph;
import chapter15.Digraph;/*** @author 土味儿* Date 2021/9/16* @version 1.0* 有向环检测*/
public class DirectedCycle {/*** 记录某个顶点是否被搜索过* 索引表示顶点* 值true：搜索过* 值false：未搜索过*/private boolean[] marked;/*** 记录图中是否有环*/private boolean hasCycle;/*** 索引代表顶点，使用栈的思想* 记录当前顶点有没有已经处于正在搜索的有向路径上*/private boolean[] onStack;/*** 构造器* 创建一个检测环对象，检测图g中是否有环** @param g*/public DirectedCycle(Digraph g) {// 初始化marked数组this.marked = new boolean[g.getVNum()];// 初始化hasCyclethis.hasCycle = false;// 初始化onStack数组this.onStack = new boolean[g.getVNum()];// 找到图中每一个顶点，让每一个顶点作为入口，调用dfs方法for (int v = 0; v < g.getVNum(); v++) {// 如果当前顶点没有被搜索过，就调用dfsif (!marked[v]) {dfs(g, v);}}}/*** 基于深度优先搜索，检测图g中是否有环** @param g* @param v*/private void dfs(Digraph g, int v) {// 把顶点v表示为已搜索过marked[v] = true;// 把顶点v进栈onStack[v] = true;// 进行深度搜索for (Integer w : g.adj(v)) {// 如果当前顶点w没有被搜索过，就递归调用dfsif(!marked[w]){dfs(g,w);}// 判断当前顶点w是否在栈中，如果已经在栈中，说明之前处于正在搜索状态，现在再次搜索，证明已经有环了if(onStack[w]){hasCycle = true;return;}}// 当前顶点出栈onStack[v] = false;}/*** 判断图中是否有环** @return*/public boolean hasCycle() {return hasCycle;}
}

16.2、基于深度优先的顶点排序

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

1）顶点排序API设计

在这里插入图片描述

2）顶点排序实现

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

在这里插入图片描述

package chapter16;import chapter03.Stack;
import chapter15.Digraph;/*** @author 土味儿* Date 2021/9/16* @version 1.0* 深度优先顶点排序*/
public class DepthFirstOrder {/*** 记录某个顶点是否被搜索过* 索引表示顶点* 值true：搜索过* 值false：未搜索过*/private boolean[] marked;/*** 使用栈，存储顶点序列*/private Stack<Integer> reversePost;/*** 构造器* 创建一个顶点排序对象，生成顶点线性序列** @param g*/public DepthFirstOrder(Digraph g) {// 初始化markedthis.marked = new boolean[g.getVNum()];// 初始化reversePostthis.reversePost = new Stack<Integer>();// 遍历图中每一个顶点，让每个顶点作为入口，进行深度优先搜索for (int v = 0; v < g.getVNum(); v++) {if(!marked[v]){dfs(g,v);}}}/*** 获取顶点线性序列** @return*/public Stack<Integer> getReversePost() {return reversePost;}/*** 基于深度优先，生成顶点线性序列** @param g* @param v*/private void dfs(Digraph g, int v) {// 把顶点v表示为已搜索过this.marked[v] = true;// 进行深度搜索for (Integer w : g.adj(v)) {// 如果当前顶点没有被搜索过，递归dfsif(!marked[w]){dfs(g,w);}}// 让顶点v进栈reversePost.push(v);}
}

16.3、拓扑排序实现

基于一幅图，先检测有没有环，如果没有环，则调用顶点排序即可

在这里插入图片描述

代码

package chapter16;import chapter03.Stack;
import chapter15.Digraph;/*** @author 土味儿* Date 2021/9/16* @version 1.0* 拓扑排序*/
public class TopoLogical {/*** 顶点的拓扑排序*/private Stack<Integer> order;/*** 构造器* 构建拓扑排序对象* @param g*/public TopoLogical(Digraph g) {// 创建一个有向环检测对象DirectedCycle cycle = new DirectedCycle(g);// 判断是否有环；如果没有环，创建一个顶点排序对象，进行排序if(!cycle.hasCycle()){order = new DepthFirstOrder(g).getReversePost();}}/*** 判断g图中是否有环* @return*/public boolean isCycle(){return order == null;}/*** 获取拓扑排序的所有顶点* @return*/public Stack<Integer> getOrder(){return this.order;}
}

测试

package chapter16;import chapter15.Digraph;
import org.junit.Test;/*** @author 土味儿* Date 2021/9/16* @version 1.0* 拓扑排序测试*/
public class TopoLogicalTest {@Testpublic void test(){// 准备有向图Digraph digraph = new Digraph(6);digraph.addEdge(0,2);digraph.addEdge(0,3);digraph.addEdge(1,3);digraph.addEdge(2,4);digraph.addEdge(3,4);digraph.addEdge(4,5);// 通过拓扑排序对有向图进行顶点排序TopoLogical topoLogical = new TopoLogical(digraph);// 输出顶点for (Integer w : topoLogical.getOrder()) {System.out.print(w +" ");}}
}