Directed Graph

术语

• 定义：一副有方向性的图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
• 出度：一个顶点指出的边的总数
• 入度：指向该顶点的边的总数
• 有向环：至少含有一条边且起点和终点都相同的有向路径。
• 简单有向环：一条（除了起点和终点必须相同之外）不含有重复的顶点和边的环。
• 约定每个顶点都能到达自己

有向图的数据类型

class Digraph {
  private V: number;
  private E: number;
  private adj: number[][];
  private data: TGraphData;

  constructor(data: TGraphData, initEdge: boolean = true) {
    this.V = data.V;
    this.E = 0;
    this.adj = [];

    this.data = data;  // just save for reverse();
    if (initEdge) {
      data.edges.forEach(([v, w]) => this.addEdge(v, w));
    }
  }

  public addEdge(v: number, w: number) {
    this.adj[v] = this.adj[v] || [];
    this.adj[w] = this.adj[w] || [];
    this.adj[v].push(w);
    // this.adj[w].push(v);
    this.E++;
  }

  public adjOf(v: number) {
    return this.adj[v];
  }

  public getV() {
    return this.V;
  }

  public getE() {
    return this.E;
  }

  public reverse(): Digraph {
    const r = new Digraph(this.data, false);
    for (let v = 0; v < r.getV(); v++) {
        this.adjOf(v).forEach(w => r.addEdge(w, v));
    }
    return r;
  }
}

几乎就是拷贝自之前无向图的Graph类，不同的在于

• 因为有方向，用邻接表表示的时候，w在v的链表中，不一定v也在w的链表中。所以在添加边（addEdge）的时候只要为一方添加就可以了
• 增加了reverse方法，将图中所有的方向反向。之所以需要这个是因为这样可以找出指向每个顶点的所有边，而adjOf()给出的每个顶点指出的边连接的所有顶点。

有向图的可达性

无向图可以使用dfs来解决连通性的问题，而这里有向图用和无向图完全相同的代码，只是将Graph替换环Digraph也可以解决判断是否存在一条s到v的有向路径的问题。例如下面这幅图：

对应的数据：

const data: TGraphData = {
  V: 13,
  edges: [
    [4, 2],
    [2, 3],
    [3, 2],
    [6, 0],
    [0, 1],
    [2, 0],
    [11, 12],
    [12, 9],
    [9, 10],
    [9, 11],
    [8, 9],
    [10, 12],
    [11, 4],
    [4, 3],
    [3, 5],
    [7, 8],
    [8, 7],
    [5, 4],
    [0, 5],
    [6, 4],
    [6, 9],
    [7, 6],
  ]
}

DirectedDFS实现和无向图的dfs完全一样。这里测试输出顶点6所有可达的顶点。

class DirectedDFS {
  private marked: boolean[];  // 标记所有与s连通的点
  private count: number; // 与s连通点的顶点总数

  constructor(g: Digraph, s: number) {
    this.marked = [];
    this.count = 0;
    this.dfs(g, s);
  }

  private dfs(g: Digraph, v: number) {
    this.marked[v] = true;  // 每访问一个点v则标记为已访问
    this.count++;
    g.adjOf(v).forEach(adj => {  // 遍历v的每一个相邻点
      if (!this.marked[adj]) {
        this.dfs(g, adj);
      }
    })
  }

  public getMarked(w: number) {
    return this.marked[w];
  }

  public getCount() {
    return this.count;
  }
}

const main = () => {
  const g = new Digraph(data);
  const search = new DirectedDFS(g, 6);

  const marked = [];
  for (let v = 0; v < g.getV(); v++) {
    if (search.getMarked(v)) {
      marked.push(v);
    }
  }
  console.log(marked.join(', '));  // 0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12
}

main();

应用

多点可达性的一个应用是内存管理系统。一副有向图中，顶点表示对象，边表示一个对象对另一个对象对引用。

在程序执行的任何时候都有某些对象是可以被直接访问的，而不能通过这些对象访问到的所有对象都应该被回收以便释放内存

周期性的运行一个类似于DirectedDFS的算法来标记所有可以被访问的对象，然后开始清理所有对象，回收♻️那些没有被标记的对象。

环和有向无环图

原则上说一幅有向图可能含有大量的环，实际应用中，一般只会重点关注其中一小部分，或者只想知道他们是否存在。

调度问题

一种应用广泛的模型是给定一组任务并安排他们的执行顺序，限制条件是这些任务的执行方法和起始时间，可能也还包括任务耗时以及消耗的其他资源。最重要的一种限制条件是叫做优先级限制，指明了哪些任务必须在哪些任务之前完成。以一个大学生安排课程为例，有些课必须在其他课完成后才能开始。

如果再假设该学生一次只能修一门课，就遇到了优先级限制下的调度问题。在满足限制条件的前提下应该如何安排并完成所有任务？

上面的图可以抽象成下面的一张有向图，顶点对应任务，有向边对应优先级顺序。

在有向图中，优先级限制下的调度问题等价于下面这个基本问题。

拓扑排序：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者无法做到）。

