图解有向环拓扑排序与Kosaraju算法

图算法第三篇 图解：有向环、拓扑排序与Kosaraju算法

首先来看一下明天的内容纲要，内容十分多，次要是对算法思路与起源的解说，图文并茂，心愿对你有帮忙~

1.有向图的概念和示意

概念

有向图与上一篇文章中的无向图绝对，边是有方向的，每条边所连贯的两个顶点都是一个有序对，它们的邻接性都是单向的。

一幅有方向的图（或有向图）是由一组顶点和一组有方向的边组成的，每条有方向的边都连贯着一对有序的顶点。

其实在有向图的定义这里，咱们没有很多要阐明的，因为大家会感觉这种定义都是很天然的，然而咱们要始终记得有方向这件事！

数据表示

咱们仍然应用邻接表存储有向图，其中v-->w示意为顶点v的邻接链表中蕴含一个顶点w。留神因为方向性，这里每条边只呈现一次！

咱们来看一下有向图的数据结构如何实现，上面给出了一份Digraph类(Directed Graph)

package Graph.Digraph;import java.util.LinkedList;public class Digraph{    private final int V;//顶点数目    private int E;//边的数目    private LinkedList<Integer> adj[];//邻接表    public Digraph(int V){        //创立邻接表        //将所有链表初始化为空        this.V=V;this.E=0;        adj=new LinkedList[V];        for(int v=0;v<V;++v){            adj[v]=new LinkedList<>();        }    }    public int V(){ return V;}//获取顶点数目    public int E(){ return E;}//获取边的数目    //留神，只有这里与无向图不同    public void addEdge(int v,int w){        adj[v].add(w);//将w增加到v的链表中        E++;    }    public Iterable<Integer> adj(int v){        return adj[v];    }    //获取有向图的取反    public Digraph reverse(){        Digraph R=new Digraph(V);        for(int v=0;v<V;v++){            for(int w:adj(V))                R.addEdge(w, v);//扭转退出的程序        }        return R;    }}

如果你曾经把握了无向图的数据表示，你会发现有向图只是改了个名字而已，只有两处须要留神的中央：addEdge(v,w)办法与reverse()办法。在增加一条边时因为有了方向，咱们只须要在邻接表中减少一次；reverse()办法可能返回一幅图的取反（即每个方向都颠倒过去），它会在当前的利用中发挥作用，当初咱们只有有个印象就行。

2.有向图的可达性

在无向图（上一篇文章）中，咱们应用深度优先搜寻能够找到一条门路，应用广度优先搜寻能够找到两点间的最短门路。认真想一下，它们是否对有向图实用呢？是的，同样的代码就能够实现这个工作，咱们不须要做任何的改变（除了Graph换成Digraph）。

因为这些内容在上篇文章中都曾经具体介绍过，所以就不开展了，有趣味的话能够翻一下上篇文章，有具体的图示解说。

3.环和有向无环图

咱们在理论生存中可能会面临这样一个问题：优先级限度下的调度问题。说人话就是你须要做一些事件，比方A,B,C，然而做这三件事件有肯定的程序限度，做B之前必须实现A,做C之前必须实现B…………你的工作就是给出一个解决方案（如何安顿各种事件的程序），使得限度都不抵触。

如上图，第一种和第二种状况都比拟好办，然而第三种？是不是哪里出了问题！！！

对于下面的调度问题，咱们能够通过有向图来形象，顶点示意工作，箭头的方向示意优先级。不难发现，只有有向图中存在有向环，任务调度问题就不可能实现！所以，咱们上面要解决两个问题：

• 如何检测有向环（只查看存在性，不思考有多少个）
• 对于一个不存在有向环的有向图，如何排序找到解决方案（任务调度问题）

1.寻找有向环

咱们的解决方案是采纳深度优先搜寻。因为由系统维护的递归调用栈示意的正是“以后”正在遍历的有向门路。一旦咱们找到了一条有向边v-->w,并且w曾经存在于栈中，就找到了一个环。因为栈示意的是一条由w指向v的有向门路，而v-->w正好补全了这个环。同时，如果没有找到这样的边，则意味着这幅有向边是无环的。

咱们所应用的数据结构：

• 根本的dfs算法
• 新增一个onStack[]数组用来显式地记录栈上的顶点（即一个顶点是否在栈上）

咱们还是以一个具体的过程为例解说

具体的代码我想曾经难不倒你了，咱们一起来看看吧

package Graph.Digraph;import java.util.Stack;public class DirectedCycle {    private boolean [] marked;    private int [] edgeTo;    private Stack<Integer> cycle;//有向环中的所有顶点（如果存在）    private boolean[] onStack; //递归调用的栈上的所有顶点    public DirectedCycle(Digraph G){        onStack=new boolean[G.V()];        edgeTo=new int[G.V()];        marked=new boolean[G.V()];                for(int v=0;v<G.V();v++){            if(!marked[v]) dfs(G,v);        }    }    private void dfs(Digraph G,int v){        onStack[v]=true;//进入dfs时，顶点v入栈        marked[v]=true;        for(int w:G.adj(v)){            if(this.hasCycle()) return;            else if(!marked[w]){                edgeTo[w]=v;dfs(G,w);            }            else if(onStack[w]){                //重点                cycle=new Stack<Integer>();                for(int x=v;x!=w;x=edgeTo[x])                    cycle.push(x);                cycle.push(w);                cycle.push(v);            }        }        //退出dfs时，将顶点v出栈        onStack[v]=false;    }    public boolean hasCycle(){        return cycle!=null;    }    public Iterable<Integer> cycle(){        return cycle;    }}

该类为规范的递归 dfs() 办法增加了一个布尔类型的数组 onStack[] 来保留递归调用期间栈上的
所有顶点。当它找到一条边 v → w 且 w 在栈中时，它就找到了一个有向环。环上的所有顶点能够通过
edgeTo[] 中的链接失去。

在执行 dfs(G,v) 时，查找的是一条由终点到 v 的有向门路。要保留这条门路, DirectedCycle保护了一个由顶点索引的数组 onStack[]，以标记递归调用的栈上的所有顶点（在调用
dfs(G,v) 时将 onStack[v] 设为 True，在调用完结时将其设为 false）。DirectedCycle 同时也
应用了一个 edgeTo[] 数组，在找到有向环时返回环中的所有顶点，

2.拓扑排序

如何解决优先级限度下的调度问题？其实这就是拓扑排序

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

上面是一个典型的例子（排课问题）

它还有一些其余的典型利用，比方：

当初，筹备工作曾经差不多了，请集中注意力，这里的思维可能不是很好了解。紧跟我的思路。

当初首先假如咱们有一副有向无环图，确保咱们能够进行拓扑排序；通过拓扑排序，咱们最终心愿失去一组顶点的先后关系，排在后面的元素指向排在前面的元素，也就是对于任意的一条边v——>w，咱们失去的后果应该保障顶点v在顶点w后面；

咱们应用dfs解决这个问题，在调用dfs(v)时，以下三种状况必有其一：

• dfs(w)曾经被调用过且曾经返回了（此时w曾经被标记）
• dfs(w)曾经被调用过且还没有返回（认真想想这种状况，这是不可能存在的）
• dfs(w)还没有被调用（w还没有被标记），此时状况并不简单，接下来会调用dfs(w)，而后返回dfs(w)，而后调用dfs(v)

简而言之，咱们能够失去一个很重要的论断：dfs(w)始终会在dfs(v)之前实现。 换句话说，先实现dfs的顶点排在前面

请确保你齐全了解了下面的思维，接下来其实就绝对容易了。咱们创立一个栈，每当一个顶点dfs实现时，就将这个顶点压入栈。 最初，出栈就是咱们须要的程序

其实到这里拓扑排序基本上就曾经被咱们解决了，不过这里咱们拓展一下，给出一些常见的排序形式，其中咱们方才说到的其实叫做逆后序排序。它们都是基于dfs。

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

咱们在这里一并实现这三个排序办法，在递归中它们体现得非常简略

package Graph.Digraph;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;public class DepthFirstOrder {    private boolean [] marked;    private Queue<Integer> pre;//所有顶点的前序排列    private Queue<Integer> post;//所有顶点的后序排列    private Stack<Integer> reversePost;//所有顶点的逆后序排列    public DepthFirstOrder(Digraph G){        pre=new LinkedList<>();        post=new LinkedList<>();        reversePost = new Stack<>();        marked=new boolean[G.V()];        for(int v=0;v<G.V();v++){            if(!marked[v]) dfs(G,v);        }    }    private void dfs(Digraph G,int v){        pre.offer(v);        marked[v]=true;        for(int w:G.adj(v))            if(!marked[w])                dfs(G, w);        post.offer(v);        reversePost.push(v);    }    //这里能够不必管    public Iterable<Integer> pre()      {  return pre;  }    public Iterable<Integer> post()    {  return post;  }    public Iterable<Integer> reversePost()    {  return reversePost;  }}

祝贺你，到这儿咱们曾经齐全能够实现拓扑排序，上面的Topological类实现了这个性能。在给定的有向图蕴含环的时候，order()办法返回null,否则会返回一个可能给出拓扑有序的所有顶点的迭代器（当然，你也能够很简略的将排序顶点打印进去）。具体的代码如下：

package Graph.Digraph;public class Topological {    private Iterable<Integer> order;//顶点的拓扑程序    public Topological(Digraph G){        //判断给定的图G是否有环        DirectedCycle cyclefinder=new DirectedCycle(G);        if(!cyclefinder.hasCycle()){            DepthFirstOrder dfs=new DepthFirstOrder(G);            order = dfs.reversePost();        }    }    public Iterable<Integer> order(){        return order;    }    //判断图G是不是有向无环图    public boolean isDAG(){        return order!=null;    }    }

到这儿，有向环的检测与拓扑排序的内容就完结了，接下来咱们要思考有向图的强连通性问题

4.强连通重量

1.强连通的定义

回忆一下咱们在无向图的时候，过后咱们就利用深度优先搜寻解决了一幅无向图的连通问题。依据深搜可能达到所有连通的顶点，咱们很容易解决这个问题。然而，问题变成有向图，就没有那么简略了！上面别离是无向图和有向图的两个例子：

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

以下是另一些强连通的例子：

2.强连通重量

在有向图中，强连通性其实是顶点之间的一种等价关系，因为它有以下性质

• 自反性：任意顶点 v 和本人都是强连通的
• 对称性：如果 v 和 w 是强连通的，那么 w 和 v 也是强连通的
• 传递性：如果 v 和 w 是强连通的且 w 和 x 也是强连通的，那

么 v 和 x 也是强连通的

因为等价，所以和无向图一样，咱们能够将一幅图分为若干个强连通重量，每一个强连通重量中的所有顶点都是强连通的。这样的话，任意给定两个顶点判断它们之间的强连通关系，咱们就直接判断它们是否在同一个强连通重量中就能够了！

接下来，咱们须要设计一种算法来实现咱们的指标————将一幅图分为若干个强连通重量。咱们先来总结一下咱们的指标：

3.Kosaraju算法

Kosaraju算法就是一种经典的解决强连通性问题的算法，它实现很简略，然而不好了解why，心愿你打起精神，我心愿我可能把它讲明确（也只是心愿，我会尽量，如果不分明的话，强烈建议联合算法4一起食用）

回顾一下咱们之前在无向图的局部如何解决连通性问题的，一次dfs可能恰好遍历一个连通重量，所以咱们能够通过dfs来计数，获取每个顶点的id[];所以，咱们在解决有向图的强连通性问题时，也心愿可能利用一次dfs可能恰好遍历一个连通重量的性质；不过，在有向图中，它生效了，来看一下图一：

在图一中，dfs遍历会存在两种状况：

第一种状况：如果dfs的终点时顶点A，那么一次dfs遍历会遍历整个区域一和区域二，然而区域一与区域二并不是强连通的，这就是有向图给咱们带来的艰难！

第二种状况：如果dfs的终点是顶点D，则第一次dfs会遍历区域二，第二次dfs会遍历区域一，这不就是咱们想要的吗？

所以，第二个状况给了咱们一个致力的方向！也就是如果咱们人为地，将所有的可能的状况都变成第二种状况，事件不就解决了！

有了方向，那么接下来，咱们来看一幅实在的有向图案例，如图二所示，这是一幅有向图，它的各个强连通重量在图中用灰色标记；咱们的操作是将每个强连通重量看成一个顶点（比拟大而已），那么会产生什么结果呢？咱们的原始的有向图就会变成一个有向无环图！

ps:想一想为什么不能存在环呢？因为前提咱们把所有的强连通重量看成了一个个顶点，如果顶点A和顶点B之间存在环，那A和B就会形成一个更大的强连通重量！它们本应属于一个顶点！

在失去一幅有向无环图（DAG）之后，事件没有那么简单了。当初，咱们再回忆一下咱们的目标————在图一中，咱们心愿区域二先进行dfs，也就是箭头指向的区域先进行dfs。在将一个个区域形象成点后，问题归纳于在一幅有向无环图中，咱们要找到一种程序，这种程序的规定是箭头指向的顶点排在前！

到这儿，咱们略微好好想想，咱们的工作就是找到一种进行dfs的程序，这种程序，是不是和咱们在后面讲到的某种排序十分相似呢？我想你曾经不难想到了，就是拓扑排序！然而和拓扑排序是齐全相同的。

咱们把箭头了解为优先级，对于顶点A指向顶点B，则A的优先级高于B。那么对于拓扑排序，优先级高者在前；对于咱们的工作，优先级低者在前（咱们想要的后果就是dfs不会从优先级低的中央跑到优先级高的中央）

对于图二：咱们想要的后果如图三所示：

如果咱们从顶点1开始进行dfs，顺次向右，那么永远不会产生咱们不心愿的状况！因为箭头是单向的！

我想，到这儿，你应该差不多了解我的意思了。咱们还有最初一个小问题————如何获取拓扑排序的反序？

其实解决办法很简略：对于一个有向图G,咱们先取反（reverse办法），将图G的所有边的程序颠倒，而后获取取反后的图的逆后序排序（咱们不能称为拓扑排序，因为真实情况是有环的）；最初，咱们利用方才取得的顶点程序对原图G进行dfs即可，这时它的原理与上一篇文章无向图的完全一致！

最初，总结一下Kosaraju算法的实现步骤：

• 1.在给定的一幅有向图 G 中，应用 DepthFirstOrder 来计算它的反向图 GR 的逆后序排列。
• 2.在 G 中进行规范的深度优先搜寻，然而要依照方才计算失去的程序而非标准的程序来拜访

所有未被标记的顶点。

具体的实现代码只在无向图的实现CC类中减少了两行代码（扭转dfs的程序）

package Graph.Digraph;public class KosarajuSCC {    private boolean[] marked;   // 已拜访过的顶点    private int[] id;           // 强连通重量的标识符    private int count;          // 强连通重量的数量   public KosarajuSCC(Digraph G)    {       marked = new boolean[G.V()];       id = new int[G.V()];       DepthFirstOrder order = new DepthFirstOrder(G.reverse()); //重点      for (int s : order.reversePost()) //重点         if (!marked[s])          {  dfs(G, s); count++;  }    }   private void dfs(Digraph G, int v)    {       marked[v] = true;       id[v] = count;       for (int w : G.adj(v))          if (!marked[w])              dfs(G, w);    }   public boolean stronglyConnected(int v, int w)    {  return id[v] == id[w];  }   public int id(int v)    {  return id[v];  }   public int count()   { return count;}}

最初，附上一幅具体的操作过程：

有了Kosaraju算法，咱们很容易可能判断

• 给定的两个顶点的连通性（上文代码stronglyConnected)
• 该图中有多少个强连通重量（上文代码count)

后记

好了，对于有向图的内容就到这里了，我心愿通过这篇文章你可能彻底了解这三种算法！，下一篇文章小超与你不见不散！

最初送你一幅图算法的思维导图

后盾回复【图算法】可取得xmind格局，我只想说：真的好多内容！????

码字绘图不易，如果感觉本文对你有帮忙，关注作者就是最大的反对！棘手点个在看更感激不尽！

欢送大家关注我的公众号：小超说 ，之后我会持续创作算法与数据结构以及计算机基础知识的文章。也能够加我微信chao_hey（备注：职业-城市） ，咱们一起交换，一起提高！

本文参考：《算法》（第四版）