算法4.4 有向图可达性

  • 单点可达性:给定G和起点s,问:是否存在一条从s到给定顶点v的有向路径
    • 和Graph的DFS方法完全一致
  • 多点可达性:是否存在一条从集合中任意顶点(顶点集sources)到给定顶点v的有向路径

有向图可达性API:public class DirectedDFS

返回类型 方法 描述
DirectedDFS(Digraph G, int s) 在G中找从s可达的所有结点
DirectedDFS(Digraph G, Iterable sources) G中找点集source可达的所有结点
boolean marked(int v) v是否可达

实现

  1. import edu.princeton.cs.algs4.In;
  2. import edu.princeton.cs.algs4.StdOut;
  4. public class DirectedDFS {
  5.     private boolean[] marked;//是否可达
  6.     private int count;//连通分量数字
  8.     public DirectedDFS(Digraph G, int s){
  9.         marked = new boolean[G.V()];
  10.         dfs(G, s);
  11.     }
  13.     //多点连通性,搜索给定点集可有向连通的点
  14.     public DirectedDFS(Digraph G, Iterable<Integer> sources){
  15.         for (int s: sources){
  16.             marked = new boolean[G.V()];
  17.             if (!marked(s)) dfs(G, s);
  18.         }
  19.     }
  21.     private void dfs(Digraph G, int v){
  22.         marked[v] = true;
  23.         count++;
  24.         for (int w: G.adj(v))
  25.             if (!marked(w))
  26.                 dfs(G, w);
  27.     }
  29.     public int count(){ return count;}
  30.     private boolean marked(int v){ return marked[v];}
  32.     public static void main(String[] args){
  33.         Digraph G = new Digraph(new In(args[0]));
  34.         Bag<Integer> source = new Bag();
  35.         for (int i = 0; i < args.length; i++)
  36.             source.add(Integer.parseInt(args[i]));
  38.         DirectedDFS reachable = new DirectedDFS(G, source);
  40.         for (int i = 0; i < G.V(); i++)
  41.             if (reachable.marked(i)) StdOut.print(i + " ");
  42.         StdOut.println();
  43.     }
  44. }

算法分析

  • 命题:在有向图中,DFS标记由一个集合的顶点可达的所有顶点所需时间与被标记的所有顶点出度之和成正比

算法应用

  • 垃圾回收算法:内存管理系统(如Java实现)标记-清楚的垃圾回收策略会为每个对象保留一个位做垃圾收集之用:周期性的运行一个DirectedDFS有向图可达性算法标记可达对象,清理未被标记的对象.
  • 有向图的寻路
    • 单点有向路径:即DFPath,只需用Digraph替换Graph
    • 单点最短有向路径:即BFPath,同上