比如下图为示例的拓扑排序，所有的边都是向下的，清晰的表示了这个优先级问题的一个解决办法。按照这个顺序，该同学就可以完成所有的课程。

一般来说，如果一个优先级限制的问题中存在有向环，那么这个问题肯定是无解的。因此要如何完成有向环检测？

定义：有向无环图（DAG）就是一副不含有环的有向图

基于深度优先搜索来解决这个问题并不困难，思路是在寻找一条路径的时候将每个点记录下来，如果找到一条边v->w且w已经被记录过了，那么就找到了一个环。

class DirectedCycle {
  private marked: boolean[];
  private edgeTo: number[];
  private cycle: number[]; // 有向环中的所有顶点
  private onStack: boolean[];  // 递归调用栈上的所有顶点

  constructor(g: Digraph) {
    this.marked = [];
    this.edgeTo = [];
    this.onStack = [];
    this.cycle = [];

    for (let v = 0; v < g.getV(); v++) {
      if (!this.marked[v]) {
        this.dfs(g, v);
      }
    }
  }

  private dfs(g: Digraph, v: number) {
    this.onStack[v] = true;
    this.marked[v] = true;
    g.adjOf(v).forEach(w => {
      if (this.hasCycle()) {
        return;
      } else if (!this.marked[w]) {
        this.edgeTo[w] = v;
        this.dfs(g, w);
      } else if (this.onStack[w]) {
        for (let x = v; x != w; x = this.edgeTo[x]) {
          this.cycle.push(x);
        }
        this.cycle.push(w);
        this.cycle.push(v);
      }
    })
    this.onStack[v] = false;
  }

  public hasCycle(): boolean {
    return this.cycle.length > 0;
  }

  public getCycle(): number[] {
    return this.cycle;
  }
}

这里的关键在于维护了一个onStack来记录递归调用栈上的所有顶点，并在在一个顶点的邻接点递归扫描完后置为false，移除当前递归路径。通过edgeTo来找到有向环中的所有顶点。而cycle的话，以下面为例，cycle最终为[3, 4, 5, 3]。

解决了检测有向环的问题，再来考虑拓扑排序的问题。我感觉拓扑排序的问题其实就是如何进行dfs时候顶点的遍历顺序的问题。当一个顶点遍历完成的时候，将其压入栈中，最后全部完成的时候从栈顶一个个拿出来的顺序就是拓扑排序。

通常人们关心的是以下三种排列顺序：

• 前序：在递归调用之前将顶点加入队列
• 后序：在递归调用之后将顶点加入队列
• 逆后序：在递归调用之后将顶点压入栈

class DepthFirstOrder {
  private marked: boolean[];
  private pre: number[];
  private post: number[];
  private reversePost: number[];

  constructor(g: Digraph) {
    this.pre = [];
    this.post = [];
    this.reversePost = [];
    this.marked = [];

    for (let v = 0; v < g.getV(); v++) {
      if (!this.marked[v]) {
        this.dfs(g, v);
      }
    }
  }

  private dfs(g: Digraph, v: number) {
    this.pre.push(v);
    this.marked[v] = true;
    g.adjOf(v).forEach(w => {
      if (!this.marked[w]) {
        this.dfs(g, w);
      }
    })

    this.post.push(v);
    this.reversePost.unshift(v);
  }

  public getPre() {
    return this.pre;
  }

  public getPost() {
    return this.post;
  }

  public getReversePost() {
    return this.reversePost;
  }
}

这里三种序列都是用的数组表示，因为读取的时候从头开始读，所以push操作就相当于加入队列。而要通过unshift从前面插入元素就满足栈先进后出的效果。

拓扑排序：

class Topological {
  private order: number[];

  constructor(g: Digraph) {
    const cyclefinder = new DirectedCycle(g);
    this.order = [];
    if (!cyclefinder.hasCycle()) {
      const dfo = new DepthFirstOrder(g);
      this.order = dfo.getReversePost();
    }
  }

  public getOrder() {
    return this.order;
  }

  public isDAG() {
    return this.order.length > 0;
  }
}

实际调用：

const data: TGraphData = {
  V: 13,
  edges: [
    [2, 3],
    [0, 5],
    [0, 1],
    [0, 6],
    [2, 0],
    [11, 12],
    [9, 11],
    [9, 12],
    [9, 10],
    [3, 5],
    [8, 7],
    [5, 4],
    [6, 4],
    [6, 9],
    [7, 6],
  ]
}

const main = () => {
  const g = new Digraph(data);
  const top = new Topological(g);

  console.log(top.getOrder().join(', '));
  // 8, 7, 2, 3, 0, 6, 9, 10, 11, 12, 1, 5, 4
}

main();

有向图中的强连通性

在无向图中，如果有一条路径连接顶点v到w，则他们就是连通的——既可以从v到w，也可以从w到v。而在有向图中，如果v到w有路径，但是w到v可以有路径也可能没有。

定义：如果两个顶点v到w是互相可达到，则称他们为强连通的。即，既存在一条从v到w到有向路径，也存在一条从w到v到有向路径。如果一幅有向图中的任意两个顶点都是强连通的，则称这幅图是强连通的

