下面代码实现一个有向图数据结构，并添加常用有向图属性和功能。
package algorithms.graph; import algorithms.bag.Bag; import ioutil.In; import ioutil.StdOut; import java.io.FileReader; public class Digraph { private final int V;// 顶点总数，定义final，第一次初始化以后不可更改。 private int E;// 边总数 private Bag<Integer>[] adj;// {邻接表}顶点为数组下标，值为当前下标为顶点值所连通的顶点个数。 public Digraph(int v) { this.V = v; this.E = 0; adj = new Bag[V]; for (int i = 0; i < V; i++) { adj[i] = new Bag<Integer>(); } } public Digraph(In in) { this(in.readInt()); int E = in.readInt(); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); addEdge(v, w); } } public int V() { return this.V; } public int E() { return this.E; } /** * v和w是两个顶点，中间加一条边，增加稠密度。 * * @param v 大V是顶点总数，v是顶点值，所以并v不存在大小限制 * @param w 同上。 */ public void addEdge(int v, int w) { adj[v].add(w); E++; } /** * 返回一个顶点的连通顶点集合的迭代器 * * @param v * @return Bag本身就是迭代器，所以返回该顶点的连通顶点集合Bag即可。 */ public Iterable<Integer> adj(int v) { return adj[v]; } /** * 将图中所有方向反转 * * @return 返回一个图将所有方向反转后的副本 */ public Digraph reverse() { Digraph R = new Digraph(V); for (int v = 0; v < V; v++) { for (int w : adj[v]) {// 遍历原图中跟v顶点连通的顶点w。 R.addEdge(w, v); } } return R; } /** * 按照邻接表数组结构输出有向图内容 * * @return */ public String toString() { String s = V + " vertices, " + E + " edges\n"; for (int v = 0; v < V; v++) { s += v + ": "; for (int w : this.adj(v)) { s += w + " "; } s += "\n"; } return s; } public static void main(String[] args) { Digraph d = new Digraph(5); d.addEdge(0, 1); d.addEdge(1, 0); d.addEdge(2, 3); d.addEdge(0, 4); StdOut.println(d); /** 输出： 5 vertices, 3 edges 0: 4 1 1: 0 2: 3: 4: */ } }以上背包和有向图代码相关解释请具体参照代码中注释。
可达性上面提到了有向图中的可达性和图中的连通性的关系，可达性是连通性的特殊形式，对方向敏感，所以提到有向图，不可不研究可达性。
可达性解答了“从一个顶点v到达另一个顶点w，是否存在一条有向路径”等类似问题。
深度优先搜索解答可达性问题，要借助深度优先搜索算法。为了更好的理解深度优先算法，先来搞清楚如何完全探索一个迷宫。
Tremaux搜索完全探索一个迷宫的规则是：从起点出发，不走重复路线，走到终点走出迷宫。具体流程：
每当第一次到达一个新的顶点或边时，标记上。
在走的过程中，遇到一个已标记的顶点或边时，退回到上一个顶点。
当回退到的顶点已没有可走的边时继续回退。
我想Tremaux搜索会给我们带来一些启发，回到图的深度优先搜索算法。
package algorithms.graph; import algorithms.bag.Bag; import ioutil.StdOut; /** * 基于深度优先搜索（Depth First Search）解答有向图顶点可达性问题。 */ public class DigraphDFS { private boolean[] marked;// 是否标记过 /** * 算法：在图中找到从某个顶点出发的所有顶点 * * @param digraph * @param start */ public DigraphDFS(Digraph digraph, int start) { marked = new boolean[digraph.V()];// 初始化marked数组 dfs(digraph, start); } /** * 算法：在图中找到从某些顶点出发的所有顶点，这些顶点被作为一个集合传入。 * * @param digraph * @param startSet */ public DigraphDFS(Digraph digraph, Iterable<Integer> startSet) { marked = new boolean[digraph.V()]; for (int w : startSet) { dfs(digraph, w); } } /** * 查询某个顶点是否被标记（是否可达，因为标记过就是可达的） * * @param v * @return */ public boolean marked(int v) { return marked[v]; } /** * 深度优先搜索核心算法，通过标记，在图中从v顶点出发找到有效路径 * <p> * 返回的是通过标记形成的一条有效路径。 * * @param digraph * @param v */ private void dfs(Digraph digraph, int v) { marked[v] = true;// 标记起点可达。 for (int w : digraph.adj(v)) {// 遍历v顶点可达的一级顶点。 if (!marked[w]) dfs(digraph, w);// 如果发现w顶点未到达过，则继续从w开始dfs（即向前走了一步） } } public static void main(String[] args) { Digraph d = new Digraph(5);// 初始化五个顶点的图 d.addEdge(0, 1); d.addEdge(1, 0); d.addEdge(2, 3); d.addEdge(0, 4); Bag<Integer> startSet = new Bag<>(); startSet.add(2); DigraphDFS reachable = new DigraphDFS(d, startSet); for (int v = 0; v < d.V(); v++) { if (reachable.marked(v)) { StdOut.print(v + " "); } StdOut.println(); } /** * 输出： * 2 3 */ } }