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);
// 边数量加1
eNum++;
}
/**
* 获取顶点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()];
// 初始化hasCycle
this.hasCycle = false;
// 初始化onStack数组
this.onStack = new boolean[g.getVNum()];
// 找到图中每一个顶点，让每一个顶点作为入口，调用dfs方法
for (int v = 0; v < g.getVNum(); v++) {
// 如果当前顶点没有被搜索过，就调用dfs
if (!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没有被搜索过，就递归调用dfs
if(!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) {
// 初始化marked
this.marked = new boolean[g.getVNum()];
// 初始化reversePost
this.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)) {
// 如果当前顶点没有被搜索过，递归dfs
if(!marked[w]){
dfs(g,w);
}
}
// 让顶点v进栈
reversePost.push(v);
}
}
16.3、拓扑排序实现
基于一幅图，先检测有没有环，如果没有环， 则调用顶点排序即可
- API
- 代码
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 {
@Test
public 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 +" ");
}
}
}
1 0 3 2 4 5