两个顶点时强连通的，当且仅当他们都在一个普通的有向环中

强连通分量

和无向图一样，有向图中的强连通性也是一种顶点之间平等关系，这种平等关系将所有顶点分为一些平等的部分，每个部分都是由相互均为强连通的顶点的最大子集组成的，我们将这些子集称为强连通分量。如下图，有5个强连通分量。

应用举例

在理解有向图的结构时，强连通性是一种非常重要的抽象。比如食物链，这种有向图中的强连通性能帮助生态学家理解食物链中能量的流动。

Kosaraju算法

• 给定一副有向图G，使用DepthFirstOrder来计算它的反向图GR的逆后序排列
• 在G中进行进行深度优先搜索，但是要按照上一步中的逆后序来访问
• 构造函数中，所有在同一个递归dfs()调用中被访问的顶点都在同一个强连通分量中。

代码跟之前无向图的CC类基本一样。

class KosarajuSCC {
  private marked: boolean[];
  private count: number;  // 连通分量数
  private id: number[];  // 记录每一个顶点的连通分量的标识符

  constructor(g: Digraph) {
    this.marked = [];
    this.count = 0;
    this.id = [];

    // 用反向图来计算逆后序
    const order = new DepthFirstOrder(g.reverse());

    order.getReversePost().forEach(s => {
      if (!this.marked[s]) {
        this.dfs(g, s);
        // 每一次dfs走完都意味着走完了一个连通分量
        this.count++;
      }
    })
  }

  private dfs(g: Digraph, v: number) {
    this.marked[v] = true;
    this.id[v] = this.count;
    g.adjOf(v).forEach(adj => {
      if (!this.marked[adj]) {
        this.dfs(g, adj);
      }
    })
  }

  public getMarked(w: number) {
    return this.marked[w];
  }

  public getCount() {
    return this.count;
  }

  public getId(v: number) {
    return this.id[v];
  }

  public stronglyConnected(v: number, w: number) {
    return this.id[v] === this.id[w];
  }
}

测试图还是上面这个图：

对应的数据及调用：

const data: TGraphData = {
  V: 13,
  edges: [
    [4, 2],
    [2, 3],
    [3, 2],
    [6, 0],
    [0, 1],
    [2, 0],
    [11, 12],
    [12, 9],
    [9, 10],
    [9, 11],
    [8, 9],
    [10, 12],
    [11, 4],
    [4, 3],
    [3, 5],
    [7, 8],
    [8, 7],
    [5, 4],
    [0, 5],
    [6, 4],
    [6, 9],
    [7, 6],
  ]
}

const main = () => {
  const g = new Digraph(data);
  const search = new KosarajuSCC(g);

  console.log(`components: ${search.getCount()}`);

  const components: number[][] = [];
  for (let i = 0; i < g.getV(); i++) {
    const id = search.getId(i);
    components[id] = components[id] || [];
    components[id].push(i);
  }
  console.log(components);
}

main();
// components: 5
// [ [ 1 ], [ 0, 2, 3, 4, 5 ], [ 9, 10, 11, 12 ], [ 6 ], [ 7, 8 ] ]

这个算法容易实现，但是难以理解。我是这么理解这个过程的：

• 首先要搞清逆后序是怎样一个序列

  回忆一下之前那个选课的问题，逆后序是在每个点递归完毕后将该点压入栈中的序列，而因为是先进后出，所以拿出来的序列就是最先开始访问的点到最后访问的点的序列，简言之，即顶点递归调用的顺序。

• 每个和s强连通的顶点v都会在构造函数调用的dfs(G, s)中被访问。这个很好理解，强连通就以为有s到v有路径，dfs(G, s)会访问到每一个s可达的点。

• 构造函数调用dfs(G, s)所到达的点v一定和s强连通的

  难以理解的就是这个。既然dfs(G, s)访问到了v，那么就说明s到v存在路径，需要证明的就是在G中v到s也存在路径，或者，去证明GR中存在s到v的路径。

  如果dfs(G, s)访问到了v，在这个逆后序中，v肯定是在s之后的，如果v在s之前那v肯定会先完成，被标记，dfs(G, s)也就访问不到v了。v在s之后，这意味着在GR中进行dfs的时候，dfs(G, v)肯定在dfs(G, s)之前结束了，因为先进后出的原因，既然它排在后面，那么它肯定是先进去的，或者说先完成。此时dfs(G, v)的调用有两种可能：

  • 在dfs(G, s)之前调用，并且也在dfs(G, s)调用之前结束

    这种情况就是v没有出现在dfs(G, s)递归调用链中的情况，而我们这里一开始就是假设的s到v有路径，那么其实等于说GR中v到s有路径，而如果v到s有路径的话，dfs(G, v)会在dfs(G, s)之前调用没错，但是会在dfs(G, s)结束之后才结束。因此这种情况不可能出现。

  • 在dfs(G, s)之后调用，并且也在dfs(G, s)结束之前结束

    这种情况正好说明了s到v有路径，得证！

本节代码：https://github.com/Yuijam/algorithms-note/tree/main/graph/directed