有向图
目录在有向图中，边是单向的：每条边所连接的两个顶点都是一个有序对，它们的邻接性是单向的。
有向图的数据类型
有向图 API：
public class Digraph {
Digraph(int V); // 创建一幅含有 V 个顶点但不含有边的有向图
Digraph(In in); // 从标准输入流中读取一幅有向图
int V(); // 顶点数
int E(); // 边数
void addEdge(int v, int w); // 添加一条边 v -> w
Iterable<Integer> adj(int v); // 由 v 指出的边所连接的所有顶点
Digraph reverse(); // 该图的方向图
String toString();
}
// 有向图
public class Digraph {
private int V;
private int E;
private Bag<Integer>[] adj;
public Digraph(int V) {
this.V = V;
this.E = 0;
this.adj = new Bag[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new Bag<>();
}
}
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 void addEdge(int v, int w) {
adj[v].add(w);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
public Digraph reverse() {
Digraph digraph = new Digraph(V);
for (int v = 0; v < v; v++) {
for (int w : adj[v]) {
digraph.addEdge(w, v);
}
}
return digraph;
}
public int V() {
return V;
}
public int E() {
return E;
}
}
可达性
可达性：是否存在一条从起点 s 到顶点 v 的路径
有向图可达性 API：
public class DirectedDFS {
DirectedDFS(Digraph G, int s);
DirectedDFS(Digraph G, Iterable<Integer> souces); // 多个起点
boolean marked(int v);
}
深度优先搜索：
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];
}
}
有向路径
有向路径 API：
public interface DirectedPaths {
boolean hasPathTo(int v);
Iterable<Integer> pathTo(int v);
}
深度优先搜索：
public class DepthFirstDirectedPaths implements DirectedPaths {
private boolean[] marked;
private int s;
private int[] pathTo;
public DepthFirstDirectedPaths(Digraph G, int s) {
this.marked = new boolean[G.V()];
this.s = s;
this.pathTo = new int[G.V()];
dfs(G, s);
}
private void dfs(Digraph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
pathTo[w] = v;
dfs(G, w);
}
}
}
@Override
public boolean hasPathTo(int v) {
return marked[v];
}
@Override
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> stack = new Stack<>();
while (v != s) {
stack.push(v);
v = pathTo[v];
}
stack.push(s);
return stack;
}
}
广度优先搜索：
public class BreadthFirstDirectedPaths implements DirectedPaths {
private boolean[] marked;
private int s;
private int[] pathTo;
public BreadthFirstDirectedPaths(Digraph G, int s) {
this.marked = new boolean[G.V()];
this.s = s;
this.pathTo = new int[G.V()];
bfs(G, s);
}
private void bfs(Digraph G, int s) {
Queue<Integer> queue = new Queue<>();
queue.add(s);
marked[s] = true;
while (!queue.isEmpty()) {
int v = queue.remove();
for (int w : G.adj(v)) {
if (!marked[w]) {
pathTo[w] = v;
queue.add(w);
marked[w] = true;
}
}
}
}
@Override
public boolean hasPathTo(int v) {
return marked[v];
}
@Override
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> stack = new Stack<>();
while (v != s) {
stack.push(v);
v = pathTo[v];
}
stack.push(v);
return stack;
}
}