定义。 一幅有方向的图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一组点对
有向图的API
public class Digraph
Digraph(int v) //创建一幅含有V个顶点但没有边的有向图
Digraph(In in) //从输入流in中读取一幅有向图
int V() //顶点总数
int E() //边的总数
void addEdge(int v, int w) //向有向图中添加一条边v->w
Iterable<Integer> adj(int v) //由v指出的边所连接的所有顶点
Digraph reverse() //该图的反向图
String toString() //对象的字符串表示
有向图与无向图类似，也使用邻接表来表示有向图，不同于无向图中如果v在w的链表中，那么w也在v的链表中，有向图中不存在这种对称性。
Digraph的数据结构：
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 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到达给定顶点v的有向路径？ - 多点可达性
是否存在一条从集合中的任意顶点到达给定顶点的有向路径？
为了解决这些问题，我们设计如下API：
public class DirectedDFS
DirectedDFS(Digraph G, int s) //在G中找到从s可到达的所有顶点
DirectedDFS(Digraph G, Iterable<Integer> sources)
//在G中找到从sources中的所有顶点可到达的所有顶点
boolean marked(int v) //判断v是否可达
DirectedDFS使用了解决图处理的标准范例和标准的深度优先搜索来解决这些问题。它对每个顶点调用递归方法dfs()，以标记遇到的任意顶点。
深度优先搜索的实现：
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 void main(String[] args){
Digraph G = new Digraph(new In(args[0]));
Bag<Integer> sources = new Bag<Integer>();
for( int i=1; i<args.length; i++)
sources.add(Integer.parseInt(args[i]));
DirectedDFS reachable = new DirectedDFS(G, sources);
for( int v = 0; v<G.V(); v++)
if( reachable.marked(v)) StdOut.print(v + " ");
StdOut.println();
}
}
标记-清除的垃圾收集
多点可达性的一个重要应用是在典型的内存管理系统中。一个顶点表示一个对象，一条边则表示一个对象对另一个对象的引用。周期性的运行多点可达算法，回收没有被达到的对象。
** 环和有向无环图 **
一种应用广泛的模型是给定一组任务并安排它们的执行顺序，限制条件是这些任务的执行方法和起始时间。当然最重要的限制条件是优先级限制。如果任务x必须在任务y之前完成，而任务y必须在任务z之前完成，但任务z又必须在任务x之前完成，那么这个问题一定是无解的。检查是否无解，需要做有向环检测。
基于深度优先搜索来解决这个问题并不难，因为系统维护的递归调用栈表示的正是“当前”正在遍历的有向路径。一旦找到一条有向边v->w且w已经存在于栈中，就找到了一个环。
有向环API：
public class DirectedCycle
DirectedCycle(Digraph G) //寻找有向环的构造函数
boolean hasCycle() //G是否含有有向环
Iterable<Integer> cycle() //有向环中所有的顶点
寻找有向环的实现：
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 = 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;
}
该类为标准的递归dfs()方法添加了一个布尔型的数组onStack[]来保存递归调用期间栈上的所有顶点。当它找到一条边v->w在栈中时，它就找到了一个有向环。环上的点可以通过edgeTo[]中的链接找到。
** 拓扑排序 **
给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素。
优先级限制下的调度问题等价于计算有向无环图中的所有顶点的拓扑排序，设计如下API：
public class Topological
Topological(Digraph G) //拓扑排序的构造函数
boolean isDAG() //判断G是否为无环图
Iterable<Integer> order() //拓扑有序的所有顶点
有向图中基于深度优先搜索的顶点排序它的基本思想是深度优先搜索正好只会访问每个顶点一次。如果将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>();
reverse = 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;
}
}
