4.2.1介绍
在有向图中,边是单向的.实际上组合性的结构对算法有深远影响,使得有向图和无向图之间的处理大有不同.
顶点出度: 由该顶点指出边的总数.
顶点入度:指向该顶点的边的总数.
一条有向边的第一个顶点叫头,第二个顶点称为尾.(v → w)
一幅有向图的顶点可能存在4种关系:
1.没有边相连接
2.存在v → w
3.存在w → v
4.存在 双向 v ↔ w
4.2.2有向图的数据类型Digraph
package algorithm.algorithmbook.graph;
/**
* description: 有向图的数据接口
*
* @author leon
* @date 18-2-23.
*/
public interface IDigraph {
/**
* @return 顶点数
*/
int V();
/**
* @return 边数
*/
int E();
/**
* 添加 v-> w 的边
*
* @param v 起点
* @param w 终点
*/
void addEage(int v, int w);
/**
* 由v指出所连接的所有顶点
*
* @param v 顶点
* @return 可迭代的顶点列表
*/
Iterable<Integer> adj(int v);
/**
* 这个方法有时很有用,返回的是图的一个副本,但将其中所有的边的方向反向.
* 因为可以找出"指向"每个顶点的边,而adj()为指出每个顶点的边.
* @return 该图的反向图
*/
IDigraph reverse();
/**
*
* @return 字符串描述
*/
String toString();
}
package algorithm.algorithmbook.graph;
import java.io.DataInputStream;
import algorithm.algorithmbook.graph.IDigraph;
/**
* description:有向图
*
* @author leon
* @date 18-2-23.
*/
public class Digraph implements IDigraph {
//顶点数
private final int v;
//边数
private int e;
//邻接表
private Bag<Integer>[] adj;
public Digraph(int v) {
this.v = v;
this.e = 0;
adj = (Bag<Integer>[]) new Bag[v];
for (int i = 0; i < v; i++) {
adj[i] = new Bag<Integer>();
}
}
public Digraph(DataInputStream input) {
v = 0;
}
@Override
public int V() {
return v;
}
@Override
public int E() {
return e;
}
@Override
public void addEage(int v, int w) {
//因为这里是有向图,所以只需要连接 v->w 的边
adj[v].add(w);
e++;
}
@Override
public Iterable<Integer> adj(int v) {
return adj[v];
}
@Override
public IDigraph reverse() {
Digraph revDigraph = new Digraph(v);
for (int i = 0; i < v; i++) {
for (int to : revDigraph.adj(i)) {
addEage(to, v);
}
}
return revDigraph;
}
}
4.2.3 有向图的可到达性.
单点可到达性:给定起点s ,是否有到指定顶点v的有向路径.算法和DeepFirstSearch类似.
多点可到达性:给定一个有向图和顶点集合,回答”是否存在一条从集合中任意的顶点到达给定顶点v的有向路径?”等类似问题.
4.2.3-1 标记-清除 的垃圾回收器
多点可到达性的重要实际应用在与 内存管理系统中.对于java 内存,在一个有向图中,对象表示一个顶点,引用表示一条边.这个模型很好的解决了java内存中.定期的进行对有向图的多点可到达性检测,发现有不可到达的顶点进行回收的处理.
4.2.3-2 有向图的寻路
DepthFirstPaths和breadthFirstPaths同样适合有向图.
单点有向图 给定一个有向图和起始顶点:回答”从s到给定目的的顶点v是否存在一条有向路径,如果有找出来”
单点最短有向路径.”从s到给定目的地v是否存在一条路径,如果存在找出其中最短的一条(所含的边最少)”
4.2.4 环和有向无环图
从原则上说,一副有向图可能包含多个有向环,但是实际上我们一般重点关注一小部分,或只想知道他们是否存在.
4.2.4.1 调度问题
优先级限制条件是调度问题的核心,他指明了哪些任务必须在哪些任务之前完成. 这时候采用有向图的方法来求解调度的顺序就是很不错的.例如下图
优先级限制下的调度问题: 解决这个问题可以用有向图来模型来表示.等价于 拓扑排序
拓扑排序: 给定一个有向图,将所有的顶点排序,使得所有的边都是从排在前面的边指向排在后面的边.例如下面下边示意图:
拓扑排序的典型应用:
| 应用 | 顶点 | 边 |
|---|---|---|
| 任务调度 | 任务 | 优先级限制 |
| 课程安排 | 课程 | 先导课程限制 |
| 继承 | java类 | Extends 关系 |
| 符号链接 | 文件名 | 链接 |
4.2.4.2 有向图中的环
在某些特定的有向图依赖关系中是不允许出现环结构的.例如java 类依赖关系.
有向环检测: 如果有环,在所有顶点中按照顺序寻找,返回自己的顶点.即找到了一个有向环.
一幅有向图的环的个数有可能是图大小的指数级别,所以一般情况下只需要找到一个有向环即可判断,而不需要找出所有的环.因此有向无环图就表现的尤为突出.
定义：
有向无环图[DAG （Directed acyclic graph）]就是一副不含环的有向图.
检测是否是有向无环图.采用深度优先搜索.维护一个递归调用栈来记录当前在遍历的有向路径,一旦我们找到了一条边v→ w ,并且w已经存在当前递归栈中,则表示找到了一个有向环,同时如果找不到这样一条边,则说明图是有向无环图.
package algorithm.algorithmbook.graph;
import java.util.Stack;
/**
* description:寻找有向环
*
* @author leon
* @date 18-2-26.
*/
public class DirectCycle {
private int[] edgeTo;
private boolean[] marked;
//用于存放环的所有顶点,如果存在环
private Stack<Integer> cycles;
//递归调用的栈上的所有顶点
private boolean[] onStack;
public DirectCycle(Digraph digraph) {
onStack = new boolean[digraph.V()];
marked = new boolean[digraph.V()];
edgeTo = new int[digraph.V()];
for (int v = 0; v < digraph.V(); v++) {
if (!marked[v]) {
dfs(digraph, v);
}
}
}
private void dfs(Digraph digraph, int v) {
onStack[v] = true;
marked[v] = true;
for (int w : digraph.adj(v)) {
//特别的处理环的,如果已经找到了环则跳出循环
if (this.hashCycle()) {
return;
}
//进行深度优先遍历
if (!marked[w]) {
edgeTo[w] = v;
dfs(digraph, w);
}
//如果已经marked了,说明已经查找过顶点,也就是出现了环
else if (onStack[w]) {
cycles = new Stack<>();
for (int x = v; x != w; x = edgeTo[x]) {
cycles.push(x);
}
cycles.push(w);
cycles.push(v);
}
onStack[v] = false;
}
}
public boolean hashCycle() {
return !cycles.empty();
}
public Iterable<Integer> cycle() {
return cycles;
}
}
4.2.3.4 顶点的深度优先次序和拓扑排序
命题E:
只有有向无环图才能进行拓扑排序.
实际上我们已经见过一种拓扑排序的算法,只需要添加一行代码就可以由标准的深度优先搜索完成这项任务!引入一种搜索排序,”有向图中基于深度优先的顶点搜索排序”.他的思想是深度优先搜索只会访问所有的顶点一次.遍历这个数据结构实际上能访问图中的所有顶点,而遍历的顺序取决与这个数据结构是递归前还是之后进行保存.一般情况人们关注3中情况:
1.前序遍历 (pre) :在递归前将顶点加入队列
2.后续遍历(post):在递归后将顶点加入队列
3.逆后续(reversePost): 把后续遍历的顺序反转采用栈保存,刚好可以反过来).在递归后将顶点加入栈.
待排序的有向图
执行深度优先搜索的 3中排序过程:
package algorithm.algorithmbook.graph;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
/**
* description:有向图深度优先排序的几种方式
* <p>
* 这里根据在递归前,后 进行顶点保存的顺序分成前序,后序,逆后序
* 1.前序遍历 (pre) :在递归前将顶点加入队列
* 2.后续遍历(post):在递归后将顶点加入队列
* 3.逆后续(reversePost): 把后续遍历的顺序反转采用栈保存,刚好可以反过来).在递归后将顶点加入栈.
*
* @author leon
* @date 18-2-27.
*/
public class DirectDeepFirstOrder {
private boolean[] marked;
private Queue<Integer> preQ;
private Queue<Integer> postQ;
private Stack<Integer> reversePost;
public DirectDeepFirstOrder(Digraph g) {
marked = new boolean[g.V()];
preQ = new ArrayDeque<>();
postQ = new ArrayDeque<>();
reversePost = new Stack<>();
for (int v = 0; v < g.V(); v++) {
if (!marked[v]) {
dfs(g, v);
}
}
}
/**
* 深度优先遍历递归
*
* @param g 图
* @param v 需要递归的顶点
*/
private void dfs(Digraph g, int v) {
preQ.offer(v);
marked[v] = true;
for (int w : g.adj(v)) {
if (!marked[w]) {
dfs(g, w);
}
}
postQ.offer(v);
reversePost.push(v);
}
/**
* 前序
*
* @return 排序列表
*/
public Iterable<Integer> pre() {
return preQ;
}
/**
* 后序
*
* @return 排序列表
*/
public Iterable<Integer> post() {
return postQ;
}
/**
* 逆后序
*
* @return 排序列表
*/
public Iterable<Integer> reversePost() {
return reversePost;
}
}
命题:
一副有向无环图的的拓扑排序即所有顶点的逆后序排序
证明:
对于任意边v→ w,在调用dfs(v)时以下三种情况之一会满足:
1.dfs(w)已经调用过并且已经返回了(w已经被标记了)
2.dfs(w)还没有调用,此时会继续接下来调用dfs(w),并且在 dfs(v)之前调用,并且标记.
3.dfs(w)已经调用并且没有返回.证明的关键在于,需要证明这种情况在有向无环图中是不可能出现的,则可以确定v→ w 的dfs(x) 是有顺序的.因为 如果 dfs(w)已经调用,但是没有返回,则说明有边w→ v存在,然而本身有v→ w ,这样就形成了一个环.与有向无环图有矛盾,故情况3是不存在的.
综上所述:任意一条边的dfs(w) 都会在dfs(v)之前标记,也就是说 在排名靠后w的dfs(w) 比排名靠前v的dfs(v)先标记,把标记列表倒序就得到排名靠前的v→ w的顶点.
package algorithm.algorithmbook.graph;
/**
* description:拓扑排序
*
* @author leon
* @date 18-2-26.
*/
public class Topological {
private Iterable<Integer> orderList;
public Topological(Digraph digraph) {
DirectCycle directCycle = new DirectCycle(digraph);
if (!directCycle.hashCycle()) {
DirectDeepFirstOrder directDeepFirstOrder = new DirectDeepFirstOrder(digraph);
orderList = directDeepFirstOrder.reversePost();
}
}
/**
* 是否是有向无环图
*
* @return
*/
public boolean isDAG() {
return orderList != null;
}
/**
* 拓扑排序
*
* @return
*/
Iterable<Integer> order() {
return orderList;
}
/**
* test
*
* @param args
*/
public static void main(String[] args) {
String fileName = args[0];
String sepatetor = args[1];
SymbolDirectGraph symbolGraph = new SymbolDirectGraph(fileName, sepatetor);
Topological topological = new Topological(symbolGraph.graph());
if (!topological.isDAG()) {
return;
}
for (int v : topological.orderList) {
//通过索引表来获取图中对应的 名字
System.out.println(symbolGraph.name(v));
}
}
}
命题G:
使用深度优先搜索对无向图进行拓扑排序的所需时间与V+E成正比.
证明:
由代码可知,拓扑排序需要进行两次,1.进行是否有环判断,2 进行逆后序排序. 每次操作都访问了顶点和边,即是V+E 的倍数关系.
4.2.5 有向图中的强连通性
定义:
如果有向图中 w和v 双向可到达即存在v到w的有向路径,也存在w到v的有向路径,称为强连通.如果一副有向图总任意两点之间都是强连通,则称这幅有向图也是强连通的.
两个顶点是强连通.当且仅当他们都是同在一个有向环中.
强连通分量特点:
- 自反性:任意顶点v 和自己都是强连通的.
- 对称性: v和w 是强连通,那么w和v也是强连通
- 传递性: v和w 是强连通,w和x 是强连通.那么v 和x 是强连通.
强连通性将所有顶点分成一些平等的部分,每个部分是由所组成强连通的顶点最大子集组成.把这些最大子集称为强连通分量.包含V个顶点的有向图包含 1-V个强连通分量;一个强连通图只有一个强连通分量(也就是整个图);而一个无环图则包含V个强连通分量(每个顶点都是自己的强连通分量,所以强连通分量就是每个顶点).因为强连通是针对顶点而不是边,所以会出现有些边连接的两个顶点出现在同一个强连通分量中,而有些边连接的两个顶点则出现在不同的强连通分量中.
4.2.5.2 应用举例
在理解有向图的结构时,强连通性是一个重要的特点.他突出了相互关联的几组顶点(强连通分量).例如强连通分量能够帮组教科书的作者决定那些话题应该归为一类,帮助程序员组织程序的模块;表示哪些食物链中的物种应该在一个生态圈中.
强连通分量API
| SCC(digraph G) | 构造函数 |
| Boolean stronglyConnetied(int v,int w) | V ,w 是否是强连通 |
| Int count() | 强连通分量数 |
| Int id(int v) | V属于哪个强连通分量(0 ~ count-1) |
kosaraju算法:
1.在给定有向图G,使用DeepFirstOrder计算他的反向图GR的逆后序排序.
2.在G图中进行标准的深度优先搜索,但是需要按照刚才计算出的顺序访问所有未标记过的顶点(而非标准的顺序访问).
3.在构造函数中,所有同一个递归dfs()调用中访问到的顶点都在同一个强连通分量中,将他们按照CC的方式识别出来.
强连通性: 回答”给定的两点是强连通的吗? 这幅图中含有多少个强连通分量 ?”
因为 Kosaraju 方法借助了有向图求反向图,然后再计算 逆序排序.
能不能用和 无向图相同的效率解决有向图图的强连通问题.Tarjan提出了一个解决方案.而且这个简单的解决方案令人惊讶.
