有向图指的是边是单向的, 每条边连接的两个顶点是一个有序对, 只能从一个点到另外一个点.
有向图数据结构
有向图有一些概念, 首先v 和 w两个顶点之间的关系有如下四种:
- v->w, 存在v到w的边
- w->v, 存在w到v的边
- v->w, w->v, 既存在v-w, 也存在v-w的边
- 没有边相连
如果存在 v->w, 就说w能够由v达到, 一个点可以由自己达到.
虽然有向图看起来不如有向图那么容易发现路径, 但其实有向图的数据结构比无向图还要简单. 其核心的理念就是, 无向图的对称状态, 在有向图中是不存在的.
public class Digraph {
//顶点数量
private final int V;
//边数
private int E;
//用于保存邻接表的背包
private Bag<Integer>[] adj;
//构造器, 一开始默认边数是0
public Digraph(int V) {
if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
this.V = V;
this.E = 0;
//对每一个顶点生成Bag, 然后放入邻接表数组中
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
}
public int V() {
return V;
}
public int E() {
return E;
}
//添加一条从v到w边, 注意这是有向图, 因此w在v的链表里, 但是v不在w的链表里
public void addEdge(int v, int w) {
adj[v].add(w);
E++;
}
//获取当前图的一个反向图
//由于每一个v->w是有序的, 因此遍历所有的顶点, 然后对于每个顶点的邻接表, 将其中的邻接顶点反向添加到一个新的表里, 就获取了一个反向图
public Digraph reverse() {
Digraph reverse = new Digraph(V);
for (int v = 0; v < V; v++) {
for (int w : adj(v)) {
reverse.addEdge(w, v);
}
}
return reverse;
}
}
有向图的添加边的时候是单向的, 需要特别注意. 除此之外, 根据有向图的特点, 还可以得到一张关系完全相反的图, 只需要遍历所有连接关系然后反向将其添加到一个新图中即可.
深度优先算法 – 可达性和路径搜索
有向图的可达性其实和无向图很类似, 深度优先搜索在可达性方面与有向图是一样的, 也是根据邻接表不断的搜索, 类似之前, 可以创建一个根据一个顶点和一个图来生成所有可达顶点的一个搜索对象:
public class DirectedDFS {
//标记数组
private boolean[] marked;
//可达点的数量
private int count;
//用一张图和一个顶点初始化搜索对象
public DirectedDFS(Digraph G, int s) {
marked = new boolean[G.V()];
//深度优先搜索
dfs(G, s);
}
//这个深度优先搜索的原理和之前的完全一样, 能同时工作在有向和无向图上, 然后会在标记数组上标出所有算法遍历过的点, 也就是s的可达点
private void dfs(Digraph G, int v) {
count++;
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) dfs(G, w);
}
}
//剩下都是一些辅助函数
}
可以看到, 深度优先搜索完全适用于有向图, 很显然, 广度优先搜索也是适合的, 因为二者本质上只是处理顶点的顺序不同, 但都能工作在图的数据结构上.
基于深度优先搜索的可达性和基于广度优先搜索的最短路径, 也同样可以工作在有向图上.
有向图的一个典型应用就是Java的垃圾回收算法, 会在每个对象里保留一个位, 用于标记, 如果没有标记, 就会回收这些对象. 在CSAPP里也提到过了.
环和有向无环图
在一些需要给顶点排序, 以获得任务的先后联系的工作中, 不能有环的存在, 因此如何检测一个有向图中有环, 是一个重要的算法.
检测环的本质是, 在进行深度优先搜索的时候, 当前递归都是存在栈中的, 存在栈中的所有内容, 就是当前遍历的所有顶点. 假如当前正在寻找一个从 w->v 的路径, 如果发现了一条 v->w 的路径, 就说明有了一个环.
看一下具体的实现, 昨晚上一边洗澡一边恍然大悟, 原来这就是跟踪栈的方法, 在递归的每一层做一个标记, 递归结束的时候再取消, 在每一层里打印共同的全局变量, 就可以知道递归的情况了, 栈也通常可以用来记录匹配的情况:
public class DirectedCycle {
//是否已经被标记, 和之前的算法用处一样
private boolean[] marked;
//记录路径
private int[] edgeTo;
//这个数组用于跟踪栈中的所有顶点
private boolean[] onStack;
//记录有向环中的所有顶点. 如果为空说明不存在
private Stack<Integer> cycle;
//使用图来初始化一个搜索对象
public DirectedCycle(Digraph G) {
//根据图的顶点数创建标记数组, 栈跟踪数组和路径数组
marked = new boolean[G.V()];
onStack = new boolean[G.V()];
edgeTo = new int[G.V()];
//对于每个顶点都进行dfs搜索, 如果找到一个环, 就会停止
for (int v = 0; v < G.V(); v++)
if (!marked[v] && cycle == null) dfs(G, v);
}
//这次是利用dfs搜索还
private void dfs(Digraph G, int v) {
//先把栈跟踪和标记的顶点都标上true
//这一行最下边还有一个onStack[v] = false; 实际上就是将当前跟踪的顶点从去标记里去掉
onStack[v] = true;
marked[v] = true;
//针对某个顶点的全部邻接顶点
for (int w : G.adj(v)) {
//每次进入递归之前检测一下是不是已经发现了环, 是的话就返回了.
if (cycle != null) return;
//如果顶点没标记过, 也不可能有环, 因为还没有遍历过, 在路径数组中标记对应关系, 然后进入递归
else if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
//如果顶点被标记过了, 而且栈跟踪数组也有这个顶点, 说明当前的顶点在之前出现过.
//由于是有向图, 则说明肯定回到了这个顶点, 就出现环了
else if (onStack[w]) {
//创建新的栈
cycle = new Stack<Integer>();
//在边数组中, 将寻找到的v->w的所有路径压入栈中
for (int x = v; x != w; x = edgeTo[x]) {
cycle.push(x);
}
//最后压入w
cycle.push(w);
//再压入v, 成了一个环
cycle.push(v);
assert check();
}
}
onStack[v] = false;
}
public boolean hasCycle() {
return cycle != null;
}
}
这个寻找环的算法的核心是跟踪栈, 也就是标红的部分, 在每次进入递归之前, 将已经经过的点放到栈里, 如果这个递归到某一处又回到了这个点, 因为是有向图, 就说明一定有环了.
这也是跟踪栈的技术, 确实有意思.
深度优先搜索 – 顶点排序
这个玩意实际上就是排出一个类似的顺序, 先干什么后干什么. 在dfs中, 由于每次判断没有被访问过, 才会做上标记, 如果将dfs访问的顺序记录下来(同样也是使用一个全局变量), 根据记录的时点不同, 就可以得到不同的排序方式.
如果在每次一进入递归就立刻判断, 然后就记录, 就是前序, 也就是dfs访问节点的顺序. 如果在递归返回之后记录, 就是后序. 还一种有意思的就是在递归调用之后将顶点压入栈, 再从栈中弹出来, 就是逆后序.
看看这三种排序的实现:
public class DepthFirstOrder {
//标记数组
private boolean[] marked;
//前序排序的顶点
private Queue<Integer>pre;
//逆序排序的顶点, 这两个都使用队列, 一直往里放就行
private Queue<Integer> post;
//逆后序排序的顶点, 使用了栈
private Stack<Integer> reversePost
//构造器
public DepthFirstOrder(Digraph G) {
//根据图的顶点数初始化几个数据结构
pre = new Queue<Integer>();
post = new Queue<Integer>();
reversePost = new Stack<Integer>();
marked = new boolean[G.V()];
//针对所有顶点进行dfs操作
for (int v = 0; v < G.V(); v++)
if (!marked[v]) dfs(G, v);
}
//来看看这次的dfs有何不同
private void dfs(Digraph G, int v){
//直接进队列, 表示一访问就进队列, 这个就是递归遍历的顺序
pre.enqueue(v);
//中间这段代码不变, 对没有遍历过的邻接点继续递归
marked[v] = true;
for(int w : G.adj(v)){
if(!marked[w]){
dfs(G,w);
}
}
//后序, 在递归返回的时候才放入顶点, 这实际上就是递归一层一层收缩的顺序
post.enqueue(v);
//后序压栈, 得到逆后序
reversePost.push(v);
}
public Iterable<Integer> reversePost(){
return reversePost;
}
}
之后只要再用一些方法把栈里的一个一个顶点从栈里弹出来, 就得到了逆后序.
所谓拓扑排序, 就是逆后序这种方法, 会返回一个任务的先后顺序, 在一些任务有关联的时候, 返回的这个先后顺序, 只要根据这个顺序安排工作, 就可以让各个工作都得以完成.
我觉得图里的处理这里, 提供了跟踪栈, 与将调用的情况进行排序的思想, 确实赞啊.
有向图的强连通性 – 连通分量
所谓有向图的强连通性, 就是指存在 v->w ,也存在 w->v ,就说w和v有强连通性, 可以看到, 一个强联通就是一个环.
有向图的连通分量, 就是所有强连通的顶点的最大子集.
注意强连通分量说的是顶点属于分量, 不是边. 强连通分量的意义在于可以将一张有向图分为几个内部有关联, 而外部关系稀疏的部分进行处理, 在现实中抽象并处理互相连通的网络设备的情况非常常见.
这里有一个神奇的Kosaraju算法, 用两个步骤来计算:
- 使用上一节的方法来计算一个图的反向图的逆后序排列
- 在G中进行标准的深度优先搜索, 但是顺序必须要按照上一步骤得到的顺序, 而不能交给递归去控制.
- 在同一个递归中被访问的顶点, 就处于同一个强连通分量中
看wiki上其实是利用了一个图和其反向图有相同的连通分量的原理, 我个人感觉好像是先用深度优先找到头, 然后反着来, 可以最快的缩小寻找范围.
public class KosarajuSharirSCC {
private boolean[] marked;
//强连通分量的标识数组
private int[] id;
//连通分量的数量
private int count;
//构造器
public KosarajuSharirSCC(Digraph G) {
//创建一个查找反向图的深度优先查找对象
DepthFirstOrder dfs = new DepthFirstOrder(G.reverse());
//执行之后通过dfs.reversePost()获取逆后序顺序, 从栈里弹出来的顺序就是逆后序
marked = new boolean[G.V()];
id = new int[G.V()];
// 这里遍历顶点的顺序不再是原来的直接拿数组索引从0开始遍历, 而是按照逆序遍历
for (int v : dfs.reversePost()) {
if (!marked[v]) {
dfs(G, v);
//每次如果有一个顶点没标记, 进入递归, 一定可以把连通的顶点全部标记, 在递归结束之后再进行count, 因此标记完一组某个顶点的连通分量, count只会加1
count++;
}
}
}
//这个深度优先就多了一个将id数组对应的v索引标记为当前连通分量号的操作
private void dfs(Digraph G, int v){
marked[v] = true;
//将当前分量都标记成当前的count
id[v]=count;
for(int w: G.adj(v){
if(!marked[w]){
dfs(G, w);
}
}
}
}
后记
明明还有一章怎么就后记了, 因为数学水平实在不高, 最后一章再看下去有点吃力. 而前边算法的部分知识太密集, 还得好好消化一下.
因为毕竟是自学, 没有工程实践, 代码练的太少, 很多题目还是写不出来, 因此准备再找点简单一点的算法书, 多做做相关练习, 应该能提高点水平.
