12. 图的进阶
12.1 有向图
在实际生活中,很多应用相关的图都是有方向性的,最直观的就是网络,可以从A页面通过链接跳转到B页面,那么a和b连接的方向是a->b,但不能说是b->a,此时我们就需要使用有向图来解决这一类问题,它和我们之前学习的无向图,最大的区别就在于连接是具有方向的,在代码的处理上也会有很大的不同。
12.1.1 有向图的定义及相关术语
定义:
有向图是一副具有方向性的图,是由一组顶点和一组有方向的边组成的,每条方向的边都连着一对有序的顶点。
出度:
由某个顶点指出的边的个数称为该顶点的出度。
入度:
指向某个顶点的边的个数称为该顶点的入度。
有向路径:
由一系列顶点组成,对于其中的每个顶点都存在一条有向边,从它指向序列中的下一个顶点。
有向环:
一条至少含有一条边,且起点和终点相同的有向路径。
一副有向图中两个顶点v和w可能存在以下四种关系:
-
没有边相连;
-
存在从v到w的边v—>w;
-
存在从w到v的边w—>v;
-
既存在w到v的边,也存在v到w的边,即双向连接;
理解有向图是一件比较简单的,但如果要通过眼睛看出复杂有向图中的路径就不是那么容易了。
12.1.2 有向图API设计
类名 | Digraph |
---|---|
构造方法 | Digraph(int V):创建一个包含V个顶点但不包含边的有向图 |
成员方法 | 1.public int V():获取图中顶点的数量 2.public int E():获取图中边的数量 3.public void addEdge(int v,int w):向有向图中添加一条边 v->w 4.public Queue adj(int v):获取由v指出的边所连接的所有顶点 5.private Digraph reverse():该图的反向图 |
成员变量 | 1.private final int V: 记录顶点数量 2.private int E: 记录边数量 3.private Queue[] adj: 邻接表 |
在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->w
public void addEdge(int v, int w) {
//由于有向图中边是有向的,v->w 边,只需要让w出现在v的邻接表中,而不需要让v出现在w的邻接表中
//无向图的话两个都要加
adj[v].add(w);
//边的数目自增1
E++;
}
//获取由v指出的边所连接的所有顶点
public Queue<Integer> adj(int v) {
return adj[v];
}
//该图的反向图
private Digraph reverse() {
//创建新的有向图对象
Digraph r = new Digraph(V);
//遍历0~V-1所有顶点,拿到每一个顶点v
for (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设计
类名 | 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:索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的有向路径上 |
12.2.1.2 检测有向环实现
在API中添加了onStack[] 布尔数组,索引为图的顶点,当我们深度搜索时:
- 如果当前顶点正在搜索,则把对应的onStack数组中的值改为true,标识进栈;
- 如果当前顶点搜索完毕,则把对应的onStack数组中的值改为false,标识出栈;
- 如果即将要搜索某个顶点,但该顶点已经在栈中,则图中有环;
代码:
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->w
public void addEdge(int v, int w) {
//由于有向图中边是有向的,v->w 边,只需要让w出现在v的邻接表中,而不需要让v出现在w的邻接表中
//无向图的话两个都要加
adj[v].add(w);
//边的数目自增1
E++;
}
//获取由v指出的边所连接的所有顶点
public Queue<Integer> adj(int v) {
return adj[v];
}
//该图的反向图
private Digraph reverse() {
//创建新的有向图对象
Digraph r = new Digraph(V);
//遍历0~V-1所有顶点,拿到每一个顶点v
for (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设计
类名 | DepthFirstOrder |
---|---|
构造方法 | DepthFirstOrder(Digraph G):创建一个顶点排序对象,生成顶点线性序列; |
成员方法 | 1.private void dfs(Digraph G,int v):基于深度优先搜索,生成顶点线性序列 2.public Stack reversePost():获取顶点线性序列 |
成员变量 | 1.private boolean[] marked: 索引代表顶点,值表示当前顶点是否已经被搜索 2.private Stack reversePost: 使用栈,存储顶点序列 |
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顶点的邻接表,得到每一个顶点w
Queue<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设计:
类名 | TopoLogical |
---|---|
构造方法 | TopoLogical(Digraph G):构造拓扑排序对象 |
成员方法 | 1.public boolean isCycle():判断图G是否有环 2.public Stack order():获取拓扑排序的所有顶点 |
成员变量 | 1.private Stack order: 顶点的拓扑排序 |
代码:
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顶点的邻接表,得到每一个顶点w
Queue<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 加权无向图
持续学习中