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

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

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

首先来看一下今天的内容纲领,内容异常多,主要是对算法思绪与泉源的解说,图文并茂,希望对你有辅助~

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

1.有向图的观点和示意

观点

有向图与上一篇文章中的无向图相对,边是有偏向的,每条边所毗邻的两个极点都是一个有序对,它们的毗邻性都是单向的。

一幅有偏向的图(或有向图)是由一组极点和一组有偏向的边组成的,每条有偏向的边都毗邻着一对有序的极点。

实在在有向图的界说这里,我们没有许多要说明的,由于人人会以为这种界说都是很自然的,然则我们要始终记得有偏向这件事!

数据示意

我们依然使用毗邻表存储有向图,其中v-->w示意为极点v的毗邻链表中包罗一个极点w。注重由于偏向性,这里每条边只泛起一次!

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

我们来看一下有向图的数据结构若何实现,下面给出了一份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…………你的义务就是给出一个解决方案(若何放置各种事情的顺序),使得限制都不冲突。

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

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

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

如上图,第一种和第二种情形都比较好办,然则第三种?是不是那里出了问题!!!

对于上面的调剂问题,我们可以通过有向图来抽象,极点示意义务,箭头的偏向示意优先级。不难发现,只要有向图中存在有向环,义务调剂问题就不可能实现!以是,我们下面要解决两个问题:

  • 若何检测有向环(只检查存在性,不思量有多少个)
  • 对于一个不存在有向环的有向图,若何排序找到解决方案(义务调剂问题)

1.寻找有向环

我们的解决方案是接纳深度优先搜索。由于由系统维护的递归挪用栈示意的正是“当前”正在遍历的有向路径。一旦我们找到了一条有向边v-->w,而且w已经存在于栈中,就找到了一个环。由于栈示意的是一条由w指向v的有向路径,而v-->w正好补全了这个环。同时,若是没有找到这样的边,则意味着这幅有向边是无环的。

我们所使用的数据结构:

  • 基本的dfs算法
  • 新增一个onStack[]数组用来显式地纪录栈上的极点(即一个极点是否在栈上)

我们还是以一个详细的历程为例解说

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

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

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

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

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

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

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

详细的代码我想已经难不倒你了,我们一起来看看吧

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 → ww 在栈中时,它就找到了一个有向环。环上的所有极点可以通过
edgeTo[] 中的链接获得。

在执行 dfs(G,v) 时,查找的是一条由起点到 v 的有向路径。要保留这条路径, DirectedCycle维护了一个由极点索引的数组 onStack[],以符号递归挪用的栈上的所有极点(在挪用
dfs(G,v) 时将 onStack[v] 设为 True,在挪用竣事时将其设为 false)。DirectedCycle 同时也
使用了一个 edgeTo[] 数组,在找到有向环时返回环中的所有极点,

2.拓扑排序

若何解决优先级限制下的调剂问题?实在这就是拓扑排序

拓扑排序的界说:给定一幅有向图,将所有的极点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素(或者说明无法做到这一点)

下面是一个典型的例子(排课问题)

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

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

它另有一些其他的典型应用,好比:

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

现在,准备工作已经差不多了,请集中注重力,这里的头脑可能不是很好明了。紧跟我的思绪。

现在首先假设我们有一副有向无环图,确保我们可以举行拓扑排序;通过拓扑排序,我们最终希望获得一组极点的先后关系,排在前面的元素指向排在后面的元素,也就是对于随便的一条边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完成时,就将这个极点压入栈。 最后,出栈就是我们需要的顺序

Netty源码阅读之如何将TCP的读写操作和指定线程绑定

实在到这里拓扑排序基本上就已经被我们解决了,不外这里我们拓展一下,给出一些常见的排序方式,其中我们适才说到的实在叫做逆后序排序。它们都是基于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.强连通的界说

回忆一下我们在无向图的时刻,那时我们就行使深度优先搜索解决了一幅无向图的连通问题。凭据深搜能够到达所有连通的极点,我们很容易解决这个问题。然则,问题酿成有向图,就没有那么简朴了!下面分别是无向图和有向图的两个例子:

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

界说。若是两个极点vw是相互可达的,则称它们为强连通的。也就是说,既存在一条从 vw的有向路径,也存在一条从wv的有向路径。若是一幅有向图中的随便两个极点都是强
连通的,则称这幅有向图也是强连通的。

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

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

2.强连通分量

