术语表
有向图
一幅有方向性的图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
出度
表示由该顶点指出的边的总数。
入度
表示指向该顶点的边的总数。
有向边
用 v -> w 表示一条由 v 指向 w 的边。
有向路径
由一系列顶点组成，对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点。路径的长度为其中所包含的边数。
有向环
为一条至少含有一条边且起点和终点相同的有向路径。简单有向环是一条（除了起点和终点必须相同之外）不含有重复的顶点和边的环。
有向图的数据类型
有向 Digraph 和 无向 Graph 基本相同，区别是 Digraph 中的 addEdge() 只调用了一次 add()；它还有一个 reverse() 方法来返回图的反向图，做法很简单，反向添加即可。
public class Digraph {
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 v = 0; v < V; v++)
adj[v] = new Bag<Integer>();
}
public Digraph(In in) {
this.V = in.readInt(); // 读取V并将图初始化
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Integer>();
}
int E = in.readInt(); // 读取E
for (int i = 0; i < E; i++) {
int v = in.readInt(); // 读取一个顶点
int w = in.readInt(); // 读取另一个顶点
addEdge(v, w); // 添加一条连接它们的边
}
}
public int V(){return V;}
public int E(){return E;}
public void addEdge(int v, int w){
adj[v].add(w);
E++;
}
public Iterable<Integer> adj(int v){
return adj[v];
}
public Digraph reverse(){ // 该图的反向图
Digraph R = new Digraph(V);
for(int v = 0; v < V; v++)
for(int w:adj(v))
R.addEdge(w, v);
return R;
}
}
有向图中的可达性
先理解一些概念：
- 单点可达性：指图中找到从 s 可达的所有顶点。例指定起点 s 为 0，看结果 0 可达的所有顶点。
- 多点可达性：指图中找到从 sources 集合中所有顶点可达的所有顶点。例指定多个起点 sources = {3,1}，看结果可达的所有顶点
有向图中的可达性介绍：
在无向图 DepthFirstSearch 类主要解决的是单点可达性问题。而本节要介绍的有向图可达性 DirectedDFS 类在 DepthFirstSearch 类基础上，以构造函数形式添加了多点可达性功能，其他与 DepthFirstSearch 类一样。
多点可达性：
以图 1 为例，若 sources 指定 "1、3" 这两个点。先看从 1 点出发，可达的所有顶点为 1，再也没有其他路了；再看从 3 点出发，可达下一个点为 5，到 5 后又没其他出路了，只能回退到 3 ，再向 4 出发，到 4 以后就结束了。结果可达所有顶点为：1、3、4、5。
代码展示
public class DirectedDFS {
private boolean[] marked;
//单点可达性
public DirectedDFS(Digraph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}
//多点可达性
public DirectedDFS(Digraph G, Iterable<Integer> sources) {
marked = new boolean[G.V()];
for(int s : sources )
if(!marked[s]) dfs(G, s);
}
private void dfs(Digraph G, int v) {
marked[v] = true;
for(int w : G.adj(v))
if(!marked[w]) dfs(G, w);
}
public boolean marked(int v) {
return marked[v];
}
public static void main(String[] args) {
Digraph G = new Digraph(new In());
Bag<Integer> sources = new Bag<Integer>();
int sourcesData[] = {1,3};
for(int i = 0; i < sourcesData.length; i++)
sources.add(sourcesData[i]);
// 测试多点可达性
DirectedDFS reachable = new DirectedDFS(G, sources);
StdOut.println("可达所有顶点为：");
for(int v = 0; v<G.V(); v++)
if(reachable.marked(v)) StdOut.print(v + " ");
}
}
运行结果：
有向环检测
有向环检测可以基于深度优先搜索来做，因为由系统维护的递归调用的栈表示的正是 "当前" 正在遍历的有向路径。一旦我们找到了一条边 v->w 且 w 已经存在于栈中，可在 onStack 中标记为 true，表示栈中，就找到了一个环，因为栈表示的是一条由 w 到 v 的有向路径，而 v->w 正好补全了这个环。
代码展示
public class DirectedCycle {
private boolean[] marked;
private int[] edgeTo;
private Stack<Integer> cycle; // 有向环中的所有顶点（如果存在）
private boolean[] onStack; // 递归调用的栈上的所有顶点
public DirectedCycle(Digraph G) {
onStack = new boolean[G.V()];
edgeTo = new int[G.V()];
marked = new boolean[G.V()];
for(int v = 0; v < G.V(); v++)
if(!marked[v]) dfs(G, v);
}
private void dfs(Digraph G, int v) {
onStack[v] = true;
marked[v] = true;
for(int w : G.adj(v))
if(this.hasCycle()) return;
else if(!marked[w])
{ edgeTo[w] = v; dfs(G, w);}
else if(onStack[w]) { // 检测到了有向环
// cycle 保存环内的所有顶点
cycle = new Stack<Integer>();
for(int x = v; x!=w; x=edgeTo[x])
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
onStack[v] = false;
}
public boolean hasCycle() {
return cycle != null;
}
public Iterable<Integer> cycle(){
return cycle;
}
public static void main(String[] args) {
Digraph G = new Digraph(new In());
DirectedCycle finder = new DirectedCycle(G);
if (finder.hasCycle()) {
StdOut.print("Directed cycle: ");
for (int v : finder.cycle()) {
StdOut.print(v + " ");
}
StdOut.println();
}else {
StdOut.println("No directed cycle");
}
}
}
运行结果：
顶点的深度优先次序
概念
通俗一点讲是指有向图中基于深度优先搜索的顶点排序，它是 DepthFirstOrder 类。它的基本思想利用深度优先搜索，然后在 dfs() 递归遍历时用队列依次序保存各个被访问的顶点。顶点在队列中的次序会因为在递归前保存与递归后保存而不同。顶点次序有以下三种：
- 前序：在递归调用之前将顶点加入队列
- 后序：在递归调用之后将顶点加入队列
- 逆后序：在递归调用之后将顶点压入栈
前序和后序顶点的保存顺序
前序 pre 可以理解为第一次访问就保存，后序 post 可以理解为哪个顶点递归先结束才保存。
代码展示
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()];
for(int v = 0; v < G.V(); v++)
if(!marked[v]) dfs(G, v);
}
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> pre(){
return pre;
}
public Iterable<Integer> post(){
return post;
}
public Iterable<Integer> reversePost(){
return reversePost;
}
public static void main(String[] args) {
In in = new In();
Digraph G = new Digraph(in);
DepthFirstOrder dfs = new DepthFirstOrder(G);
StdOut.println("--------------");
StdOut.print("Preorder: ");
for (int v : dfs.pre()) {
StdOut.print(v + " ");
}
StdOut.println();
StdOut.print("Postorder: ");
for (int v : dfs.post()) {
StdOut.print(v + " ");
}
StdOut.println();
StdOut.print("Reverse postorder: ");
for (int v : dfs.reversePost()) {
StdOut.print(v + " ");
}
StdOut.println();
}
}
运行结果：
拓扑排序
例如，假定一个计算机专业的学生必须完成图 2 所列出的全部课程。可以发现，有些课程有先修课程，如学习《算法》就先得学完《java语言》和《数据结构》。所以学生并不可以随心修这些课程，他必须思考在课程有先后次序的条件下，该如何安排并完成所有课程？
先将上面的图 2 简化成我们更熟悉的图，如下图所示
学生遇到的问题等价于，给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，而这个排序的过程，叫做拓扑排序。
按照拓扑排序的思路，课程应该排成如下顺序，且按照如下顺序学习所有课程。拓扑排序中所有边方向一致，如下边都是从左指向右：
要如何做到拓扑排序：
- 必须是无环有向图，因为有环的话，先后次序这个条件就会乱了。这里可用有向环检测 DirectedCycle 类来检测图是否有环。
- 满足无环条件下，拓扑排序其实就是逆后序的结果。这里可由 DepthFirstOrder 类提供逆后序。
代码展示
public class Topological {
private Iterable<Integer> order; // 顶点的拓扑排序
public Topological(Digraph G) {
DirectedCycle cyclefinder = new DirectedCycle(G);
if(!cyclefinder.hasCycle()) { // 判断图是否有无环
DepthFirstOrder dfs = new DepthFirstOrder(G);
order = dfs.reversePost(); // 逆后序
}
}
public Iterable<Integer> order(){
return order;
}
public boolean isDAG() {
return order != null;
}
public static void main(String[] args) {
Digraph G = new Digraph(new In()); // 以图 3 为例
Topological top = new Topological(G);
StdOut.println("拓扑排序：");
for(int v : top.order())
StdOut.print(v+" ");
}
}
运行结果：
有向图中的强连通性
定义
强连通：有向图中，如果两个顶点 v 和 w 是互相可达的，则称它们为强连通的。
强连通图：如果一幅有向图中的任意两个顶点都是强连通的，则称这幅有向图也是强连通的。
强连通分量：强连通性将所有顶点分为了一些平等的部分，每个部分都是由相互均为强连通的顶点的最大子集组成的。我们将这些子集称为强连通分量。下图中有三个强连通分量，分别是a、b、e以及f、g和c、d、h。
强连通分量传递性：如果 v 和 w 是强连通的且 w 和 x 也是强连通的，那么 v 和 x 也是强连通的。
Kosaraju算法的基本原理
对于一个无向图的连通分量，从连通分量的任意一个顶点开始，进行一次DFS，一定能遍历这个连通分量的所有顶点。所以，整个图的连通分量数应该等价于遍历整个图进行了几次（最外层的）DFS。一次DFS中遍历的所有顶点属于同一个连通分量。
下面我们将介绍有向图的强连通分量的求解方法，Kosaraju算法。
显然上图中有两个强连通分量，即强连通分量A和强连通分量B，分别由顶点A0-A1-A2和顶点B3-B4-B5构成。每个连通分量中有若干个可以相互访问的顶点（这里都是3个），强连通分量与强连通分量之间不会形成环，否则应该将这些连通分量看成一个整体，即看成同一个强连通分量。
我们现在试想能否按照无向图中求连通分量的思路求解有向图的强连通分量。我们假设，DFS从强连通分量B的任意一个顶点开始，那么恰好遍历整个图需要2次DFS，和连通分量的数量相等，而且每次DFS遍历的顶点恰好属于同一个连通分量。但是，我们若从连通分量A中任意一个顶点开始DFS，就不能得到正确的结果，因为此时我们只需要一次DFS就访问了所有的顶点。所以，我们不应该按照顶点编号的自然顺序（0,1,2，……）或者任意其它顺序进行DFS，而是应该按照被指向的强连通分量的顶点排在前面的顺序进行DFS。上图中由强连通分量A指向了强连通分量B。所以，我们按照
B3, B4, B5, A0, A1, A2
的顺序进行DFS，这样就可以达到我们的目的。但事实上这样的顺序太过严格，我们只需要保证被指向的强连通分量的至少一个顶点排在指向这个连通分量的所有顶点前面即可，比如
B3, A0, A1, A2, B4, B5
B3排在了强连通分量A所有顶点的前面。
现在我们的关键问题就是如何得到这样一个满足要求的顶点顺序，Kosaraju给出了这解决办法：对原图取反，然后从反向图的任意节点开始进行DFS的逆后序遍历，逆后序得到的顺序一定满足我们的要求。
DFS的逆后序遍历是指：如果当前顶点未访问，先遍历完与当前顶点相连的且未被访问的所有其它顶点，然后将当前顶点加入栈中，最后栈中从栈顶到栈底的顺序就是我们需要的顶点顺序。
上图表示原图的反向。
我们现在进行第一种假设：假设DFS从位于强连通分量A中的任意一个节点开始。那么第一次DFS完成后，栈中全部都是强连通分量A的顶点，第二次DFS完成后，栈顶一定是强连通分量B的顶点。保证了从栈顶到栈底的排序强连通分量B的顶点全部都在强连通分量A顶点之前。
我们现在进行第二种假设：假设DFS从位于强连通分量B中的任意一个顶点开始。显然我们只需要进行一次DFS就可以遍历整个图，由于是逆后续遍历，那么起始顶点一定最后完成，所以栈顶的顶点一定是强连通分量B中的顶点，这显然是我们希望得到的顶点排序的结果。
上面使用了最简单的例子说明Kosaraju算法的原理，对于有多个强连通分量，连接复杂的情况，仍然适用。大家可以自行举例验证。
综上可得，不论从哪个顶点开始，图中有多少个强连通分量，逆后续遍历的栈中顶点的顺序一定会保证：被指向的强连通分量的至少一个顶点排在指向这个连通分量的所有顶点前面。所以，我们求解强连通分量的步骤可以分为两步：
（1）对原图取反，从任意一个顶点开始对反向图进行逆后续DFS遍历，可使用 DepthFirstOrder。
（2）按照逆后续遍历中栈中的顶点出栈顺序，对原图进行DFS遍历，一次DFS遍历中访问的所有顶点都属于同一强连通分量。
强连通分量的代码实现
测试图形如下：
代码展示
public class KosarajuSCC {
private boolean[] marked; // 已访问过的顶点
private int[] id; // 强连通分量的标识符
private int count; // 强连通分量的数量
public KosarajuSCC(Digraph G){
marked = new boolean[G.V()];
id = new int[G.V()];
DepthFirstOrder order = new DepthFirstOrder(G.reverse());
for(int s : order.reversePost())
if(!marked[s])
{ dfs(G, s); count++; }
}
private void dfs(Digraph G, int v){
marked[v] = true;
id[v] = count; // 给同一个内的强连通分量顶点做相同 count 标记
for(int w : G.adj(v))
if(!marked[w])
dfs(G, w);
}
public boolean stronglyConnected(int v, int w)
{ return id[v] == id[w]; }
public int id(int v)
{ return id[v]; }
public int count()
{ return count; }
public static void main(String[] args) {
Digraph G = new Digraph(new In());
KosarajuSCC scc = new KosarajuSCC(G);
int m = scc.count();
// 强连通分量总数
StdOut.println(m + " strong components");
Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
for (int i = 0; i < m; i++) {
components[i] = new Queue<Integer>();
}
for (int v = 0; v < G.V(); v++) {
components[scc.id(v)].enqueue(v);
}
// 输出所有强连通分量
for (int i = 0; i < m; i++) {
for (int v : components[i]) {
StdOut.print(v + " ");
}
StdOut.println();
}
}
}
运行结果
