精华内容
下载资源
问答
  • 有向图和无向图

    万次阅读 多人点赞 2019-04-13 18:51:19
    有向图、无向图 有向图和无向图是我们常用到的术语,本文属于简单的科普帖。 全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为无向图(Directed Graph)。有向,顾名思义,有方向。本文...

    有向图、无向图

    有向图和无向图是我们常用到的术语,本文属于简单的科普帖。

    全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为有向图(Directed Graph)。有向,顾名思义,有方向。本文中顶点Vertex(V),边Edge(E)

    (1)出度和入度:如图D,以点A为例子,在所有与A关联的边中,以A为起点的边的条数称为出度。而入度则刚好相反,以A为终点的边的条数则称为入读。其中,入度+出度,我们称为A的度。注意特殊情况:如图:A有一个自环,起点和终点都是自己,此时出度算一度,入度也算一度。如图:A的出度为3,入度也为2,A的度的5。

    在这里插入图片描述
    (2)描述图的邻接矩阵和关联矩阵
    【邻接矩阵】

    定义:
    设无向图G=(V,E),其中顶点集V=v1,v2,…,vn,边集 E=e1,e2,…,eε。用aij表示顶点vi与顶点vj之间的边数,可能取值为0,1,2,…,称所得矩阵A=A(G)=(aij)n×n为图G的邻接矩阵。邻接矩阵可以描述有向图和无向图。

    示例,求图所示简单图的邻接矩阵?
    在这里插入图片描述
    解:根据定义,可求得该无向图的邻接矩阵为
    在这里插入图片描述

    邻接矩阵的存储特点:
    (a)无向图的邻接矩阵一定是一个对称矩阵,有向图不一定是。
    *(b)邻接矩阵所需的存储空间值域只与顶点数有关系。
    (c)用邻接矩阵存储图,容易判断两个点之间是否有边。
    (d)如果一个有向图的邻接矩阵为三角矩阵(主对角线为0),则它的拓扑排序一定存在。
    *(e)小技巧:
    无向图:邻接矩阵的第i行或者第i列的非零元素的个数正好是第i个顶点Vi的度;
    有向图:邻接矩阵的第i行的非零元素个数正好是第i个顶点Vi的出度,第i列非零元素的个数正好是第i个顶点Vi的入度。

    【关联矩阵】

    定义:
    设任意图G=(V,E),其中顶点集V=v1,v2,…,vn,边集E=e1,e2,…,eε。用mij表示顶点vi与边ej关联的关系,可能取值为0,1,-1,称所得矩阵M(G)=(mij)n×ε为图G的关联矩阵。
    在这里插入图片描述
    mij 表示i行j列,探究顶点Vi和边Ej之间的关系,形成下列的关联矩阵
    示例:
    在这里插入图片描述
    关联矩阵
    在这里插入图片描述

    连通图、连通分量

    连通图:无向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为连通图。
    连通分量:无向图中极大连通子图称为连通分量。

    强连通图、强连通分量

    强连通图:有向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为强连通图。
    连通分量:无向图中极大连通子图称为强连通分量。特:强连通图只有强连通分量(本身),非强连通图有多个强连通分量。

    另外,本文参考路了下面两位作者的优秀博客
    https://blog.csdn.net/Hanging_Gardens/article/details/55670356
    https://blog.csdn.net/legendaryhaha/article/details/83049101

    展开全文
  • 有向图和无向图的相关概念

    千次阅读 2020-04-29 15:44:42
    图的定义:  图在数据结构中是中一对多的关系,一般分为无向图与无向图  常用 邻接矩阵 或者 邻接链表 来...对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为:  G1=(V1,E1), 其中 V1={a,b,c,d...

    图的定义:

      图在数据结构中是中一对多的关系,一般分为无向图与无向图

      常用 邻接矩阵 或者 邻接链表 来表示图中结点的关系

      ⑴图是由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构
      ⑵用二元组定义为:G=(V,E)。

    例如:

    对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为:

          G1=(V1,E1), 其中 V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},
                     G2=(V2,E2),其中 V2={1,2,3}, E2={<1,2>,<1,3>,<2,3>,<3,1>}。

    有向图与无向图

        ⑴在图中,若用箭头标明了边是有方向性的,则称这样的图为有向图,否则称为无向图。

        如图7-1中:
             ①G1为无向图,   ②G2 为有向图。
        ⑵在无向图中:一条边(x,y)与(y,x)表示的结果相同,用圆括号表示,
        ⑶在有向图中:一条边<x,y>与<y,x>表示的结果不相同,故用尖括号表示。<x,y>表示从顶点x发向顶点y的边,x为始点,y为终点。
        ⑷有向边也称为弧,x为弧尾,y为弧头,则<x,y>表示为一条弧, 而<y,x>表示y为弧尾,x为弧头的另一条弧 。

     

    完全图/稠密图/稀疏图:

      ⑴具有n个顶点,n(n-1)/2条边的图,称为完全无向图,
      ⑵具有n个顶点,n(n-1) 条弧的有向图,称为完全有向图。
      ⑶完全无向图和完全有向图都称为完全图。
      ⑷对于一般无向图,顶点数为n,边数为e,则 0≤e  ≤n(n-1)/2。
      ⑸对于一般有向图,顶点数为n,弧数为e, 则 0≤e≤n(n-1)  。
      ⑹当一个图接近完全图时,则称它为稠密图,
      ⑺当一个图中含有较少的边或弧时,则称它为稀疏图。

    度/出度/入度:

      ⑴在图中,一个顶点依附的边或弧的数目,称为该顶点的度。

      ⑵在有向图中,一个顶点依附的弧头数目,称为该顶点的入度。

      ⑶一个顶点依附的弧尾数目,称为该顶点的出度,某个顶点的入度和出度之和称为该顶点的度。

      ⑷若图中有n个顶点,e条边或弧,第i个顶点的度为di,则有  e=1/2 * Σ(1<= i <= n,   di)

    子图

    ⑴若有两个图G1和G2, G1=(V1,E1), G2=(V2,E2), 满足如下条件:
        V2⊆V1  ,E2⊆ E1,即V2为V1的子集,E2为E1的子集,则 称图G2为图G1的子图。

    权:
    ⑴在图的边或弧中给出相关的数,称为权。
    ⑵权可以代表一个顶点到另一个顶点的距离,耗费
       等,带权图一般称为网。

    一个图由多个结点以及边组成。

    无向图例子:

      

      有向图例子:

      

    从上述例子中可以看出,一个图表是由数个顶点和边组成的。

      其中,无向图的边是没方向的,即两个相连的顶点可以互相抵达。

      而有向图的边是有方向的,即两个相连的顶点,根据边的方向,只能由一个顶点通向另一个顶点。(当然,如有向图例子中的2和3,由于有两个指向对方的方向,所以2和3是互通的。)

    完全图

    连通图:如果一个无向图从每一个顶点到其他顶点都存在一条路径,则称该无向图为连通图

    强连通图:具有这样的性质的有向图称为是强连通的,如果不是强连通的,

    弱连通图:它的基础图,即去掉弧上的方向所形成的的图,是连通的,那么该有向图称为弱连通的

    完全无向图:具有n个顶点,并具有n(n - 1)/2 条边的图,称为完全无向图(每个顶点到其他顶点都有边),连通图

    完全有向图:具有n个顶点,并且具有n(n - 1) 条边的有向图,称为完全有向图(每个顶点到其他顶点都有相互两条边),强连通图

    完全图:完全无向图和完全有向图都称为完全图

    邻接矩阵

    定义:
    设无向图G=(V,E)G=(V,E),其中顶点集V=v0,v1,v2,...,vnV=v1,v2,...,边集E=e0,e1,e2,...,eεE=e1,e2,...,eε。用aijaij表示顶点vivi与顶点vjvj之间的边数,可能取值为0,1,2,…,称所得矩阵A=A(G)=(aij)n×nA=A(G)=(aij)n×n为图G的邻接矩阵

    性质:

    类似地,有向图D的邻接矩阵A(D)=(aij)n×nA(D)=(aij)n×n, aijaij表示从始点vivi到终点vjvj的有向边的条数,其中vivi和vjvj为D的顶点

    示例,求图所示简单图的邻接矩阵?

    解:根据定义,可求得该无向图的邻接矩阵为

    注:邻接矩阵是描述图的一种常用的矩阵表示。

     

    关联矩阵

    定义:
    设任意图G=(V,E)G=(V,E),其中顶点集V=v1,v2,...,vnV=v1,v2,...,vn,边集E=e1,e2,...,eεE=e1,e2,...,eε。用mijmij表示顶点vivi与边ejej关联的次数,可能取值为0,1,2,…,称所得矩阵M(G)=(mij)n×εM(G)=(mij)n×ε为图G的关联矩阵

    类似地,有向图DD的关联矩阵M(D)=(mij)n×εM(D)=(mij)n×ε的元素mi×jmi×j定义为:

    示例,求图中有向图的邻接矩阵和关联矩阵

    解:根据定义,可求得该有向图的邻接矩阵:

    关联矩阵:

    注:关联矩阵是描述图的另一种矩阵表示。

    参考地址:

    https://blog.csdn.net/Hanging_Gardens/article/details/55670356

    https://blog.csdn.net/legendaryhaha/article/details/83049101

    https://www.cnblogs.com/schips/p/10632250.html

    展开全文
  • 有向图和无向图以及拓扑的复习

    万次阅读 2018-10-14 17:43:36
    1)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。 理解:如图D,...

    备注:大一学了图后,一段时间没用就还给老师了,如今重新复习一下,理解有误的地方请指教。


    有向图和无向图的定义

    1)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。
    理解:如图D,如果e是D的一条边,而这时候存在这样的一个关系,ψD,有A,B两点,使得,ψD(A,B)=e(到底是怎样的关系?我觉得在应用中,需要我们自己制定,就像在预算100元的条件下,你选择怎样的交通工具快速到达目的地),通俗理解:边有方向的图。即AB != BA。
    [外链图片转存失败(img-OHZsll7R-1567908307459)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483515239_C07BA5588B40E754EB534225BA630A0D “图片标题”)]


    (2)平行边:在图中,如果起点和终点相同则称为平行边,平行边的条数则称为重数。如图:e2和e3为平行边,B和C之间的重数为2。
    [外链图片转存失败(img-EMKaEUe6-1567908307460)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483671400_6DA66AE52EFE0CF2370DF02226877263 “图片标题”)]


    (3)关于无向图:了解了有向图,那它就好理解了,就是有向图中去掉所有的方向,AB=BA,如图,就是去掉D中的所有箭头(此时,又称为基础图,反之给无向图添上箭头的有向图又称为定向图)。
    [外链图片转存失败(img-DJM75Udh-1567908307461)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483731056_5FB56EBF13116F56F22CCFD0F068F03B “图片标题”)]


    (4)出度和入度:如图D,以点A为例子,在所有与A关联的边中,以A为起点的边的条数称为出度。而入度则刚好相反,以A为终点的边的条数则称为入读。其中,入度+出度,我们称为A的度。注意特殊情况:如图:A有一个自环,起点和终点都是自己,此时出度算一度,入度也算一度。如图:A的出度为3,入度也为2,A的度的5。


    (5)邻接矩阵和关联矩阵定义:设D(V,E)是有向图,其中V={v1,v2,v2…vn},E={e1,e2,e3,…em}称A(D)=(aij)nxn是D的领接矩阵,其中aij是以vi为起始点,以vj为终点的边的条数。若图D中无环,则称M(D)=(mij)nxm为关联矩阵。[i,j是下标,n是点的个数,m是边的数量注意:1.关联矩阵是针对边来说的,所以矩阵大小为n*m,它的取值如下:

    图片来源于百科
    例子:
    图片来源于百科
    (6)补充:对于无向图而言:邻接矩阵则是对称的,且只有0和1,因为没有方向的区别后,要么有边,要么没边:
    在这里插入图片描述
    从图我们可以看到,它是关于对角线对称的一个矩阵,我们在编程中,遍历和存储是只需要关注上半部分或者下半部分即可。
    在这里插入图片描述


    (7)跟邻接矩阵一样,用来存储图中信息的,还有邻接表:如果学过链表了,就很好理解了,首先在一个数组中存储各个点(对象或者成为链),而每个对象又保存着一个next引用指向连接的点在数组中的坐标,如图:A到E在数组中存储后,坐标依次排列,A连B,B的坐标为1,所以指向的地方标记为1,代表A连着B,接着,B连着E,E的坐标为4,这1的引用指向4。

    从图我们就可以得出邻接表的存储方式了:即链表加数组,这存储结构比起纯粹用数组(邻接矩阵)要节约很多空间。邻接矩阵,我们需要一个n*n维的数组,复杂度为O(n^2),而邻接表是根据点和边来保存数据的,当一个起点决定后,就采用深度搜索的方法沿着边,保存连接点的信息,复杂度为O(n+m)

    另外,若果是有向图,我们在保存下一个顶点时,还需要保存边的权值,看图中每个格子都分成两小格了吗,第二个小格子就是用来存储权值的。

    图来自百度词条,好难画
    在这里插入图片描述


    拓扑排序

    百度词条这样描述:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
    理解:(1)根据定义,我们可以知道它是针对有向图而言的.(2)它是一个包含有向图的所有点的线性序列,且满足两个条件:a.有向图的每个顶点只出现一次。b.若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 应该出现在顶点 B 的前面。

    备注:图来源于百度,之前都没发现,它的786,应该是678,C0是连着C2和C6的
    [外链图片转存失败(img-q5yfBWrf-1567908307464)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539485618410_F203E6F40B767104E9635E84C103CA7C “图片来源于百科”)]

    (2)注意,拓扑排序并不是唯一的,它的排序方式:以上图为例子:a.首先我们从有向图图中选择一个没有前驱(即入度为0)的顶点并输出,这里我们可以选择c0或者c1。b.从图中删除输出的顶点和所有以它为起点的有向边。c.循环 a步骤 和 b步骤,终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注:若当前图中不存在无前驱的顶点,说明有向图中必然存在环。


    展开全文
  • 【图结构专题】有向图

    万次阅读 2018-03-19 22:00:26
    有向图 一. 有向图的相关术语 在有向图中,边是单向的:每条边连接的两个顶点都是一个有序对,它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图:比如任务調度的依赖关系,社交网络的任务关系等等...

    一. 有向图的相关术语

    在有向图中,边是单向的:每条边连接的两个顶点都是一个有序对,它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图:比如任务調度的依赖关系,社交网络的任务关系等等都是天然的有向图。

    以下概念都是针对有向图的:

    (1)有向图:一幅有向图是由一组顶点和一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点。

    (2)顶点的出度:该顶点指出的边的总数。

    (3)顶点的入度:指向该顶点的边的总数。

    (4)比如对于有序对(w,v) 一般代表w->v 的一条有向边。

    (5)有向路径:由一系列顶点组成,其中每个顶点都存在一条有向边从它指向序列中的下一个顶点。

    (6)有向环:为一条至少含有一条边且起点和终点相同的有向路径。

    (7)简单有向环:是一条除了起点和终点外,不含有重复的顶点和边的环。

    二. 有向图的存储数据结构

    首先定义有向图的API接口,DiGraph 本质上和Graph是一样的。

    public class Digraph
    Digraph(int v)创建一幅含有v个顶点,但是没有边的有向图
    Digraph(In in)从输入流中读取一幅有向图
    int E()边的总数
    int V()边的总数
    void addEdge(int v, int w)添加一条有向边v ->w
    Iterble<Integer>adj(int v)由顶点v出发的有向边所连接的所有顶点
    Digraph reverse()该图的反向图
    String toString()对象的字符串表示形式

    1. 有向图的表示

    和无向图的表示类似,我们还是使用 邻接表 来存储有向图,其中边 v—>w 表示为顶点v所对应的邻接链表中包含一个w顶点。

    2. 有向图取反

    上面的API中给出了reverse() 方法,将有向图中的所有有向边反转,并生成副本。

    3. 有向图的实现

    使用邻接表来存储有向图,用数组来表示图中的每个节点的集合,并且数组的下标就表示节点的标识符。

    下面就是有向图的实现方式:

    package com.example.algorithm4.graphs;
    
    import edu.princeton.cs.algs4.Bag;
    
    /**
     * 有向图的实现
     * 
     * @author 惜暮
     * @email chris.lyt@alibaba-inc.com
     * @date 2017/12/7
     */
    public class DiGraph {
        /**
         * 节点的总个数
         */
        private final int V;
        /**
         * 边的总个数
         */
        private int E;
        /**
         * 有向图的邻接表表示法
         */
        private Bag<Integer>[] adj;
    
        /**
         * 创建一个含有V个节点,但是0条边的有向图
         * @param V
         */
        public DiGraph(int V) {
            this.V = V;
            this.E = 0;
            adj = (Bag<Integer>[])new Bag[V];
            for (int i=0; i<this.V; i++){
                adj[V] = new Bag<>();
            }
        }
    
    
        public int E(){
            return this.E;
        }
    
    
        public int V(){
            return this.V;
        }
    
        /**
         * 添加一条 v-->w 的边
         * @param v 有向边的源在数组中的标识符
         * @param w 有向边的终在数组中的标识符
         */
        public void addEgge(int v, int w){
            adj[v].add(w);
            this.E++;
        }
    
        /**
         * 节点v 的所有出度的终顶点
         * @param v 节点v 的标识符
         * @return
         */
        public Iterable<Integer> adj(int v){
            return adj[v];
        }
    
        /**
         * 此有向图反转之后的副本
         * @return
         */
        public DiGraph reverse(){
            DiGraph reverse = new DiGraph(this.V);
            for(int i=0 ;i<this.V; i++){
                for (int w : adj[i]){
                    //边反转
                    reverse.addEgge(w, i);
                }
            }
            return reverse;
        }
    }
    

    4. 符号有向图的实现

    有向图的邻接表表示和无向图的邻接表表示区别不大,仅仅在于边的处理上有一点区别。如果对于有向图的结点的标识我们也想用字符串来表示呢?其实现方法几乎和无向图一样,增加一个Map用来保存顶点的符号到数组下表的映射关系,然后用字符数组保存所有的符号,数组下标天然表示每个顶点的index。 代码实现上只需要把SymbolGraph中的Graph替换成DiGraph就可,下面也给出实现代码:

    package com.example.algorithm4.graphs;
    
    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.ST;
    
    /**
     * 符号有向图的实现
     * @author 惜暮
     * @email chris.lyt@alibaba-inc.com
     * @date 2017/12/7
     */
    public class SymbolDiGraph {
        private ST<String, Integer> st; // map,顶点符号名 -> 数组索引
        private String[] keys; // 数组索引 -> 顶点符号名
        private DiGraph G; // 图
    
        /**
         * 构造一颗符号有向图
         * @param stream 顶点边的数据源
         * @param sp 顶点分隔符
         */
        public SymbolDiGraph(String stream, String sp) {
            st = new ST<>();
            In in = new In(stream); // First pass
            while (in.hasNextLine()) {// builds the index
                String[] a = in.readLine().split(sp); // by reading strings
                for (int i = 0; i < a.length; i++) {// to associate each
                    if (!st.contains(a[i])) {// distinct string
                    	st.put(a[i], st.size()); // with an index.
                    }
                }
            }
            keys = new String[st.size()]; //建立索引 --> 结点符号
            for (String name : st.keys()) {// to get string keys
              	keys[st.get(name)] = name; // is an array.
            }
          
            // 创建符号图
            G = new DiGraph(st.size());
            in = new In(stream); // Second pass
            while (in.hasNextLine()) {// builds the graph
                String[] a = in.readLine().split(sp); // by connecting the
                int v = st.get(a[0]); // source vertex
                for (int i = 1; i < a.length; i++) {// on each line
                	G.addEdge(v, st.get(a[i])); // to all the others.
                }
            }
        }
    
      	public boolean contains(String s) {
          	return st.contains(s);
        }
    
      	public int index(String s) {
          	return st.get(s);
        }
    
    	public String name(int v) {
          	return keys[v];
        }
    
    	public DiGraph G() {
          	return G;
        }
    }
    

    三. 有向图中的可达性

    我们在无向图中介绍的第一个算法就是DFS,其实无向图是很多算法的基础,解决了单点连通性的问题,可以判断无向图中指定的两个顶点是否连通。其思想对于有向图同样适用~

    定义:有向图的单点可达性:给定一个有向图和一个起点s,判断是否存在一条从起点s到指定节点v的有向路径。

    针对以上问题,设计DirectedDFS 算法的API:

    public class DirectedDFS
    DirectedDFS(DiGraph G, int s)在G中找到从s可达的所有顶点
    DirectedDFS(DiGraph G, Iterable<Integer> sources)在G中找到从sources的所有顶点中可达的所有顶点
    boolean reachable(int v)d顶点v是可达的嘛

    1. 使用DFS实现有向图的可达性分析

    在有向图中,深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。

    下面是有向图的可达性算法的实现:

    package com.example.algorithm4.graphs;
    
    /**
     * 有向图的深度优先遍历
     *
     * @author 惜暮
     * @email chris.lyt@alibaba-inc.com
     * @date 2017/12/7
     */
    public class DirectedDFS {
        /**
         * 从起点s开始DFS访问过的路径标记
         */
        private boolean[] marked;
    
        public DirectedDFS(Digraph digraph, int s) {
            this.marked = new boolean[digraph.V()];
            dfs(digraph, s);
        }
    
        public DirectedDFS(Digraph digraph, Iterable<Integer> sources) {
            this.marked = new boolean[digraph.V()];
            for(int s : sources){
                if (!marked[s]){
                    dfs(digraph, s);
                }
            }
        }
    
        /**
         * 从节点v 开始有向图的DFS
         *
         * @param digraph 有向图
         * @param v 结点
         */
        private void dfs(Digraph digraph, int v){
            this.marked[v] = true;
            for (int w : digraph.adj(v)){
                if(!this.marked[w]){
                    dfs(digraph, w);
                }
            }
        }
    
        public boolean marked(int v){
            return marked[v];
        }
    }
    

    这份深度优先搜索能够实现判断一个或则一组(多点可达性)顶点能到达哪些其他顶点。

    2. 标记-清除的垃圾收集

    多点可达性的一个重要的实际应用是在典型的内存管理上,比如JVM内存管理,在一幅有向图中,一个顶点代表一个对象,一条边代表一个对象对另外一个对象的引用。 有向图的模型很好的可以应用在JVM内存管理上面。当从根节点遍历时候,那么不可达的顶点就代表不会再被使用,就可以被回收以释放内存。

    标记-清除的垃圾回收算法会为每个对象保存一个位作为垃圾回收之用,然后周期性的运行一个类似于DirectedDFS的有向图可达性算法来标记所有可以被访问到的对象,然后清理所有对象,回收没有被标记的对象,以达到释放内存的目的。

    3. 有向图的寻路

    DepthFirstPaths 和 BreadthFirstPaths 也都是有向图处理中的重要算法。可以用处理下面问题:

    • 单点有向路径:给定一个起点s,从s到给定目的顶点v是否存在一条有向路径。如果有就找出这条路径。
    • 单点最短有向路径:给定一个起点s,从s到给定目的顶点v是否存在一条有向路径。如果有就找出最短的路径。

    下图给出了一个使用深度优先遍历在一幅有向图中寻找能够从顶点0到达的所有顶点的轨迹的示意图:

    这里写图片描述

    四. 环和有向无环图(DFS和拓扑排序)

    在有向图的应用场景中对于有向环的检测十分重要,因为有向环就代表着死循环,然后实际的项目中由于依赖关系的复杂,几乎不可能肉眼检测有向环,所以检测有向环是否存在就至关重要。

    对于有向环的检测主要有两种方法:DSF和拓扑排序。下面以实际例子来分析

    1. 调度问题(拓扑排序)

    一个广泛使用的模型就是给定一组任务并安排它们的执行顺序,限制条件是这些任务的执行方法和起始时间。限制条件可能还包括任务的耗时以及消耗的其他资源。最重要的一种限制条件叫做优先级限制,它指明了哪些任务必须在哪些任务之前完成。 不同类型的限制条件会产生不同类型不同难度的调度问题

    下面以一个正在安排课程的大学生为例,有些课程是其余课程的先导课程:如图:

    这里写图片描述

    再假设该学生一次只能修一门课,问题就可以抽象成以下模型:

    优先级限制下的調度问题:给定一组需要完成的任务,以及一组关于任务完成的先后次序的优先级顺序。在满足条件下以最优方案完成任务。为了简化模型,以数字标识顶点,顶点代表任务。可以等价成下图:

    这里写图片描述

    拓扑排序:给定一幅有向图,将所有顶点排序,使得所有的有向边均从排在前面元素指向排在后面的元素。

    上面的实例的拓扑排序图如下:所有边都朝下,清晰描绘了这幅有向图模型代表的优先级限制下調度问题的解决方法:

    这里写图片描述

    拓扑排序有很多典型的应用,比如任务調度,继承等等。

    2. 有向环的检测方法一:DFS

    定义。有向无环图就是一幅不包含环的有向图。

    有向环的检测,我们可以借助于DFS算法,也可以借助拓扑排序。算法DirectedCycle 实现了环的检测,API如下:

    public class DirectedCycle
    DirectedCycle(Digraph digraph)寻找有向环的构造函数
    boolean hasCycle()digraph是否有环
    Iterable<Integer> cycle()有向环中的所有顶点

    下图是一个在有向环中寻找环的过程示意图:

    这里写图片描述

    算法实现如下:

    package com.example.algorithm4.graphs;
    
    import java.util.Stack;
    
    /**
     * 有向图环的检测:DFS算法
     *
     * @author 惜暮
     * @email chris.lyt@alibaba-inc.com
     * @date 2017/12/7
     */
    public class DirectedCycle {
        /**
         * 从起点开始DFS访问过的路径标记
         */
        private boolean[] marked;
        /**
         * 从起点到一个顶点v的已知路径上的最后一个顶点
         */
        private int[] edgeTo;
        /**
         * 如果存在有向环,就保存有向环中的所有顶点。
         */
        private Stack<Integer> cycle;
        /**
         * 递归调用栈上的所有顶点
         * 这里类似于Java里面的一个set,里面保存了所有已经访问过的顶点
         */
        private boolean[] onStack;
    
        /**
         * 构造器
         *
         * @param digraph 有向图
         */
        public DirectedCycle(Digraph digraph) {
            this.marked = new boolean[digraph.V()];
            this.edgeTo = new int[digraph.V()];
            this.onStack = new boolean[digraph.V()];
            for (int v=0; v<digraph.V(); v++) {
                if( !marked[v] ) {
                    dfs(digraph, v);
                }
            }
        }
    
        /**
         * 从节点v 开始有向图的DFS
         *
         * @param digraph 有向图
         * @param v 结点
         */
        private void dfs(Digraph digraph, int v){
            // 标记当前结点在堆栈路径上
            this.onStack[v] = true;
            this.marked[v] = true;
            for (int w : digraph.adj(v)){
                // 如果当前图已经有环就直接返回
                if (this.hasCycle(w)){
                    return;
                } else if(!this.marked[w]){
                    // 如果当前结点没有被标记过,递归dfs
                    edgeTo[w] = v;
                    dfs(digraph, w);
                } else if (onStack[w]){
                    // (1)当前结点被标记过来了,(2)而且在已经访问过得堆栈上,则存在环
                    cycle = new Stack<>();
                    for(int x = v; x!=w; x = this.edgeTo[x]) {
                        cycle.push(x);
                    }
                    cycle.push(w);
                    cycle.push(v);
                }
            }
            // 递归回溯时,当前结点重置为不在环的堆栈上。
            this.onStack[v] = false;
        }
    
        public boolean hasCycle(int v){
            return cycle!=null;
        }
    
        public Iterable<Integer> cycle(){
            return cycle;
        }
    }
    

    上面检测有向图是否有环的算法采用标准的递归dfs算法,添加了一个布尔型数组onStack[] 来保存递归调用期间栈上面的所有顶点。当找到一条边 v->w 且w在栈中时,就代表找到了有向环。环上所有顶点都可以通过edgeTo[]数组得到。

    3. 顶点的深度优先次序与拓扑结构

    在优先级限制下的調度问题等价于计算有向无环图中的所有顶点的拓扑排序,因此给出如下API:

    public class Topological
    Topological(Digraph digraph)拓扑排序的构造函数
    boolean isDAG()图digraph是有向无环图嘛?
    Iterable<Integer> order()拓扑排序的所有顶点

    定理:当且仅当一幅图是有向无环图时才能进行拓扑排序。也就是有向无环图才有拓扑排序。

    首先我们先来看看 有向图中基于深度优先搜索的顶点排序 的DepthFirstOrder算法。

    其基本思想是:深度优先搜索正好只会访问每个顶点一次,如果将dfs()的参数顶点保存在一个数据结构中,遍历这个数据结构实际上就能访问图中的所有顶点,遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是调用之后进行保存。在应用中我们关注的是以下3种排列顺序:

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

    下图是用DepthFirstOrder 算法处理有序无环图产生的轨迹。实现简单,支持处理图的高级算法中十分有用的pre()、post()和reversePost()方法。 例如Topological类中order()方法就调用了reversePost()方法。

    这里写图片描述

    算法实现如下:

    package com.example.algorithm4.graphs;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 有向图中基于深度优先搜索的顶点排序
     *
     * @author 惜暮
     * @email chris.lyt@alibaba-inc.com
     * @date 2017/12/7
     */
    public class DepthFirstOrder {
        /**
         * 从起点开始DFS访问过的路径标记
         */
        private boolean[] marked;
        /**
         * 所有顶点的前序排列
         */
        private Queue<Integer> pre;
        /**
         * 所有顶点的后序排列
         */
        private Queue<Integer> post;
        /**
         * 所有顶点的逆后序排列
         */
        private Stack<Integer> reversePost;
    
        public DepthFirstOrder(Digraph digraph) {
            marked = new boolean[digraph.V()];
            pre = new LinkedList<>();
            post = new LinkedList<>();
            reversePost = new Stack<>();
    
            for (int v=0; v<digraph.V(); v++){
                if ( !marked[v] ) {
                    dfs(digraph, v);
                }
            }
        }
    
        /**
         * 从节点v 开始有向图的DFS
         *
         * @param digraph 有向图
         * @param v 结点
         */
        private void dfs(Digraph digraph, int v){
            pre.add(v);
            this.marked[v] = true;
            for (int w : digraph.adj(v)){
                if(!this.marked[w]){
                    dfs(digraph, w);
                }
            }
            post.add(v);
            reversePost.push(v);
        }
    
        public Iterable<Integer> pre(){
            return pre;
        }
    
        public Iterable<Integer> post(){
            return post;
        }
    
        public Iterable<Integer> reversePost(){
            return reversePost;
        }
    }
    

    该类允许使用各种顺序遍历DFS经过的顶点。这在高级的有向图处理算法中非常有用,因为搜索的递归性是的我们能够证明这段计算的许多性质。

    下面给出拓扑排序==Topological==的实现算法:

    package com.example.algorithm4.graphs;
    
    /**
     * 有向无环图的 拓扑排序
     *
     * @author 惜暮
     * @email chris.lyt@alibaba-inc.com
     * @date 2017/12/7
     */
    public class Topological {
        /**
         * 顶点的拓扑排序
         */
        private Iterable<Integer> order;
    
        public Topological(Digraph digraph){
            DirectedCycle cycleFinder = new DirectedCycle(digraph);
            if( !cycleFinder.hasCycle() ) {
                DepthFirstOrder dfs = new DepthFirstOrder(digraph);
                order = dfs.reversePost();
            }
        }
    
        public Iterable<Integer> order() {
            return order;
        }
    
        public boolean isDAG(){
            return order!=null;
        }
    }
    

    Topological的实现借助了DirectedCycle 检测环是否存在,借助DepthFirstOrder的逆后续来获取拓扑排序。

    定理:一幅有向无环图的拓扑排序就是所有顶点的逆后续排列。

    证明:

    在任意一条边v->w, 在调用dfs(v) 时,下面三种情况,必有一种成立:

    (1)dfs(w) 已经被调用过了,且已经返回了。 (w节点已经被标记true了)

    (2)dfs(w)还没有被调用(w还没被标记), 因此v->w 会直接或则间接调用并返回dfs(w),且dfs(w)会在dfs(v)之前返回。

    (3)dfs(w)已经被调用但还没返回。证明的关键在于,在DAG中,这种情况是不可能出现的。由于递归调用链的特性意味着存在从w到v的路径,但又存在v->w的边,所以存在一个环。

    在上面(1)(2)两种情况中dfs(w) 会在dfs(v)之前完成,也就是后续排列中w排在v之前。 所以在逆后序中w排在v之后,因此任意一条边v->w 都如我们所愿地从排名比较靠前的顶点指向排名靠后的顶点。

    定理:使用深度优先算法对有向无环图进行拓扑排序所需要时间和 (V+E) 成正比。

    证明:从DirectedCycle和DepthFirstOrder的实现可知,两次搜索都访问了所有顶点和边,所以时间和(V+E)成正比。

    下面给出了一个示例 DAG 的逆后续是拓扑排序的轨迹图:

    这里写图片描述

    五. 有向图中的强连通性

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

    1. 强连通分量

    有向图的强连通性也是一种顶点之间的平等关系,因为其有着如下性质:

    • 自反性:任意顶点v和自己都是强连通的。
    • 对称性:如果v和w是强连通的, 那么w和v也是强连通的。
    • 传递性:如果v和w是强连通的且w和x也是强连通的 ,那么v和x也是强连通的。

    强连通分量就是:有向图的极大强连通子图

    2.强连通分量应用

    最典型应用就是网络,以顶点代表网页,超链接代表边。 下面给强连通分量的API:

    public class SCC
    SCC(Digraph digraph)预处理构造函数
    boolean stronglyConnected(int v, int w)v和w是强连通的吗?
    int count()图中强连通分量的总数
    int id(int v)v所在强连通分量的标识符(0至count()-1 之间)

    3. 计算强连通分量的Kosaraju算法(无)

    4. 再谈可达性(无)

    六. 总结(无)

    展开全文
  • 有向图的深度和广度遍历

    万次阅读 2018-05-04 09:33:26
    对于下图所示的有向图(访问顺序按序号从小到大),试写出: (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树;(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树。 package com.test.tree; ...
  • 有向图及拓扑排序

    万次阅读 2018-10-20 23:06:53
    有向图 在无向图中,边没有方向,两条边之间的顶点是单向可达的,而有向图的边是单向的。虽然边的性质不同,但我们仍然可以用邻接表来表示有向图。对有向图的结构定义如下: #include <map> #include <...
  • 两种方式判断有向图是否有环-python实现 1. DFS判断有向图是否有环 假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后...
  • 图论基础知识(四) —— 有向图

    千次阅读 2019-03-01 15:51:52
      由定义可见,有向图和无向图的区别仅仅在于有向图的弧集是有序对的多重集,而无向图的边集是无序顶点对的多重集,无向图的一切概念均可平移到有向图。 定义2:入度、出度 设D是一个有向图,D...
  • 有向图的相关概念和结论 强连通分支和单项连通分支的求法 一、有向图概念和性质 概念:边有方向的图称为有向图 出度:以点v为始点的边的条数称为点v的出度,一个自环算一度 入度:以点v为终点的边的条数称为...
  • 有向图的连通性

    千次阅读 多人点赞 2020-04-21 16:17:47
    文章目录 无向图: ...单向连通:有向图中,任意结点对中,至少从一个到另一个是可达的,就是单向连通。 强连通:有向图中,强连通图是任意对中都互相可达。 PS:弱连通图不一定是单向连通。 ...
  • 图2——利用邻接表创建有向图

    千次阅读 多人点赞 2019-04-05 19:42:58
    图2——利用邻接表创建有向图 图 假设以邻接表作为图的存储结构,编写算法,创建有向图并输出邻接表。 主要考查对邻接表的理解。图的邻接表分为两个部分:表头结点和边表结点,因此创建有向图也分成两部分:一是...
  • 邻接表有向图

    万次阅读 2018-08-14 22:47:20
    邻接表有向图的介绍 邻接表有向图是指通过邻接表表示的有向图。 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"&lt;A,B&gt;,&lt;B,C&gt;,&lt;B,E&gt;,&lt;...
  • 有向图的连通分量的求解思路 kosaraju算法 逛了很多博客,感觉都很难懂,终于找到一篇能看懂的,摘要记录一下 原博客https://www.cnblogs.com/nullzx/p/6437926.html 关于连通分量是什么自行百度,这里主要...
  • 网上查了很多资料,发现主要是使用邻接表来实现图,并进行遍历的。而采用邻接矩阵的就非常少...不想看的可以直接下载:python 邻接矩阵三种方法实现有向图、无向图,并绘图显示不废话。上代码首先图类 class Graph_Matr
  • 图5——判断有向图中是否存在回路

    万次阅读 多人点赞 2019-06-22 09:32:13
    假设以邻接矩阵作为图的结构,编写算法,判别在给定的有向图中是否存在一个简单的有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)(注意:图中不存在顶点到自身的弧) 这是清华大学的考研试题。...
  • 【0】README0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——遍历有向图+判断有向图是否有圈” 的idea 并用源代码加以实现 ; 0.2) 判断有向图是否有圈的rule—— 一个有向图是无...
  • 如何求有向图的拓补序列

    万次阅读 多人点赞 2018-09-12 11:11:15
    求一个有向图的拓扑序列也是图论的基本题型。但是一般不会显式的看出题意是求拓扑序列或者求是否存在拓扑序列。拓扑序列一般用来判断一个图是否是一个有向无环图,如果一个图存在符合拓扑次序的序列则该图是有向无环...
  • 此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。解法一:深度遍历假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个...
  • 有向图与无向图判断有环

    万次阅读 多人点赞 2015-11-17 12:38:59
    最近开始认真学习算法,用的是...而判断环问题又分为有向图与无向图,我会分别对无向图和有向图判断环问题进行阐述,然后比较他们之间的不同. 首先介绍一下无向图,无向图的边没有方向,或者说每一条无向图的边都是双
  • 有向图的环和有向无环图

    千次阅读 2018-07-25 07:10:00
    本篇主要分享关于有向图的环和有向无环图(DAG,估计做大数据的同学到处都可以看到),所以相关概念我就不做详细介绍了。 用有向图中各个节点代表着一个又一个的任务,...
  • 二:有向图 1.定义 2.图形化解释 3.结合​表达式介绍 有向图和无向图区别: 三:简单图 1.定义 2.图形化解释 四:完全无向图 1.定义 2.图形化解释 五:有向完全图 1.定义 2.图形化解释 一:无向图 1....
  • python库之networkx之创建有向图的方法

    千次阅读 2020-07-20 20:07:56
    多的不说,看代码就懂了: import networkx as nx import matplotlib.pyplot as plt textline = '1 2 3' fh = open('test.edgelist','w') d = fh.write(textline) fh.close() G = nx.read_edgelist('test.edge...
  • 有向图的拓扑排序

    万次阅读 多人点赞 2016-03-15 23:01:41
     有向图的拓扑排序的基本思想是:首先在有向图中选取一个没有前驱的顶点,将其输出,从有向图中删除该顶点,并且删除以该顶点为尾的所有有向图的边。重复以上的步骤,直到图中的所有顶点均输出或是图中的顶点均没有...
  • 由邻接矩阵画有向图、无向图

    万次阅读 2017-07-19 10:39:08
    由邻接矩阵画有向图、无向图 由邻接矩阵画有向图的逻辑如下: 设邻接矩阵的行(列)数为N,矩阵中非零元素的个数为M,画布宽为W、高为H 1、有向图顶点数为N、有向边数为M,问题转化为:画正N边形的所有顶点、以及顶点...
  • 判断有向图是否有环

    千次阅读 2019-04-08 20:35:41
    1.计算中所有点的入度,把入度为0的点加入栈 2.如果栈非空: 取出栈顶顶点a,输出该顶点值,删除该顶点 从中删除所有以a为起始点的边,如果删除的边的另一个顶点入度为0,则把它入栈 3.如果中还存在顶点,则...
  • 有向图邻接矩阵

    万次阅读 多人点赞 2018-05-06 18:39:04
    :是一种线性结构,由n个点和m条边组成,任意两个点之间可以用连线连接. #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define MAX_VALUE 8888 //初始化数组的默认值,相当于无限大 #...
  • 有向图和无向图用邻接矩阵储存

    万次阅读 多人点赞 2017-04-08 09:15:47
    一般存储图的方式两种:一是用邻接矩阵表示,二是用邻接链表。 所谓用邻接矩阵,是用一个二维数组存储,边使用矩阵来构建模型,...无向图的边的矩阵一定是一个对称矩阵,因为无向图只关心边是否存在,而不关心方向,
  • Gephi画无向图和有向图(显示节点和边序号) 数据形式 如果画无向图只要把Type这一列设置成undirected,不填入数据默认是directed 导入数据以后就可以设计节点以及边的属性了,如下: 显示的有向图如下: ...
  • 23.有向图和无向图

    千次阅读 2017-09-04 20:29:24
    无向图的邻接表 有向图的邻接表 无向图的邻接矩阵 有向图的邻接矩阵
  • 有向图和无向图用邻接矩阵储存及代码实现

    万次阅读 多人点赞 2017-09-14 17:26:48
    一般存储图的方式两种:一是用邻接矩阵表示,二是用邻接链表。 所谓用邻接矩阵,是用一...1、无向图的存储:无向图的边的矩阵一定是一个对称矩阵,因为无向图只关心边是否存在,而不关心方向,V0和V1边,那么V1和V

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,151,262
精华内容 860,504
关键字:

有向图