有向图----可达性问题
- 单点可达性：回答“是否存在一条从起点s到给定节点v的有向路径？”等类似问题。
- 多点可达性：回答“是否存在一条从集合中任意顶点到给定节点v的有向路径？”等类似问题。
- 顶点对的可达性：回答“是否存在一条从一个给定节点v到给定节点w的有向路径？”等类似问题。
针对单点可达性和多点可达性，使用深度优先遍历很容易实现。先定义API：
public class DirectedDFS DirectedDFS(Digraph G, int s) //在G中找到s可达的所有顶点 DirectedDFS(Digraph G, Iterable<Integer> sources) //在G中找到从sources中所有顶点可达的所有顶点 boolean marked(int v) //v是可达的吗
public class DirectedDFS{
private boolean[] marked;
//单点可达性
public DirectedDFS(Digraph G,int s){
mark = new boolean[G.V()];
dfs(G,s);
}
//多点可达性
public DirectedDFS(Digraph G, Iterable<Integer> sources){
mark = new boolean[G.V()];
for(int s : sources)
if(!marked[s]) dfs(G,s);
}
//深度优先遍历算法
private void dfs(Graph 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]; }
}有向图的顶点对之间的可达性：
在无向图中，这个问题很好解决，等价于连通性问题。无向图中需要线性时间的预处理能达到常数时间的查询操作。但在有向图图中，该问题目前还达不到这样的效率。
有向图G的传递闭包是由相同的一组顶点组成的另一幅有向图，在传递闭包中存在一条从v指向w的边当且仅当G中w是从v可达的。我们很容易想到通过计算有向图的传递闭包来解决顶点对的可达性问题，但一般来说，一幅有向图的传递闭包中所含的边比原图中多得多，与其明确计算一幅有向图的传递闭包，不如使用深度优先搜索来实现。
定义API：
public class TransitiveClosure TransitiveClosure(Digraph G) //预处理构造器 boolean reachable(int v,int w) //w是从v可达的吗
public class TransitiveClosure{
private DirectedDFS[] all; //all[]数组中每个元素都是一个以下标为起始顶点的深度优先遍历逆后序排列
public TransitiveClosure(Digraph G) {
all = new DirectedDFS[G.V()];
for(int v = 0; v<G.V();v++)
all[v] = new DirectedDFS(G,v);
}
boolean reachable(int v,int w) {
return all[v].marked(w);
}
}此方法不适用于实际问题中大型有向图，因为构造函数所需要的空间和V^2成正比，所需要的时间和V(V+E)成正比：共有V个DirectedDFS对象，每个所需的空间都与V成正比（他们都含有大小为V的marked[]数组并会检查E条边来计算标记）。
本质上，该方法是通过计算G的传递闭包来支持常数时间查询----传递闭包的第v行就是TransitiveClosure类中 DirectedDFS[]数组中第v个元素的marked[]数组。
用远小于平方级别的空间支持常数级别的查询的一般解决方案仍是一个有待解决的研究问题。