目录
1、定义
一幅有方向性的图(或有向图)是由一组顶点和一组有方向的边组成的，每条有方向的 边都连接着有序的一对顶点。
1.1、应用
1.2、术语
一个顶点的出度为 由该顶点指出的边的总数;
一个顶点的入度为指向该顶点的边的总数。
2、数据结构
有向图的数据结构和无向图的数据结构基本一样，区别在于无向图在addEdge时会将两个顶点互相连接，而有向图只能按照指定方向将这两个顶点相连。
2.1、代码
public class Digraph { private int V; // 顶点的总数 private int E; // 边的总数 private Bag<Integer>[] adj; // 存放所有顶点的的链表，链表里边放着各自的所有相邻顶点 public Digraph(int V) { this.V = V; adj = new Bag[V]; for (int i = 0; i < V; i++) { adj[i] = new Bag<>(); } } public Digraph(In in) { V = in.readInt(); adj = new Bag[V]; int E; for (E = 0; E < this.V; ++E) { this.adj[E] = new Bag<>(); } 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 int E() { return E; } public int V() { return V; } public Iterable<Integer> adj(int v) { return adj[v]; } /** * 反向图 */ public Digraph reverse() { Digraph D = new Digraph(V); for (int v = 0; v < D.V; v++) { for (int w : adj(v)) { D.addEdge(w, v); } } return D; } }
3、有向图的可达性
在有向图中，因为边的方向性的限制，导致我们的点只能按照指定的方向前进，我们有时会需要找出 从一个点出发，它能到达图中所有可能到达的点。
对于这样的需求，其实我们应用无向图的深度优先搜索就能获取结果，因为每个顶点的链表存放着的都是它能到达的顶点，和无限图中相邻的顶点是一样的。
3.1、代码
public class DirectedDFS { private final boolean[] marked; // 标记是否走过该点 private int s;// 起点 public DirectedDFS(Digraph D, int s) { marked = new boolean[D.V()]; dfs(D, s); } public DirectedDFS(Digraph D, Iterable<Integer> sources) { marked = new boolean[D.V()]; for (int s : sources) { if (!marked[s]) { dfs(D, s); } } } private void dfs(Digraph D, int v) { marked[v] = true; for (int w : D.adj(v)) { if (!marked(w)) { dfs(D, w); } } } private boolean marked(int w) { return marked[w]; } public static void main(String[] args) { Digraph G = new Digraph(new In(args[0])); Bag<Integer> sources = new Bag<>(); 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(); } }
3.2、垃圾回收机制---有向图的应用
多点可达性的一个重要的实际应用是在典型的内存管理系统中，包括许多 Java 的实现。
在一幅有向图中，一个顶点表示一个对象，一条边则表示一个对象对另一个对象的引用。这个模型很好 地表现了运行中的 Java 程序的内存使用状况。在程序执行的任何时候都有某些对象是可以被直接 访问的，而不能通过这些对象访问到的所有对象都应该被回收以便释放内存。标 记 - 清除的垃圾回收策略会为每个对象保留一个位做垃圾收集之用。它会周期性地运行一个类似于 DirectedDFS 的有向图可达性算法来标记所有可以被访问到的对象，然后清理所有对象，回收没有 被标记的对象，以腾出内存供新的对象使用。
4、有向图的路径
有向图和无向图的路径都可以通过深度优先搜索和广度优先搜索来查找。寻找路径的代码可以用来解决一下问题：
单点有向路径。给定一幅有向图和一个起点 s，回答“从 s 到给定目的顶点 v 是否存在一条有 向路径?如果有，找出这条路径。”等类似问题。
单点最短有向路径。给定一幅有向图和一个起点 s，回答“从 s 到给定目的顶点 v 是否存在一 条有向路径?如果有，找出其中最短的那条(所含边数最少)。”等类似问题。
4.1、深度优先搜索
public class DepathFirstPath { private boolean[] marked; // 标记是否走过该点 private int edge[]; // s-w 路径上 w 的上一个顶点 private int s; public DepathFirstPath(Digraph D, int s) { marked = new boolean[D.V()]; edge = new int[D.V()]; this.s = s; dfs(D, s); } private void dfs(Digraph D, int v) { marked[v] = true; for (int w : D.adj(v)) { if (!marked[w]) { edge[w] = v; dfs(D, w); } } } public boolean hasPathTo(int w) { return marked[w]; } @Nullable private Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; Stack<Integer> path = new Stack<>(); for (int w = edge[v]; w != s; w = edge[w]) { path.push(w); } path.push(s); return path; } }
4.1、有向图最短路径---广度优先搜索
深度优先搜索就好像是一个 人在走迷宫，广度优先搜索则好像是一组人在一起朝各个方向走这座迷宫， 每个人都有自己的绳子。当出现新的叉路时，可以假设一个探索者可以分裂 为更多的人来搜索它们，当两个探索者相遇时，会合二为一(并继续使用先 到达者的绳子)。
这样做的目的可以是从起点出发到达每个顶点的路径是最短的。
下图有深度和广度优先搜索的区别。
public class BreadthFirstPath { private boolean[] marked; private int[] edge; private int s; public BreadthFirstPath(Digraph D,int s) { marked = new boolean[D.V()]; edge = new int[D.V()]; this.s=s; bfs(D,s); } private void bfs(Digraph D,int s){ Queue<Integer> queue=new Queue<>(); queue.enqueue(s); while (!queue.isEmpty()) { int v=queue.dequeue(); for (int w:D.adj(v)){ if (!marked[w]){ edge[w]=v; marked[w]=true; queue.enqueue(w); } } } } private boolean hasPathTo(int v){ return marked[v]; } @Nullable private Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; Stack<Integer> path = new Stack<>(); for (int w = edge[v]; w != s; w = edge[w]) { path.push(w); } path.push(s); return path; } }
5、拓扑排序
对于有向图，一种应用广泛的模型是给定一组任务并安排它们的执行顺序，并且这些任务是有优先级限制的。就比如任务A的优先级高于任务B，那么我们必须在任务A完成之后才能执行任务B。
就比如学校课程的分配，每个课程也是有优先级的，而且一些基础课程一定要放在高级课程的前面。但对于一张复杂的课程优先图，我们怎么来实现将所有课程的按照优先级排序呢？
拓扑排序。给定一幅有向图，将所有的顶点排序，使得所有的 有向边均从排在前面的元素指向排在后面的元素。
下图就是通过拓扑排序将所有课程按照优先级的顺序排列的，右下图是拓扑排序的应用。
5.1、有向无环图检查
对有向图进行拓扑排序前，我们必须确认该有向图中是否含有环，如果存在环的话，那么对于优先级的问题是会造成无解的情况， 你可以想象一下，任务A--->任务B---->任务C---->任务A 不断的循环，那么我们要把哪个任务放在第一个呢？
这时候我们就需要对有向图进行检测，当没有环的时候才能进行拓扑排序，不然是无解的。
public class DirectedCycle { private final boolean[] marked; //是否走过该点 private final boolean[] onStack; //对递归路径上的点存入栈中（true），当该路径没有环时改为false private final int[] edge; // s-w 路径上 w 的上一个顶点 private Stack<Integer> cycle; //存放有向环的所有顶点 public DirectedCycle(Digraph D) { marked=new boolean[D.V()]; onStack=new boolean[D.V()]; edge=new int[D.V()]; for (int i=0;i<D.V();i++){ if (!marked(i)){ dfs(D,i); } } } private void dfs(Digraph D,int v){ marked[v]=true; onStack[v]=true; for (int w:D.adj(v)){ if (!marked(w)){ edge[w]=v; dfs(D,w); }else if (onStack[w]){ cycle=new Stack<>(); for (int k=edge[w];k!=w;k=edge[k]){ cycle.push(k); } cycle.push(w); cycle.push(v); } } onStack[v]=false; //-------记住退出递归之后要释放该点，以防下条路径有环并且含有该点 } public boolean hasCycle(){ return cycle!=null; } public Iterable<Integer> cycle(){ return cycle; } private boolean marked(int w){ return marked[w]; } }
5.2、基于深度优先搜索的顶点排序
在深度优先搜索的时候，我们其实会产生三种顶点的排序方式：（如果不理解，看一下代码就能理解了）
- 前序:在递归调用之前将顶点加入队列。
- 后序:在递归调用之后将顶点加入队列。
- 逆后序:在递归调用之后将顶点压入栈。
public class DepthFirstOrder { private final boolean[] marked; private final Queue<Integer> pre; //前序 private final Queue<Integer> post; //后序 private final Stack<Integer> reversePost; //逆后序 public DepthFirstOrder(Digraph D) { marked = new boolean[D.V()]; pre = new Queue<>(); post = new Queue<>(); reversePost = new Stack<>(); for (int v = 0; v < D.V(); v++) { if (!marked(v)) { dfs(D,v); } } } private void dfs(Digraph D, int v) { marked[v] = true; pre.enqueue(v); //在递归调用之前将顶点加入队列。 for (int w : D.adj(v)) { if (!marked(w)) { dfs(D, w); } } post.enqueue(v); //在递归调用之后将顶点加入队列。 reversePost.push(v); //在递归调用之后将顶点压入栈。 } private boolean marked(int w) { return marked[w]; } public Iterable<Integer> pre(){ return pre; } public Iterable<Integer> post(){ return post; } public Iterable<Integer> reversePost(){ return reversePost; } }
5.3、拓扑排序
一幅有向无环图的拓扑顺序即为所有顶点的逆后序排列。
证明：对于任意边 v → w，在调用 dfs(v) 时，下面三种情况必有其一成立。
dfs(w) 已经被调用过且已经返回了(w 已经被标记)。
dfs(w)还没有被调用(w还未被标记)，因此v→w会直接或间接调用并返回dfs(w)，且 dfs(w) 会在 dfs(v) 返回前返回。
dfs(w) 已经被调用但还未返回。证明的关键在于，在有向无环图中这种情况是不可能出现的，这是由于递归调用链意味着存在从w到v的路径，但存在v→w则表示存在一个环。
在两种可能的情况中，dfs(w) 都会在 dfs(v) 之前完成，因此在后序排列中 w 排在 v 之前而 在逆后序中 w 排在 v 之后。因此任意一条边 v → w 都如我们所愿地从排名较前顶点指向排名较后的顶点。
public class Topological { private Iterable<Integer> order; public Topological(Digraph D) { DirectedCycle cycle = new DirectedCycle(D); if (!cycle.hasCycle()) { DepthFirstOrder depthFirstOrder = new DepthFirstOrder(D); this.order = depthFirstOrder.reversePost(); } } public Iterable<Integer> order(){ return order; } /** * 是否是有向无环图 */ public boolean isDAG() { return order!=null; } }
6、有向图中的强连通分量
无向图中的连通分量：是指子图的数量。
有向图中：如果两个顶点 v 和 w 是互相可达的，则称它们为强连通的。也就是说，既存在一条从 v 到 w 的有向路径，也存在一条从 w 到 v 的有向路径。如果一幅有向图中的任意两个顶点都是强 连通的，则称这幅有向图也是强连通的。
强连通分量：指的是一个有向图中，含有这样可以互相抵达的子集的数量。
下图就有5个强连通分量，单个顶点也是一个强连通分量。
我们要想得到一个有向图中的强连通分量，思路是：
1、我们要想确认这个子集是一个强连通分量，那么我们得证明： v--->w是可达的 并且 w--->v 也是可达的
2、我们先讲有向图中的指向关系反转 v--->w 改成 w--->v
3、然后我们将指向关系反转的有向图，进行深度优先搜索，并且得到它的拓扑排序后的序列a。（这样做的目的是先证明w--->v是可达的）
4、我们按照序列a的顺序对原来的有向图进行可达性检验，当 v--->w 可达的话，那么就证明 v---w属于一个强连通分量中。
public class KosarajuSCC { private boolean[] marked; private int[] id; private int count; public KosarajuSCC(Digraph D) { marked=new boolean[D.V()]; id=new int[D.V()]; DepthFirstOrder order=new DepthFirstOrder(D.reverse()); for (int v:order.reversePost()){ if (!marked(v)){ dfs(D,v); count++; } } } private void dfs(Digraph D, int v) { marked[v]=true; id[v]=count; for (int w:D.adj(v)){ if (!marked(w)){ dfs(D,w); } } } private boolean marked(int w) { return marked[w]; } public boolean stronglyConnected(int v,int w){ return id[v]==id[w]; } public int id(int v){ return id[v]; } private int count() { return count; } }
- 版权声明：文章来源于网络采集，版权归原创者所有，均已注明来源，如未注明可能来源未知，如有侵权请联系管理员删除。