在有向图中,强连通性实在是极点之间的一种等价关系,由于它有以下性子

  • 自反性:随便极点 v 和自己都是强连通的
  • 对称性:若是 v 和 w 是强连通的,那么 w 和 v 也是强连通的
  • 传递性:若是 v 和 w 是强连通的且 w 和 x 也是强连通的,那
    么 v 和 x 也是强连通的

由于等价,以是和无向图一样,我们可以将一幅图分为若干个强连通分量,每一个强连通分量中的所有极点都是强连通的。这样的话,随便给定两个极点判断它们之间的强连通关系,我们就直接判断它们是否在同一个强连通分量中就可以了!

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

接下来,我们需要设计一种算法来实现我们的目的————将一幅图分为若干个强连通分量。我们先来总结一下我们的目的:

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

3.Kosaraju算法

Kosaraju算法就是一种经典的解决强连通性问题的算法,它实现很简朴,然则欠好明了why,希望你打起精神,我希望我能够把它讲明了(也只是希望,我会只管,若是不清楚的话,强烈建议连系算法4一起食用)

回忆一下我们之前在无向图的部门若何解决连通性问题的,一次dfs能够正好遍历一个连通分量,以是我们可以通过dfs来计数,获取每个极点的id[];以是,我们在解决有向图的强连通性问题时,也希望能够行使一次dfs能够正好遍历一个连通分量的性子;不外,在有向图中,它失效了,来看一下图一:

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

在图一中,dfs遍历会存在两种情形:

第一种情形:若是dfs的起点时极点A,那么一次dfs遍历会遍历整个区域一和区域二,然则区域一与区域二并不是强连通的,这就是有向图给我们带来的难题!

第二种情形:若是dfs的起点是极点D,则第一次dfs会遍历区域二,第二次dfs会遍历区域一,这不就是我们想要的吗?

以是,第二个情形给了我们一个起劲的偏向!也就是若是我们人为地,将所有的可能的情形都酿成第二种情形,事情不就解决了!

有了偏向,那么接下来,我们来看一幅真实的有向图案例,如图二所示,这是一幅有向图,它的各个强连通分量在图中用灰色符号;我们的操作是将每个强连通分量看成一个极点(比较大而已),那么会发生什么结果呢?我们的原始的有向图就会酿成一个有向无环图!

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

ps:想一想为什么不能存在环呢?由于条件我们把所有的强连通分量看成了一个个极点,若是极点A极点B之间存在环,那AB就会组成一个更大的强连通分量!它们本应属于一个极点!

在获得一幅有向无环图(DAG)之后,事情没有那么庞大了。现在,我们再回忆一下我们的目的————在图一中,我们希望区域二先举行dfs,也就是箭头指向的区域先举行dfs。在将一个个区域抽象成点后,问题归结于在一幅有向无环图中,我们要找到一种顺序,这种顺序的规则是箭头指向的极点排在前

到这儿,我们稍微好好想想,我们的义务就是找到一种举行dfs的顺序,这种顺序,是不是和我们在前面讲到的某种排序十分相似呢?我想你已经不难想到了,就是拓扑排序!然则和拓扑排序是完全相反的。

我们把箭头明了为优先级,对于极点A指向极点B,则A的优先级高于B。那么对于拓扑排序,优先级高者在前;对于我们的义务,优先级低者在前(我们想要的效果就是dfs不会从优先级低的地方跑到优先级高的地方)

对于图二:我们想要的效果如图三所示:

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

若是我们从极点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算法

有了Kosaraju算法,我们很容易能够判断

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

后记

好了,关于有向图的内容就到这里了,我希望通过这篇文章你能够彻底明了这三种算法!,下一篇文章小超与你不见不散!

最后送你一幅图算法的头脑导图

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

后台回复【图算法】可获得xmind花样,我只想说:真的很多多少内容!

码字绘图不易,若是以为本文对你有辅助,关注作者就是最大的支持!随手点个在看更感激涕零!

迎接人人关注我的民众号:小超说 ,之后我会继续创作算法与数据结构以及盘算机基础知识的文章。也可以加我微信chao_hey(备注:职业-都会) ,我们一起交流,一起提高!

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

本文参考:《算法》(第四版)
转载请注明出处博客园【小超说】https://www.cnblogs.com/chaotalk/p/13304385.html

原创文章,作者:admin,如若转载,请注明出处:https://www.2lxm.com/archives/22774.html