精华内容
下载资源
问答
  • 有向完全图和强连通图的区别?

    千次阅读 2020-08-14 10:52:27
    有向完全图和强连通图的区别?其他概念: 首先了解概念 相邻关系:两个顶点之间存在一条边,则表示两个顶点具有相邻关系 路径:相邻顶点序偶所构成的序列 路径长度:路径上边的数目 回路:若一条路径中第一个顶点和...

    首先了解概念

    相邻关系:两个顶点之间存在一条边,则表示两个顶点具有相邻关系
    路径:相邻顶点序偶所构成的序列
    路径长度:路径上边的数目
    回路:若一条路径中第一个顶点和最后一个顶点相同,则为回路
    连通从顶点Vi到顶点Vj有路径,则称Vi和Vj连通
    连通图和连通分量是针对无向图的
    强连通图和强连通分量是针对有向图的
    在这里插入图片描述

    区别在哪里?

    由概念感觉两者像是形式不同但意思一样,但不一样的说法.
    任意两个不同顶点之间都存在方向相反的两条弧.

    看概念:

    • 如果图中任意两个顶点之间都连通,则称该图为连通图。
    • 连通从顶点Vi到顶点Vj有路径,则称Vi和Vj连通
    • 路径相邻顶点序偶所构成的序列
      其实最大的疑惑是路径是相邻顶点

    其实可看出,连通是两个顶点连通就可以,也就是说,连通图是说两个顶点连通,不一定非要是相邻的两个顶点。

    一个无向图G= (V,E)是连通的,那么边的数目大于等于顶点的数目减一

    有向完全图和强连通图的区别?

    有向完全图一定是强连通的,但强连通不一定是有向完全图
    看概念:

    • 强连通图(Strongly Connected Graph)是指在有向图G中,如果对于每一对vi、vj,vi≠vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
    • 有向完全图:具有n(n-1)条边的有向图称为有向完全图

    有n个顶点的强连通图最多有n(n-1)条边,最少有n条边
    证明:

    • (1)最多的情况:即n个顶点中两两相连,若不计方向,n个点两两相连有n(n-1)/2条边,而由于强连通图是有向图,故每条边有两个方向,n(n-1)/2×2=n(n-1),故有n个顶点的强连通图最多有n(n-1)条边。
      在这里插入图片描述

    • (2)最少的情况:即n个顶点围成一个圈,且圈上各边方向一致,即均为顺时针或者逆时针,此时有n条边。
      在这里插入图片描述

    下面举例说明:如图1所示,设ABCD四个点构成强连通图,则:
    (1)边数最多有4×3=12条
    (2)边数最少有4条
    即:一个有向图是强连通的,当且仅当G中有一个回路,它至少包含每个节点一次

    其他概念:

    图:由结点的有穷集合V和边的集合E组成。
    图的结点称为顶点,边是顶点的有序偶对。
    简单路径:序列中顶点不重复出现的路径称为简单路径
    网:边上带权的图称为带权图,也称为网
    无法在扩充顶点的连通子图称为极大连通子图
    一个图中的极大连通子图:从一个顶点开始作为子图,逐个添加和这个子图有边相连的顶点,直到所有相连顶点都被纳入其中,所生成的子图就是一个极大连通子图。

    图有多种存储方式,但一般用到的是邻接矩阵(顺序存储)和邻接表(链式存储)。
    邻接表:由单链表的表头形成的顶点表和单链表其余结点形成的边表两部分组成
    邻接多重表中,所有的依附于同一顶点的边串联在同一链表中,由于每条边依附于两个顶点,因此每个边结点同时链接在两个链表中。对无向图而言,其邻接多重表和邻接链表的差别仅仅在于,同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点

    展开全文
  • 图论:连通分量和强连通分量

    万次阅读 2018-06-07 10:19:24
    1.连通图1.1 顶点的连通性在无向图G中,若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径),则称vi和vj是连通的。1.2 连通图在无向图G中,若V(G)中任意两个不同的顶点vi和vj都连通(即有路径),则称G为连通图(Con-...
    1.连通图
    1.1 顶点的连通性
    在无向图G中,若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径),则称vi和vj是连通的。
    1.2 连通图
    在无向图G中,若V(G)中任意两个不同的顶点vi和vj都连通(即有路径),则称G为连通图(Con-nected Graph)。【例】图G2,和G3是连通图。

    有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图
    2.连通分量
    图论中无向图连通分量(或者仅分量)是一个子图,其中任何两个顶点通过路径相互连接,并且在图中不连接顶点。例如,图中显示的图形有三个连接的组件。没有边缘的顶点本身就是一个连通的组件。自身连接的图形只有一个连接组件,由整个图组成。
    在有向图的数学理论中,如果每个顶点都可以从其他顶点到达,则图被称为强连通或不连通。任意有向图的强连通分量连通分量形成一个划分成本身强连接的子图。可以在线性时间内(即Θ(V + E))测试图的强连通性,或者查找其强连通分量。


    2.1.无向图的连通分量
    无向图的G的极大连通子图称为G的连通分量(Connected)。任何连通图的连通分量都只有一个,即使是其本身,非连通的无向图有多个连通分量。
    使用广度优先搜索深度优先搜索来计算线性时间内图的连通分量(以图的顶点和边的数量表示)是很直接的。无论哪种情况,从某个特定顶点v开始的搜索将在返回之前找到包含v(并且不再有)的整个连接组件。要查找图的所有连通分量,循环遍历其顶点,每当循环到达一个尚未包含在先前找到的连通分量中的顶点时,开始新的宽度第一次或深度第一次搜索。
    2.1.有向图的强连通分量
    有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。
    2.1.1 算法思路
    Kosaraju算法思路
    这个算法可以说是最容易理解,最通用的算法,其比较关键的部分是同时应用了原图G和反图GT。步骤1:先用对原图G进行深搜形成森林(树),步骤2:然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是E-AB存在于反图GT),能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林,继续步骤2直到 没有顶点为止。
    改进思路:
    当然,基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时,可能深搜到其他树上去,这是不允许的,强连通分量只能存在单棵树中(由开篇第一句话可知)),我们当然不这么做,我们可以巧妙的选择第二深搜选择的树的顺序,使其不可能深搜到其他树上去。想象一下,如果步骤2是从森林里选择树,那么哪个树是不连通(对于GT来说)到其他树上的呢?就是最后遍历出来的树,它的根节点在步骤1的遍历中离开时间最晚,而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择,在第一次深搜遍历时,记录时间i离开的顶点j,即numb[i]=j。那么,我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。
    隐藏性质:
    分析到这里,我们已经知道怎么求强连通分量了。但是,大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢?如果在看上述思路的时候,你的脑子在思考,相信你已经知道了!!!它就是:如果我们把求出来的每个强连通分量收缩成一个点,并且用求出每个强连通分量的顺序来标记收缩后的节点,那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图拓扑序列。为什么呢?首先,应该明确搜索后的图一定是有向无环图呢?废话,如果还有环,那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量,而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列,我们在改进分析的时候,不是先选的树不会连通到其他树上(对于反图GT来说),也就是后选的树没有连通到先选的树,也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗?这就是Kosaraju算法的一个隐藏性质。
    伪代码
    Kosaraju_Algorithm:
    step1:对原图G进行深度优先遍历,记录每个节点的离开时间。
    step2:选择具有最晚离开时间的顶点,对反图GT进行遍历,删除能够遍历到的顶点,这些顶点构成一个强连通分量。
    step3:如果还有顶点没有删除,继续step2,否则算法结束。

    #include<iostream>
    #include<cstring>
    using namespace std;
    const int MAXN=110;
    int n;
    bool flag[MAXN];//访问标志数组
    int belg[MAXN];//存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量
    int numb[MAXN];//结束时间标记,其中numb[i]表示离开时间为i的顶点
    AdjTableadj[MAXN],radj[MAXN];//
    邻接表,逆邻接表
    //用于第一次深搜,求得numb[1..n]的值
    voidVisitOne(int cur,int& sig)
    {
        flag[cur]=true;
        for(inti=1;i<=adj[cur][0];++i)
            if(false==flag[adj[cur][i]])
                VisitOne(adj[cur][i],sig);
        numb[++sig]=cur;
    }
    //用于第二次深搜,求得belg[1..n]的值
    voidVisitTwo(int cur,int sig)
    {
        flag[cur]=true;
        belg[cur]=sig;
        for(inti=1;i<=radj[cur][0];++i)
            if(false==flag[radj[cur][i]])
                VisitTwo(radj[cur][i],sig);
    }
    //
    Kosaraju算法,返回为强连通分量个数
    int Kosaraju_StronglyConnectedComponent()
    {
        inti,sig;
        //第一次深搜
        memset(flag+1,0,sizeof(bool)*n);
        for(sig=0,i=1;i<=n;++i)
            if(false==flag[i])
                VisitOne(i,sig);
        //第二次深搜
        memset(flag+1,0,sizeof(bool)*n);
        for(sig=0,i=n;i>0;--i)
            if(false==flag[numb[i]])
                VisitTwo(numb[i],++sig);
        return sig;
    }
    


    展开全文
  • 连通图由若干连通图组成,都是极大连通子图。 2.树是一个无环连通图连通图的生成树是其一个子图,拥有图的所有顶点。 3.二分图 一种能够将所有节点分为两部分的图。简单的说,如果按双色上色,二分图的任意两个...

    本文仅作为《算法》第四版图的相关知识的个人笔记。

    几个概念:

    1.连通图:
    从任意一个顶点都存在一条路径到达另一个任意顶点。非连通图由若干连通图组成,都是极大连通子图。
    2.是一个无环连通图。连通图的生成树是其一个子图,拥有图的所有顶点。
    3.二分图
    一种能够将所有节点分为两部分的图。简单的说,如果按双色上色,二分图的任意两个相邻的顶点的颜色不同。
    4. 两个顶点通过一条边连接,称为相邻的。顶点的度数为与他相连的边的总数。有向图中的度数分为入度和出度,入度为指向该顶点的边的总数,出度为从该顶点指出的边的总数。
    5. 自环:一条连接顶点和其自身的边
    6. 一对顶点的两条边称为平行边

    PartOne:无向图相关算法

    一、无向图

    1.1 数据结构

     /**
         * 顶点数目
         */
        private final int V;
        /**
         * 边的数目
         */
        private int E;
        /**
         * 邻接表,Bag为背包,为一个只入不出的队列,adj[v]即表示与顶点v相连的顶点,因此相邻的两个顶点v和w分别会出现在对方的邻接表中
         */
        private Bag<Integer>[] adj;
    
    

    1.2 构造

     public Graph(int v) {
            V = v;
            this.E=0;
            adj=new Bag[V];
            for (int i = 0; i < V; i++) {
                adj[i]=new Bag<>();
            }
        }
    

    1.3 相关方法

    两顶点是否相邻:

      public boolean hasEdge(int v,int w){
      		//遍历顶点v的邻接表,查找有无顶点w
            for(int x:adj(v)){
                if (x==w){
                    return true;
                }
            }
            return false;
        }
    

    添加一条边:

     public void addEdge(int v,int w){
           //也可以通过判断v==w和hasEdge(v,w)决定是否允许自环和平行边
                adj[v].add(w);
                adj[w].add(v);
                E++;
       
    
        }
    
    //顶点度数
     public  int degree(int v){
            int degree=0;
            for (int w:adj(v)){
                degree++;
            }
            return degree;
        }
        //最大度数
        public  int maxDegree(){
            int max=0;
            for (int v = 0; v < V; v++) {
                int degree = degree(v);
                if (degree>max){
                    max=degree;
                }
            }
            return max;
        }
        //自环数
        public int numOfSelfLoops(Graph graph){
            int loops=0;
            for (int i = 0; i < graph.V(); i++) {
                for(int w:graph.adj(i)){
                    if (w==i){
                        loops++;
                    }
                }
            }
            return loops/2;
        }
    

    二、深度优先搜索

    简单的说就是 从给定顶点出发,一直向下走,直到下面没有路了,然后返回上一个顶点,继续进行同样方式遍历,直到遍历完所有的顶点。

    因此我们需要如下的数据结构:

    
     /**
         * 标记顶点i是否被访问
         */
        private boolean[] marked;
        /**
         * 从起点到一个顶点的已知路径上的最后一个顶点
         * 如 v->w->x  则edgeTo[w]=v,edgeTo[x]=w
         */
        private int[] edgeTo;
        /**
         * 遍历的起点
         */
        private final int s;      
    
    

    构造函数:

    public DepthFirstPaths(Graph G, int s) {
            this.s = s;
            //初始化两个数组
            edgeTo = new int[G.V()];
            marked = new boolean[G.V()];
            dfs(G, s);
        }
    

    深度优先遍历:

    private void dfs(Graph G, int v) {
    		//标记当前顶点为true
            marked[v] = true;
            //遍历与当前顶点相邻的顶点
            for (int w : G.adj(v)) {
            	//如果没有被访问
                if (!marked[w]) {
                	//标记起点到当前顶点的最后一个路径
                    edgeTo[w] = v;
                    //从当前节点继续进行遍历
                    dfs(G, w);
                }
            }
        }
    

    是否存在从起点到指定顶点的路径:

     public boolean hasPathTo(int v) {
            validateVertex(v);
            return marked[v];
        }
    

    返回从起点到指定顶点的路径,如果不存在返回null:

     public  Iterable<Integer> pathTo(int v) {
            if (!hasPathTo(v)){
               //没有到达路径,返回null
                return null;
            }
            //因为edgeTo保存的是到达当前节点的父节点,因此使用栈结构,这样从当前节点到起始顶点的顶点依此入栈,遍历的时候便是从起点到该顶点的完整路径
            Stack paths=new Stack();
            for (int i = v; i !=s ; i=edgeTo[i]) {
                paths.push(i);
            }
            paths.push(s);
    
            return paths;
        }
    

    测试:

     public static void main(String[] args) {
            Graph graph=new Graph(6);
            graph.addEdge(0,2);
            graph.addEdge(0,1);
            graph.addEdge(0,5);
            graph.addEdge(2,1);
            graph.addEdge(2,3);
            graph.addEdge(2,4);
            graph.addEdge(3,5);
            graph.addEdge(3,4);
            DepthFirstPaths dfs=new DepthFirstPaths(graph,0);
            Iterable<Integer> paths = dfs.pathTo(4);
            for (Integer i:paths){
                System.out.println(i.toString());
            }
        }
    

    结果:

    0
    5
    3
    4
    

    三、广度优先搜索:

    广度优先搜索的思想是,从当前节点,先遍历与该节点相邻的所有节点,然后再对相邻顶点进行广度优先遍历
    深度优先是纵向遍历,广度优先是横向遍历。

    数据结构:
    广度优先搜索的数据结构同深度基本一样:

    public class BreadthFirstPaths {
    	private final int start;
        private int[] edgeTo;
        private boolean[] marked;
    
        public BreadthFirstPaths(Graph graph,int start) {
            this.start = start;
            edgeTo=new int[graph.V()];
            marked=new boolean[graph.V()];
            bfs(graph,start);
        }
    }    
    

    但在遍历的时候采用队列进行辅助,思想如下:
    1.将当前顶点加入队列
    2.从出队出队一个顶点(第一次时出队的就是当前节点),遍历该顶点的所有相邻顶点,置marked[v]为true,并依此入队。
    3.当队列非空时,循环步骤2

    代码如下:

    private void bfs(Graph graph, int start) {
            Queue<Integer> queue=new Queue<>();
            queue.enqueue(start);
            marked[start]=true;
            while (!queue.isEmpty()){
                int v = queue.dequeue();
                for (int w:graph.adj(v)){
                    queue.enqueue(w);
                    edgeTo[w]=v;
                    marked[w]=true;
                }
            }
        }
    

    四、连通分量

    数据结构如下:

    public class CC {
    	 private boolean[] marked;   
        /**
         * 顶点属于哪个连通分量 如 顶点v属于第count个连通分量,则id[v]=count
         */
        private int[] id;
        /**
         * 第count个连通分量的顶点数
         */
        private int[] size;
        /**
         * 连通分量数
         */
        private int count;
        
    }    
    

    思想如下:
    遍历所有的顶点,对每个顶点都执行dfs深度优先遍历,如果两个顶点在同一个连通分量,那么在对一个顶点进行dfs遍历的时候,两个顶点必然会在构造函数的一个dfs中被访问到,属于同一个连通分量。
    构造函数:

    public CC(Graph G) {
            marked = new boolean[G.V()];
            id = new int[G.V()];
            size = new int[G.V()];
            //代码1
            for (int v = 0; v < G.V(); v++) {
                if (!marked[v]) {
                    dfs(G, v);
                    //与顶点v连通的所有顶点都遍历完毕后,说明该连通分量所有顶点已遍历完毕,增加count
                    count++;
                }
            }
     }
     private void dfs(Graph G, int v) {
            marked[v] = true;
            //顶点v属于第count个分量
            id[v] = count;
            //第count个分量的顶点数加1
            size[count]++;
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    dfs(G, w);
                }
            }
        }
    
    

    五、判断是否为无环图

    对于无向图而言,判断其是否为无环图很简单,在对某个顶点进行dfs遍历时,假如它的相邻顶点已被访问过,那么有两种可能:

    3-4-5-3为例
    每次dfs都传递要遍历的节点,和当前刚刚被遍历过的节点
    一开始三个顶点都未被访问
    1.现在对3进行dfs,访问到5,5被标记为true;
    2.再对5进行dfs,此时3已经被访问,但是此时的3属于顶点5的父级,不构成环,再访问4,标记4为true;
    3.接着对4进行dfs,此时顶点5被访问,同2一样,顶点5属于顶点4的“父级”,不构成环,但是3也被访问了,且3不是顶点4的“父级”,因此此处出现环。
    关键代码如下:

    private boolean[] marked;
        private boolean hasCycle;
    
        public Cycle(Graph G) {
            marked=new boolean[G.V()];
            for (int i = 0; i < G.V(); i++) {
                if (!marked[i]){
                    dfs(G,i,i);
                }
            }
        }
    
        private void dfs(Graph G,int v, int u){
            marked[v]=true;
            for(int w:G.adj(v)){
                if (!marked[w]){
                    dfs(G,w,v);
                }else if (w!=u){//如 3:5 5:3 就不构成环
                    hasCycle=true;
                }
            }
        }
    

    六、二分图问题

    这个同无环图问题类型,在对一个顶点进行dfs遍历时,将其未被访问的临接顶点置为与该顶点对立的颜色,若已经被访问,则判断该顶点的颜色与当前顶点的颜色是否不一样,如果一样,则不是二分图。

    关键代码如下:

     private void dfs(Graph graph, int v) {
            marked[v]=true;
            for (int w: graph.adj(v)){
                if (!marked[w]){
                    color[w]=!color[v];
                    dfs(graph,w);
                }else if (color[w]==color[v]){
                    isTwoColorable=false;
                    break;
                }
            }
        }
    

    PartTwo:有向图相关算法

    有向图的定义和无向图基本一样,这里也是基于临接表实现,但在插入边的时候,有向图只需要操作边的始点的邻接表,不需像无向图一样两个顶点的邻接表都插入对应的顶点。

    public class Digraph {
        private final int V;
        private int E;
        private Bag<Integer>[] adj;
    
        public Digraph(int v) {
            V = v;
            this.E=0;
            adj=new Bag[V];
            for (int i = 0; i < v; i++) {
                adj[i]=new Bag<>();
            }
        }
        public int V(){
            return V;
        }
        public int E(){
            return E;
        }
        public void addEdge(int v,int w){
            adj[v].add(w);
            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;
        }
    }
    
    

    一、有向图的可达性:

    这里同无向图一样,只需将Graph换为Digraph即可:
    进行DFS遍历:

    public class DirectedDFS {
        private boolean[] marked;
    
        /**
         * 单点可达性
         * 经过此方法,从marked(int v)返回是否存在一条从s到达给定顶点v的有向路径
         * @param digraph
         * @param s
         */
        public DirectedDFS(Digraph digraph,int s) {
            marked=new boolean[digraph.V()];
            dfs(digraph,s);
        }
    
        /**
         * 多点可达性
         * 是否存在一条从集合中的任意顶点到达给定顶点v的有向路径
         * @param digraph
         * @param sources
         */
        public DirectedDFS(Digraph digraph,Iterable<Integer> sources) {
            marked=new boolean[digraph.V()];
            for (int s:sources){
                if (!marked[s]){
                    dfs(digraph,s);
                }
            }
    
        }
    
        private void dfs(Digraph digraph, int v) {
            marked[v]=true;
            for (int w:digraph.adj(v)){
                if (!marked[w]){
                    dfs(digraph,w);
                }
            }
        }
    
        public boolean marked(int v){
            return marked[v];
        }
    
        public static void main(String[] args) {
            Digraph graph=new Digraph(6);
            graph.addEdge(0,2);
            graph.addEdge(0,1);
            graph.addEdge(0,5);
            graph.addEdge(2,1);
            graph.addEdge(2,3);
            graph.addEdge(4,5);
    
            DirectedDFS dfs=new DirectedDFS(graph,0);
            System.out.println(dfs.marked(3));
    
        }
    
    }
    
    

    顶点对的可达性

    借助DirectedDFS数组,我们可以实现顶点对的可达性:
    无论对于稀疏还是稠密的图,它都是理想的解决方案,但不适用于实际应用中的大型有向图,因为构造函数所需的空间和V²成正比,所需时间和V(V+E)成正比

    public class TransitiveClosure {
        private DirectedDFS[] directedDFS;  // tc[v] = reachable from v
    
        /**
         * 构造函数
         * 所需空间与V²成正比
         * 所需时间与 V(V+E)成正比
         * @param G
         */
        public TransitiveClosure(Digraph G) {
            directedDFS = new DirectedDFS[G.V()];
            for (int v = 0; v < G.V(); v++)
                directedDFS[v] = new DirectedDFS(G, v);
        }
    
        boolean reachable(int v,int w){
            return directedDFS[v].marked(w);
        }
    
    }
    
    

    二、单点有向路径和单点最短有向路径

    同无向图一样,单点有向路径就是借助DFS,对从s到v路径上的每一个顶点,使用edgeTo数组保存从s到该顶点的路径上的最后一个顶点坐标;而单点最短路径就是以同样的方式借助BFS保存从s到指定顶点的路径,这样得出的路径就是到达该顶点的最短路径。

    三、环和无环图(拓扑排序)

    在调度问题中,限制条件是这些任务的执行方法和起始时间,但最重要的限制条件叫做有限制级限制,它指明了任务间执行的先后顺序。

    我们需要在一个有优先级限制的任务中,按该限制条件找出安排完成任务的顺序。这也等价于一个基本问题:拓扑排序,即在一个有向图中,将所有顶点排序,满足所有的有向边均从排在前面的元素指向排在后面的元素(或指出无法做到这一点)。

    以高校课程安排为例,一些课程的开课必须要求学生修完前面的某些课,而拓扑排序就是在这种限制条件下,找出学生选修课程的顺序。

    而一旦一个优先级限制的问题中存在有向环,那么这个问题一定是无解的。因此我们需要进行有向环的检测。
    有向无环图就是不含有有向环的有向图

    检测有向环的思路如下:
    对有向图的每个顶点都进行DFS遍历,假设从顶点v开始深度优先遍历,将从该顶点递归调用路径上的所有顶点marked标记后再使用一个boolean[] onStack标记是否在递归栈上,如果对一个顶点的DFS递归调用没有发现有向环,则递归结束前再让该节点的onStack状态改为false;而如果对某个顶点的递归调用时发现另一个顶点已经被标记了,且onStack为true,则说明这个路径上一定存在有向环,这时将该环上的所有点加入Stack cycle栈中。

    public class DirectedCycle {
        private boolean[]marked;
        private int[] edgeTo;
        /**
         * 有向环中的所有顶点(如果存在)
         */
        private Stack<Integer>cycle;
    
        /**
         * 递归调用的栈上的所有顶点
         */
        private boolean[] onStack;
    
        public DirectedCycle(Digraph digraph) {
            marked=new boolean[digraph.V()];
            edgeTo=new int[digraph.V()];
            onStack=new boolean[digraph.V()];
            for (int v = 0; v < digraph.V(); v++) {
                if (!marked[v]){
                    dfs(digraph,v);
                }
            }
        }
    
        /**
         * 使用不带权的Digraph
         * @param digraph
         * @param v
         */
        private void dfs(Digraph digraph, int v) {
            onStack[v]=true;
            marked[v]=true;
            for (int w: digraph.adj(v)){
                if (this.hasCycle()){
                //如果已经找到有向环,则返回
                    return;
                } else if (!marked[w]){
                    edgeTo[w]=v;
                    dfs(digraph,w);
                }else if (onStack[w]){
                    cycle=new Stack<>();
                    for (int x = v; x != w; x=edgeTo[x]) {
                        cycle.push(x);
                    }
                    cycle.push(w);
                    cycle.push(v);
                }
            }
            //对v的一次递归调用后,如果没发现环,则重置为false
            onStack[v]=false;
    
        }
        public Iterable<Integer>cycle(){
            return cycle;
        }
        public boolean hasCycle(){
            return cycle!=null;
        }
    }
    
    

    测试:

    public static void main(String[] args) {
            Digraph digraph=new Digraph(4);
            digraph.addEdge(0,1);
            digraph.addEdge(2,3);
            digraph.addEdge(3,1);
            digraph.addEdge(1,2);
            //存在环3>1->2>3
            DirectedCycle cycle = new DirectedCycle(digraph);
            if (cycle.hasCycle()){
                System.out.println("存在环");
                Stack<Integer> stack = cycle.cycle;
                while (!stack.isEmpty()){
                    System.out.println(stack.pop());
                }
            }
        }
    

    结果:

    存在环
    3
    1
    2
    3
    

    《算法4》中给出:

    一幅有向无环图的拓扑排序就是所有顶点的逆后排序

    那么什么是逆后排序呢?
    我们规定:
    前序: 在对顶点v递归调用前就将该顶点加入队列,最后出队的顺序就是前序
    后序:在对顶点v递归调用后将该顶点加入队列,最后出队的顺序就是后序
    逆后序:在对顶点v递归调用后将该顶点加入栈中,最后出栈的顺序就是逆后序

    实现如下:

    /**
     * 有向图中基于深度优先搜索的顶点排序
     * @author MaoLin Wang
     * @date 2020/2/2214:55
     */
    public class DepthFirstOrder {
        private boolean[]marked;
        /**
         * 所有顶点的前序遍历(递归调用前加入队列)
         */
        private Queue<Integer> pre;
        /**
         * 所有顶点的后序遍历(递归调用后加入队列)
         */
        private Queue<Integer> post;
        /**
         * 所有顶点的逆后序遍历(递归调用后压入栈)
         */
        private Stack<Integer> reversePost;
    
        public DepthFirstOrder(Digraph digraph) {
            pre=new Queue<>();
            post=new Queue<>();
            reversePost=new Stack<>();
            marked=new boolean[digraph.V()];
    
            for (int v = 0; v < digraph.V(); v++) {
                if (!marked[v]){
                    dfs(digraph,v);
                }
            }
    
        }
    
         private void dfs(Digraph digraph, int v) {
            System.out.println("dfs("+v+")");
    
            pre.enqueue(v);
            marked[v]=true;
            for (int w: digraph.adj(v)){
                if (!marked[w]){
                    dfs(digraph,w);
                }
            }
            System.out.println(v+"完成");
    
            post.enqueue(v);
            reversePost.push(v);
        }
    
        public Iterable<Integer>pre(){
            return pre;
        }
    
        public Queue<Integer>post(){
            return post;
        }
        public Iterable<Integer>reversePost(){
            return reversePost;
        }
    }
    
    

    我们先测试一下一张有向无环图的各个排序的顺序:

    public static void main(String[] args) {
            Digraph digraph = new Digraph(13);
            digraph.addEdge(0,5);
            digraph.addEdge(0,1);
            digraph.addEdge(0,6);
            digraph.addEdge(2,0);
            digraph.addEdge(2,3);
            digraph.addEdge(3,5);
            digraph.addEdge(5,4);
            digraph.addEdge(6,4);
            digraph.addEdge(6,9);
            digraph.addEdge(7,6);
            digraph.addEdge(8,7);
            digraph.addEdge(9,10);
            digraph.addEdge(9,11);
            digraph.addEdge(9,12);
            digraph.addEdge(11,12);
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
            Stack<Integer> reversePost = depthFirstOrder.reversePost;
    
    
        }
    

    调用结果及形成的队列如下:
    边的构造顺序不一样,得到的拓扑排序也会不一样,但是结果一定是满足拓扑排序优先级限制的。

    			  pre     			   post				 			reversePost
    dfs(0)  	  0
      dfs(6)	  0 6
        dfs(9)    0 6 9
    	  dfs(12) 0 6 9 12 
    	  12完成 						12							 12
    	  dfs(11) 0 6 9 12 11
    	  11完成						12 11						 11 12
    	  dfs(10)0 6 9 12 11 10			    					
    	  10完成						12 11 10    		 		 10 11 12
    	9完成							12 11 10 9					 9 10 11 12
        dfs(4)	0 6 9 12 11 10 4			
    	4完成							12 11 10 9 4            	 4 9 10 11 12
      6完成								12 11 10 9 4 6 				 6 4 9 10 11 12
    dfs(1)		0 6 9 12 11 10 4 1	
    1完成								12 11 10 9 4 6 1 			 1 6 4 9 10 11 12
    dfs(5)		0 6 9 12 11 10 4 1 5
    5完成								12,11,10,9,4,6,1,5 			 5 1 6 4 9 10 11 12
    0完成								12,11,10,9,4,6,1,5,0    	 0,5,1,6,4,9,10,11,12
    dfs(2)	   0,6,9,12,11,10,4,1,5,2		
     dfs(3)    0,6,9,12,11,10,4,1,5,2,3
     3完成								12,11,10,9,4,6,1,5,0,3  	 3,0,5,1,6,4,9,10,11,12
    2完成								12,11,10,9,4,6,1,5,0,3,2     2,3,0,5,1,6,4,9,10,11,12
    dfs(7)     0,6,9,12,11,10,4,1,5,2,3,7
    7完成   							12,11,10,9,4,6,1,5,0,3,2,7   7,2,3,0,5,1,6,4,9,10,11,12
    dfs(8)
    8完成								12,11,10,9,4,6,1,5,0,3,2,7,8   8,7,2,3,0,5,1,6,4,9,10,11,12
    

    我们发现其逆后序就是我们要的拓扑排序,那么为什么逆后序就是拓扑排序呢?

    对于任意边v->w,调用dfs(v)时,一定会出现以下三种情况之一:
    1.dfs(w)已调用过,且已经结束(w被标记过了)
    2.dfs(w)未被调用(w没被标记),因此dfs(v)时会调用dfs(w),且dfs(w)会在dfs(v)之前返回
    3.dfs(w)被调用过了,且没有返回。这个就是有有向环时会出现的情况,但进行拓扑排序的前提的没有有向环,因为该情况不会出现。
    因此 情况1和2都是w在v之前结束调用,则w在后序排序中,一定在v之前,相反,在逆后序中,w一定在v之后,因此对于任意v->w都是排名较前点指向排名较后的点。

    这样我们就可以得到拓扑排序的实现:

    public class TopologicalSort {
        //顶点的拓扑排序
        private Iterable<Integer>order;
    
        public TopologicalSort(Digraph digraph) {
            DirectedCycle directedCycle=new DirectedCycle(digraph);
            //排序前进行有向环检测,没有环才可以进行拓扑排序
            if (!directedCycle.hasCycle()){
                //返回拓扑排序
                DepthFirstOrder dfs=new DepthFirstOrder(digraph);
                order=dfs.reversePost();
            }
    
        }
    
    
        public Iterable<Integer>order(){
            return order;
        }
        public boolean hasOrder(){
            return order!=null;
        }
    }
    

    四、有向图的强连通性

    定义:
    如果两个顶点是互相可达的,则称是强连通的。如果一个有向图的任意两个顶点都是强连通的,则该有向图是强连通的。
    有向图的极大强连通子图,称为强连通分量(strongly connected components)。
    如下:每个颜色代表一个强联通分量。
    在这里插入图片描述
    计算强连通分量的最常用的方法是Kosaraju算法:
    其思想是:
    1.使用DFS查找给定有向图G的反向图G^R
    2.根据反向图G^R求得其逆后序列
    3.对2求得的逆后序进行DFS遍历,访问未被标记的点
    4.在构造函数中,所有在同一个dfs调用中被访问的顶点都在同一个强连通分量中,按无向图中求连通分量的方法求强连通分量。

    有关该思想的证明如下:
    我们只要证明以下两个问题即可:
    (树上的证明猛一看可能看的不太懂,下面用自己的理解讲的细一点)
    1.每个和s强连通的顶点v都会在构造函数调用的dfs(G,s)中被访问到
    2.构造函数调用的dfs(G,s)所到达的任意顶点v都必然是和s强连通的。

    对命题1,我们使用反证法:
    1.假设一个和s强连通的顶点v在dfs(G,s)的调用中没有被访问到
    2.由于存在一条从s->v的路径,所以如果顶点v没有在dfs(G,s)中被访问,就一定在之前调用了dfs(G,v),并且访问到了v。
    3.又因为s和v是强连通的,所以也存在v->s的路径,在dfs(G,v)中,s一定会被标记,而s被标记,就一定不会再次进行dfs(G,s)的调用,矛盾,因此命题1成立。

    对命题2:
    1.要证明s和任意顶点v强连通,只要证明s->v且v->s,因为v是dfs(G,s)调用中访问到的任意顶点,所以一定存在s->v,接下来只要证明存在v->s即可。
    2.要证明存在v->s,就相当于证明反向图中存在s1->v1
    如下:
    在这里插入图片描述
    因为我们是按照逆后序进行深度优先遍历的,按照逆序,我们是在dfs(G,s)的调用中调用dfs(G,v),即先访问s再访问v,所以在反向图GR中,我们就应该是先访问v再访问s,对应上图GR中的点就是,先访问s1再访问v1。
    即只要证明dfs(G,v1)在dfs(G,s1)之前结束,则这样就有如下两个情况:

    1. dfs(G,v1)在调用dfs(G,s1)之前,且在dfs(G,s1)的调用开始前结束。
    2. dfs(G,v1)在调用dfs(G,s1)之后,且在dfs(G,s1)的调用结束前结束。

    如果出现情况1,这显然不可能,因为如果v1在s1之前就结束了,那么得出的逆后序应该是s1,v1,对应G中的v和s,先调用v再调用s,但是显然G是先调用s再调用v,所以该情况不存在。
    如果是情况2,则说明存在一条路径s1>v1,即原图G中存在一条路径v->s,命题2正确。

    下面是Kosaraju算法的实现:

    /**
     * 计算强连通分量的Kosaraju算法
     * @author MaoLin Wang
     * @date 2020/2/2216:54
     */
    public class KosarajuSCC {
        private boolean[] marked;
        /**
         * 强连通分量的标识符
         */
        private int[] id;
        /**
         * 强连通分量个数
         */
        private int count;
    
        public KosarajuSCC(Digraph digraph){
            marked=new boolean[digraph.V()];
            id=new int[digraph.V()];
            //求反向图的逆后序
            DepthFirstOrder order=new DepthFirstOrder(digraph.reverse());
            //对逆后序进行dfs遍历
            for(int s: order.reversePost()){
                if (!marked[s]){
                    dfs(digraph,s);
                    count++;
                }
            }
        }
    
        private void dfs(Digraph digraph, int v) {
            marked[v]=true;
            //顶点v属于第count个强连通分量
            id[v]=count;
            for (int w: digraph.adj(v)){
                if (!marked[w]){
                    dfs(digraph,w);
                }
            }
        }
        /*v和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;
        }
    }
    
    
    展开全文
  • 圈复杂度和强连通图

    2015-09-14 20:35:18
    今天上课老师让我们查一查路径测试的圈复杂度和强连通图是什么?  我就在网上查了一下圈的复杂度是:一种代码复杂度的衡量标准,在软件测试概念里圈复杂度用来衡量一个模块判定结构的杂度数量上表现为独立现行路径...

    今天上课老师让我们查一查路径测试的圈复杂度和强连通图是什么?

          我就在网上查了一下圈的复杂度是:一种代码复杂度的衡量标准,在软件测试概念里圈复杂度用来衡量一个模块判定结构的杂度数量上表现为独立现行路径数,即合理的预防错误所需测试的最少路径数,圈复杂度大说明代码可能质量低且难于测试和维护,根据经验,程序的可能错误和高的圈复杂度有很大的关系。

          圈复杂度的计算方法有三点:1)线数-节点数+2  2)判定节点数+1  3)控制流程图中的区域数

          强连通图:是指一个有向图中任意两点V1、V2之间存在V1到V2的路径及V2到V1的路径的图


    展开全文

空空如也

空空如也

1 2 3 4 5
收藏数 82
精华内容 32
关键字:

连通图和强连通图