精华内容
下载资源
问答
  • 有向无环图 拓扑排序

    2012-02-07 15:53:57
    package endual.... * 找到一个没有后续的顶点(这是从有向图的角度是做了,而不能用最简单的那种图去考虑问题了) * 顶点的后续也是一些顶点,他们是该节点的直接“下游” 也就是说这些节点与他们由一条...

    package endual.tuopupaixu;
    
    /**
     * 拓扑排序
     * 
     * 拓扑排序的思想虽然不寻常,但是还是很简单的
     * 有两个步骤要去考虑
     * 步骤1 
     *   找到一个没有后续的顶点(这是从有向图的角度是做了,而不能用最简单的那种图去考虑问题了)
     *      顶点的后续也是一些顶点,他们是该节点的直接“下游”  也就是说这些节点与他们由一条边相连,并且
     *      边的方向指向它们。如果有一条边从A指向B,那么B是A的后续
     *      
     *  步骤2
     *    从图中删除这个顶点,在列表的前面插入顶点的标记
     *    
     *  重复步骤1和步骤2,直到所有的顶点都从图中删除。这时,列表显示的顶点顺序就是拓扑排序的结构了
     * @author Endual
     *
     *   说明:
     *   删除顶点似乎是一个极端的步骤,但是它是算法的核心,如果第一个顶点不处理,算法就不能计算出要处理的是第二个顶点。
     *   如果需要,也可以在其他地方存储图的数据(顶点列表或者邻接矩阵),然后再排序完成后恢复他们就可以了
     *   
     *      算法能够执行是因为,如果一个顶点没有后续,那么它肯定是拓扑序列的最后一个了。一旦删除它,剩下的顶点中比如有一个
     *      没有后续的,所以它成为下一个拓扑序列的最后的一个了。依次类推。
     *   
     *   
     *   拓扑排序算法可以既可以是连通图,也可以用于非联通图。这可以模拟另外一种两个互不相关的目标的情况。
     *   例如同时获得数学学位和急救资格的证书。
     */
    
    /**
     * 环和树
     * 
     * 环是拓扑排序无法处理的。
     * 图的话=====》》》》 不是环就是树了
     * @author Endual
     *
     *要计算是不是要环也是简单的:
     *   如果N个顶点的图有超过N-1条边,那么就肯定有环的存在了。可以尝试下画一个没有环而有N个顶点的,N条边的图,这样就可以lij
     *   理解了
     *   
     *   拓扑排序必须在无环的有向图中进行的(有向无环图)
     *
     *
     */
    public class GrapnSort {
    
    }
     
    展开全文
  • 无环拓扑排序与关键路径 一:基本概念 1:无环图 一个无环有向图称做无环图(Directed Acyclic Graph)。简称DAG 图。DAG 图是一类较有向树更一般的特殊有向图, 2:拓扑排序 对一个...

    有向无环图 拓扑排序与关键路径

    一:基本概念

    1:有向无环图

    一个无环的有向图称做有向无环图(Directed Acyclic Graph)。简称DAG 图。DAG 图是一类较有向树更一般的特殊有向图,
    这里写图片描述

    2:拓扑排序

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

    3:关键路径

    通俗的讲:关键路径是项目中最长的路径。任何关键路径上的元素的延迟(浮动)时间将直接影响项目的预期完成时间。

    4:AOE网

    顶点表示事件弧表示活动,弧上的权值表示活动持续的时间的有向图AOE(Activity On Edge Network)网。
    (1) 活动(弧)开始的最早时间ee(i);
    (2) 活动(弧)开始的最晚时间el(i) ;
    (3) 事件(顶点)开始的最早时间ve(i);
    (4) 事件(顶点)开始的最晚时间vl(i)。

    5:关键活动

    定义ee(i)=el(i)的活动叫关键活动。

    二:拓扑排序

    1:储存结构

    (1):采用邻接表作为存储结构(无向图
    邻接表详细知识见下:
    https://blog.csdn.net/weixin_39956356/article/details/80514672

    注意:权值一定要在建好链表后赋值

    这里写图片描述
    相关代码

    //创建有向图的邻接表
    void CreatDLGraph(DLGraph &G)
    {
        for (int i = 0; i < G.vexnum; i++) {
            printf("Please enter %d data:", i + 1);
            scanf(" %c", &G.vertices[i].data);                                      //输入顶点值
            G.vertices[i].firstarc = NULL;                                          //弧表头指针置为空  
        }
    
        VertexType v1, v2;                                                          //输入的两条弧(A B C···)
        EdgeType w;
        int i, j;                                                                   //获取(v1,v2)各自在图中位置      
        printf("Please input the two data of arc,for example: A C\n");
        for (int k = 0; k < G.arcnum; k++) {
            printf("The %d arc: ", k + 1);
            scanf(" %c", &v1);                                                      //输入第一个顶点
            getchar();                                                              //把输入的空格读走
            v2 = getchar();                                                         //输入弧的第二个顶点
            scanf("%d", &w);                                                        //输入权值
            i = LocateVex(G, v1);                                                   //获取弧的第一个节点位置
            j = LocateVex(G, v2);                                                   //获取弧的第二个节点位置
    
    
    
            /*******************************************************
            **  1:无向图相互的,所以下面的两段代码就i,j互换
            **  2:这里要清楚怎么接上去的
            新结点的next后面接的是之前的一串上(可以这么想,新的节点接在原来的左弧)
            不断把上次firtarc赋值给新节点的next,新的p又接在firtarc
            ********************************************************/
            ArxNode *p = (ArxNode *)malloc(sizeof(ArxNode));                        //分配弧结点空间
            p->adjvex = j;
            p->nextarc = G.vertices[i].firstarc;                                    //i是弧尾,且出发的弧是一链表,说明这里的p是
            G.vertices[i].firstarc = p;
    
            //注意:这里必须在邻接表创建后才能赋值w,不然G.vertices[i].firstarc是个空指针-error
            G.vertices[i].firstarc->weight = w;                                     //某活动持续的时间
    
            //p = (ArxNode *)malloc(sizeof(ArxNode));                                   //重新分配弧结点空间(上面的消逝了)
            //p->adjvex = i;
            //p->nextarc = G.vertices[j].firstarc;                                  //将结点i链接到j的单链表中
            //G.vertices[j].firstarc = p;
        }
    }

    (2):邻接表求出度——这个很简单,邻接本来就是一个节点所有出发的弧
    这里写图片描述

    相关代码

    //求出度
    void FindOutDegree(DLGraph &G, int *indegree)
    {
        ArxNode *p;                                                                 //切记:这里创建一个临时p,我们不可以把之前邻接表结构改变了,就像给你U盘拷贝东西,你只能复制而不是剪切!你不可以改变之前的结构,不然之后邻接表是个空的
        int num;
        for (int i = 0; i < G.vexnum; i++)                                          
        {
            num = 0;
            p = G.vertices[i].firstarc;                                             //先指向一个结点
            while (p != NULL) {
                p = p->nextarc;                                                     //指向下一条弧
                num++;                                                              //出度加一
            }
            indegree[i] = num;
        }
    }

    (3):邻接表求入度——这个对邻接表而言是不可以直接求出,需要一次遍历才能求出一个节点的入度
    这里写图片描述

    相关代码

    //求入度
    void FindInDegree(DLGraph &G, int *indegree)
    {
        ArxNode *p;                                                                 //切记:这里创建一个临时p,我们不可以把之前邻接表结构改变了,就像给你U盘拷贝东西,你只能复制而不是剪切!你不可以改变之前的结构,不然之后邻接表是个空的
        int num;
        for (int i = 0; i < G.vexnum; i++)                                          //求所有节点的入度
        {
            num = 0;
            for(int j = 0; j < G.vexnum; j++)                                       //一个结点的入度需要遍历所有结点才可以知道
            { 
                p = G.vertices[j].firstarc;                                         //先指向一个结点
                while (p != NULL) {
                    if (p->adjvex == i)                                             //从另外一个结点出发的链域,发现与该次所求结点一致,入读加一,break
                    {
                        num++;
                        break;
                    }
                    p = p->nextarc;                                                 //指向下一条弧
                }
            }
            indegree[i] = num;
            //printf("%d\t", indegree[i]);
        }
    }

    2:拓扑排序

    (1):这里涉及两个栈(S,T),事件开始的最早时间ve[i]
    S—-拓扑有序栈
    T—-逆拓扑有序栈
    初始值全为0ve[i] = 0; 最早发生时间
    这里写图片描述
    这里写图片描述
    (2):入度为0,全部入栈S
    这里写图片描述
    (3):S出栈(直到S为空),T入栈
    (4):ve[k] (终点)值更新 popDataIndex(起点)–>k(终点)
    这里写图片描述
    (5):关于栈的基础函数

    stack.h

    #ifndef _STACK_H
    #define _STACK_H
    #include <stdlib.h>
    
    #define STACK_INIT_SIZE 8                                           //储存空间初始量
    #define STACKINCREMENT  5                                           //储存空间分配增量
    
    #define ERROR       0
    #define OK           1
    #define TRUE         2
    #define OVERFLOW    -2
    
    typedef int Status;
    typedef char SElemType;
    
    typedef struct 
    {
        SElemType *base;                                                //栈底
        SElemType *top;                                                 //栈顶
        int        stacksize;                                           //每次的新元素个数
    }SqStack;
    
    Status InitStack(SqStack &s);                                       //构造一个空栈操作              
    Status Push(SqStack &s, SElemType e);                               //栈的插入操作 Push
    SElemType Pop(SqStack &s);                                          //取栈顶元素 Pop
    SElemType GetTop(SqStack &s);                                       //获取栈顶元素
    SElemType StackLength(SqStack &s);                                  //获取栈当前元素个数
    Status StackEmpty(SqStack &s);
    #endif // !_STACK_H
    

    stack.cpp

    #include "stdafx.h"
    #include "stack.h"
    
    //构造一个空栈操作
    Status InitStack(SqStack &s)
    {
        s.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
        if (!s.base)
            return OVERFLOW;
        memset(s.base, 0, STACK_INIT_SIZE * sizeof(SElemType));                 //初始化每个都弄为0
        s.top = s.base;
        s.stacksize = STACK_INIT_SIZE;
        return OK;
    }
    
    
    //栈的插入操作 Push
    Status Push(SqStack &s, SElemType e)
    {
        if ((s.top - s.base) >= s.stacksize)
        {
            s.base = (SElemType *)realloc(s.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType));
            if (!s.base)
                return OVERFLOW;
            s.top = s.base + s.stacksize;
            s.stacksize += STACKINCREMENT;
        }
        *s.top++ = e;
        return OK;
    }
    
    
    //取栈顶元素 Pop
    SElemType Pop(SqStack &s)
    {
        if (s.base == s.top)
            return ERROR;
        return *--s.top;
    }
    
    
    //获取栈顶元素
    SElemType GetTop(SqStack &s)
    {
        if (s.base == s.top)
            return ERROR;
        return *(s.top - 1);
    }
    
    
    //获取栈当前元素个数
    SElemType StackLength(SqStack &s)
    {
        return (s.top - s.base) / sizeof(SElemType);
    }
    
    //判栈空
    Status StackEmpty(SqStack &s)
    {
        if (s.base == s.top)
            return 1;
        return 0;
    }

    相关代码

    int *ve;
    //拓扑排序
    int TopologicalOrder(DLGraph &G, SqStack &S, SqStack &T)
    {
        int *indegree = (int *)malloc(G.vexnum * sizeof(int));
        ve = (int *)malloc(G.vexnum * sizeof(int));
        FindInDegree(G, indegree);                                                  //求出每个节点的入度
    
        int count = 0;                                                              //累计访问的结点个数
        InitStack(S);                                                               //拓扑有序栈
        for (int i = 0; i < G.vexnum; i++) {
            if (!indegree[i])
                Push(S, G.vertices[i].data);                                        //入度为0,全部入栈S
            ve[i] = 0;                                                              //最早发生时间
        }
    
        InitStack(T);                                                               //逆拓扑有序栈
        while(!StackEmpty(S)){
            char popData = Pop(S);                                                  //出栈元素
            int popDataIndex = LocateVex(G, popData);                               //出栈元素的位置
            Push(T, popData);                                                       //出栈元素马上入栈T
            count++;                                                                //访问节点数+1
    
            ArxNode *p = G.vertices[popDataIndex].firstarc;
            for (; p; p = p->nextarc) {
                int k = p->adjvex;
                if (--indegree[k] == 0)                                             //减1,入度为0,入栈S
                    Push(S, G.vertices[k].data);
                if (ve[popDataIndex] + p->weight > ve[k])                           //更新k最早发生时间
                    ve[k] = ve[popDataIndex] + p->weight;
            }
        }
    
        printf("\n\nve[]:\n");
        for(int i = 0; i < G.vexnum; i++)
            printf("%d\t", ve[i]);
    
        if (count < G.vexnum)                                                       //该有向网有环
            return ERROR;
        return OK;
    }

    三:关键路径

    1:vl[i]初始值是关键路径长度(最长时间),也就是T栈顶元素对应的ve[ ]

    这里写图片描述

    2:逆序求vl[ ],T出栈(直至为0),下面用一个图将清楚

    这里写图片描述
    这里写图片描述

    3:求所有的关键路径并输出,关键路径长度,注意怎么计算ee(正着) 与 el (反着)的

    4:ee = el,关键路径

    这里写图片描述
    这里写图片描述

    相关代码

    //求关键路径及长度
    int CriticalPath(DLGraph &G)
    {
        SqStack S;
        SqStack T;
        int *vl = (int *)malloc(G.vexnum * sizeof(int));
    
        if (!TopologicalOrder(G, S, T)){                                            //有环结束,不需要继续了
            printf("The direction graph contains rings, Can't output critical path, Test end!!!\n");
            return ERROR;
        }
        else
        {
            ArxNode *p;
            int k;
            for (int i = 0; i < G.vexnum; i++)
                vl[i] = ve[LocateVex(G, GetTop(T))];                                //获取栈T的栈顶元素,找到其位置,把ve[]赋值给vl[]的所有元素(就是把最大值赋给所有的vl[])
            while (!StackEmpty(T)) {
                char popData = Pop(T);                                              //出栈元素
                int popDataIndex = LocateVex(G, popData);                           //出栈元素的位置
                p = G.vertices[popDataIndex].firstarc;
                for (; p; p = p->nextarc) {
                     k = p->adjvex;
                    if (vl[k] - p->weight < vl[popDataIndex]) {                     //倒序求,已知k(弧头)求popDataIndex(弧尾),弧尾-弧头<弧头,替换
                        vl[popDataIndex] = vl[k] - p->weight;
                    }
                }
            }
    
            printf("\n\nvl[]:\n");                                                  //输出vl[]
            for(int i = 0; i < G.vexnum; i++)
                printf("%d\t", vl[i]);
    
            /*******************************************************************
            **  这里我举个例子,比如A->B
            **  在第一次循环中,i是A  k是B
                               el是'vl[B]'- 权值 ---如果等于--ee = ve[i],关键路径
            ********************************************************************/
            int ee, el;
            printf("\n\ncritical path  weight\tee    el    是否为关键路径");
            for (int i = 0; i < G.vexnum; i++)                                      //求所有的关键路径
                for (p = G.vertices[i].firstarc; p; p = p->nextarc) {               //不防从第一个点开始,比如A
                    k = p->adjvex;
                    ee = ve[i];     el = vl[k] - p->weight;
                    if (ee == el) {
                        printf("\n%c --> %c weight: %d\tee: %d el:%d   关键路径", G.vertices[i].data, G.vertices[k].data, p->weight, ee, el);
                    }
                }
            printf("\n\nThe length of critical path is: %d", vl[G.vexnum-1]);           //关键路径长度
        }
        return OK;
    }

    三:主函数与输出

    (1):主函数

    #include "stdafx.h"
    #include "Topological.h"
    #include "stack.h"
    
    int main()
    {
        DLGraph G;
        printf("Please enter vexnum and arcnum: ");
        scanf("%d %d", &G.vexnum, &G.arcnum);                                               //输入结点数,弧数
    
        CreatDLGraph(G);                                                                    //创建有向图的邻接表
        printf("\n无向图的邻接表输出:\n");
        PrintDLGraph(G);                                                                    //输出有向图的邻接表
    
        CriticalPath(G);                                                                    //输出关键路径与长度
    
        return 0;
    }

    (2):输出
    这里写图片描述

    四:感谢与源代码(VS2017)

    (1):感谢以下文章对我的帮助
    https://www.cnblogs.com/acmtime/p/6106148.html
    (2):源代码
    链接: https://pan.baidu.com/s/1-n70wJc42KfQvtHOsJn-DQ 密码: zjbg

    展开全文
  • final为最终代码,其他为测试代码,有向无环图进行拓扑排序若不是DAG则输出圈
  • 拓扑排序是将有向无环图的顶点排成一个线性序列的过程。 比如可将上 三、拓扑排序步骤 1. 首先要任意选择一个没有前驱的顶点,即入度为0的点,然后将它输出。 在下面这张图中我们选择1为出发点。 2. ...

    一、有向无环图

    • 有方向
    • 没有闭环

    有向图的拓扑排序

     

    二、拓扑排序

    拓扑排序是将有向无环图的顶点排成一个线性序列的过程。

    比如可将上图

     

    三、拓扑排序步骤

    1. 首先要任意选择一个没有前驱的顶点,即入度为0的点,然后将它输出。

    在下面这张图中我们选择1为出发点。

    有向图的拓扑排序

     

    2. 删除该节点以及与它相关联的所有边,这个点的nexts里面的点入度就减少1

    选择1为出发点之后,我们将它输出,并删除该节点以及与它相关联的所有边。

     

    有向图的拓扑排序

     

    3. 然后在删除后的图中继续找一个没有前驱的节点,

    这里没有前驱的节点只有2和3.

    这里我们选择3,那么将节点3输出后的图 如下图所示。

    有向图的拓扑排序

     

    4. 继续找入度为0的点重复上述步骤。

    接下来没有前驱的节点只有2和6了。

    我们这里选择节点6,同样的输出节点6后删除。

    然后继续找没有前驱的节点。这时候没有前驱的节点只剩下节点2.

     

    有向图的拓扑排序

    接下来的点继续进行拓扑排序,

     

    5. 得到的拓扑排序的一种如下图所示。

    有向图的拓扑排序

     

    相信大家也都发现其实拓扑排序是不唯一的,我们选择的出发点不同,结果就是不一样的。

    这里给出大家针对上图几种拓扑排序序列。

    有向图的拓扑排序

     

     

    四、算法设计

    用一个map保存他的所有节点对应的入度。

    用一个队列保存每次入度为0的节点然后pop,pop的顺序就是拓扑排序的顺序。

     

    list <node*> tsort(graph G) {
    	list<node*> res;
    	unordered_map<node*, int> inmap; 
    	queue<node*> zeronode;
    	for (auto next : G.nodes) {//G.nodes是map
    		inmap[next.second] = next.second->in;
    		if (next.second->in == 0) {
    			zeronode.push(next.second);
    		}
    	}
    	while (!zeronode.empty()) {
    		node* cur = zeronode.front();
    		zeronode.pop();
    		res.push_back(cur);
    		for (auto next : cur->nexts) {
    			inmap[next]--;
    			if (inmap[next] == 0) {
    				zeronode.push(next);
    			}
    		}
    	}
    
    	return res;
     }

     

     

    https://jingyan.baidu.com/article/1e5468f9c2c830094861b769.html

     

    https://zhuanlan.zhihu.com/p/127190494

    展开全文
  •   无环图的拓扑排序在 https://blog.csdn.net/Bob__yuan/article/details/95613891 也记录,是通过拓扑排序查看一个图是不是无环的。   这篇文章记录的是另一种用法,就是用有向图来表示任务的依赖关系,...

      有向无环图的拓扑排序在 https://blog.csdn.net/Bob__yuan/article/details/95613891 也有记录,是通过拓扑排序查看一个图是不是无环的。
      这篇文章记录的是另一种用法,就是用有向图来表示任务的依赖关系,然后通过拓扑排序找出按照依赖关系前后顺序完成所有任务的方法。百度里介绍拓扑排序也是说拓扑排序就是这个目的。
      就比如说,有 n 个任务需要执行,但是有的任务和任务之间是有依赖关系的,比如穿毛裤之前肯定要先穿秋裤这种感觉。题目是:第一行给出两个正整数 nmn 表示任务总数,m 表示有 m 个依赖关系,下边一行是 n 个正整数,表示每个任务需要花费的时间(任务从 1 开始计数),接下来 m 行每行两个正整数 xi 、yi 表示 yi 依赖 xi,也就是 xi 必须在 yi 之前完成。如果一个任务必须完成了才能开始新的任务,怎么能让所有任务平均等待时间最短。
      肯定要让完成所需时间短的任务先完成,所以需要一个优先队列,还需要考虑的是,先让所有入度 为0(也就是不依赖别的任务)的任务进队列,然后每次有任务完成,如果有任务依赖它,那这个任务的入度就减少1,如果入度减少为 0,说明这个任务前边的依赖任务已经都完成了,就让它入队,代码如下:

    #include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    
    vector<int> need_time;
    
    struct cmp {
    	bool operator()(int i, int j) {
    		if (need_time[i] != need_time[j])
    			return need_time[i] > need_time[j];
    		else
    			return i > j;
    	}
    };
    
    int main() {
    	int n, m;		// n 个任务,m 个依赖关系
    	cin >> n >> m;
    	need_time = vector<int>(n + 1);
    	vector<int> ins(n + 1, 0);			// 每个节点的入度
    	vector<pair<int, int>> req(m + 1);	// require
    	for (int i = 1; i <= n; ++i)
    		cin >> need_time[i];
    	for (int i = 1; i <= m; ++i){
    		cin >> req[i].first >> req[i].second;
    		++ins[req[i].second];
    	}
    
    	priority_queue<int, vector<int>, cmp> q;
    
    	// 入度为0(不依赖别的任务)的任务入队
    	for (int i = 1; i <= n; ++i)
    		if(ins[i] == 0)
    			q.push(i);
    	while (!q.empty())
    	{
    		auto tmp = q.top();
    		cout << tmp << " ";
    		q.pop();
    		for (auto ite = req.begin(); ite != req.end();)	{
    			if (ite->first == tmp) {
    				if (--ins[ite->second] == 0)
    					q.push(ite->second);
    				ite = req.erase(ite);
    			}
    			else
    				++ite;
    		}
    	}
    }
    

      也可以把任务依赖关系用一个 unordered_map<int, unordered_set< int >> 来存储,这样每次就不需要遍历了。

    展开全文
  • 算法7-12:有向无环图拓扑排序 时间限制: 1 Sec 内存限制: 32 MB 题目描述 由某个集合上的一个偏序得到该集合上的一个全序,这个操作被称为拓扑排序。偏序和全序的定义分别如下: 若集合X上的关系R是自反的、反对...
  • Kahn算法 拓扑排序
  • 算法 有向无环图 拓扑排序

    千次阅读 2017-05-23 11:48:21
    1. 如何构造图 邻接矩阵(二维数组) 图的邻接矩阵存储方式是用两个数组来表示图,一个一维数组存储图中顶点信息,一个二维数组存储图中边或弧的...无向图成为顶点v的边表,有向图成为顶点v作为弧尾的出边表。等等其他表
  • //该算法比较简单,对无环图进行拓扑排序输出。也可以检验有向图是否存在回路。这里处理的对象是邻接表。 bool ToplogicalSort(Graph G){ InitStack(S); for(int i=0;i&lt;G.vexnum;i++)//初始化栈,存储...
  • 第7章 有向无环图拓扑排序 ——《数据结构》-严蔚敏.吴伟民版  源码使用说明 链接☛☛☛ 《数据结构-C语言版》(严蔚敏,吴伟民版)课本源码+习题集解析使用说明  课本源码合辑 链接☛☛☛ 《数据结构...
  • : 由一个有向无环图的顶点组成的序列, 当且仅当满足以下条件的序列时, 称为该的一个拓扑排序: 每个顶点出现且仅出现一次; 若 A 在序列中排在 B 的前面, 则中不存在从 B 到 A 的路径; 拓扑排序...
  • 带你了解有向无环图拓扑排序

    千次阅读 2020-04-09 19:19:42
    在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个无环图(DAG图)。而提到DAG,就差不多会联想到拓扑排序拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序的操作。...
  • 如果一个有向图的任意顶点都无法通过一些向边回到自身,那么称这个图为无环图(Directed Acyclic Graph, DAG)。 拓扑排序 拓扑排序是将无环图 G 的所有顶点排序成一个线性序列,使得对图 G 中的任意两个...
  • 拓扑排序只适用于有向无环图 拓扑排序规则如下: (1) 从有向无环图中选择一个没有前驱(入度为0)的顶点vertex,并将顶点输出 (2)从中删除这个顶点,同时删除从该顶点出发的所有边 本文算法复杂度为 O(n+e); ...
  • 有向无环图拓扑排序 有向无环图 (DAG) 的拓扑排序是顶点的线性排序,使得对于每个有向边 u, v,顶点 u排在 v 之前。如果不是 DAG,则无法对图进行拓扑排序。 例如,下拓扑排序是「5 4 2 3 1 0」。一个...
  • No.4有向无环图拓扑排序

    千次阅读 2019-10-20 08:57:10
    举个浅显易懂的有向无环图拓扑排序的例子(Linux驱动匹配): 比如现在abcde五个驱动模块文件,它们的具体的依赖顺序未知 但是给出了单个驱动模块文件会依赖其它的驱动依赖模块 1> a->bce,表示a的正常工作...
  • **有向无环图拓扑排序** 一. 偏序:若集合X上的关系R是自反的,反对称的和传递的,则称R是集合X上的偏序关系。 全序:设R是集合X上的偏序,如果对每个x,y属于X,必xRy或yRx,则称R是集合X上的全序关系。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,402
精华内容 8,960
关键字:

有向无环图的拓扑排序