精华内容
下载资源
问答
  • 拓扑排序简单的例子
    2022-09-01 13:55:20

    拓扑排序对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

    拓扑排序执行步骤

    由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。

    (1) 选择一个入度为0的顶点并输出之;

    (2) 从网中删除此顶点及所有出边

    循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列

    拓扑排序算法介绍
    拓扑排序(Topological Order)是指,将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

    这样说,可能理解起来比较抽象。下面通过简单的例子进行说明!
    例如,一个项目

    更多相关内容
  • 拓扑排序示例

    2022-04-30 21:30:46
    """ 设计:Python程序设计 作者:初学者 ...(2)拓扑排序中的第一的节点可以是图中的任何一个没有其他节点指向它的节点。 # 针对给定的有向图找到任意一种拓扑排序的顺序。 # 2.问题示例 # 有向图的
    """
    设计:Python程序设计
    作者:初学者
    日期:2022年 04月 30日
    """
    
    
    # 例114  拓扑排序
    #         1.问题描述
    #         给定一个有向图,图节点的拓扑排序定义如下;(1)对于图中的每一条有向边A——》B,
    #         在拓扑排序中A一定在B之前;(2)拓扑排序中的第一的节点可以是图中的任何一个没有其他节点指向它的节点。
    #         针对给定的有向图找到任意一种拓扑排序的顺序。
    #         2.问题示例
    #         有向图的拓扑排序可以为:
    #         [0,1,2,3,4,5]
    #         [0,2,3,1,5,4]
    #         3.代码实现
    # 定义有向图节点
    class DirectedMapNode:
        def __init__(self, x):
            self.label = x
            self.neighbors = []
    
    
    class Solution:
        """
        参数graph:有向图节点列表
        返回值:整数列表
        """
    
        def top_sort(self, graph):
            indegree = {}
            for x in graph:
                indegree[x] = 0
            for i in graph:
                for j in i.neighbors:
                    indegree[j] += 1
            ans = []
            for i in graph:
                if indegree[i] == 0:
                    self.dfs(i, indegree, ans)
            return ans
    
        def dfs(self, i, indegree, ans):
            ans.append(i.label)
            indegree[i] -= 1
            for j in i.neighbors:
                indegree[j] -= 1
                if indegree[j] == 0:
                    self.dfs(j, indegree, ans)
    
    
    # 主函数
    if __name__ == '__main__':
        s = Solution()
        g0 = DirectedMapNode(0)
        g1 = DirectedMapNode(1)
        g2 = DirectedMapNode(2)
        g3 = DirectedMapNode(3)
        g4 = DirectedMapNode(4)
        g5 = DirectedMapNode(5)
        g0.neighbors = [g1, g2, g3]
        g1.neighbors = [g4]
        g2.neighbors = [g4, g5]
        g3.neighbors = [g4, g5]
        graph = [g0, g1, g2, g3, g4, g5]
        result = s.top_sort(graph)
        print("输入:")
        print("输出:", result)
    
    
    展开全文
  • 拓扑排序算法

    千次阅读 2022-07-12 21:32:36
    拓扑排序

    拓扑排序介绍

    拓扑排序(Topological Order)是指,将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

    这样说,可能理解起来比较抽象。下面通过简单的例子进行说明!
    例如,一个项目包括A、B、C、D四个子部分来完成,并且A依赖于B和D,C依赖于D。现在要制定一个计划,写出A、B、C、D的执行顺序。这时,就可以利用到拓扑排序,它就是用来确定事物发生的顺序的。

    在拓扑排序中,如果存在一条从顶点A到顶点B的路径,那么在排序结果中B出现在A的后面。

    拓扑排序的算法图解

    拓扑排序算法的基本步骤:

    1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological);
    2. 把所有没有依赖顶点的节点放入Q;
    3. 当Q还有顶点的时候,执行下面步骤:
    3.1 从Q中取出一个顶点n(将n从Q中删掉),并放入T(将n加入到结果集中);
    3.2 对n每一个邻接点m(n是起点,m是终点);
    3.2.1 去掉边<n,m>;
    3.2.2 如果m没有依赖顶点,则把m放入Q;
    注:顶点A没有依赖顶点,是指不存在以A为终点的边。

     

    以上图为例,来对拓扑排序进行演示。

    缺少图

    第1步:将B和C加入到排序结果中。
        顶点B和顶点C都是没有依赖顶点,因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储,因此先访问B,再访问C。访问B之后,去掉边<B,A>和<B,D>,并将A和D加入到队列Q中。同样的,去掉边<C,F>和<C,G>,并将F和G加入到Q中。
        (01) 将B加入到排序结果中,然后去掉边<B,A>和<B,D>;此时,由于A和D没有依赖顶点,因此并将A和D加入到队列Q中。
        (02) 将C加入到排序结果中,然后去掉边<C,F>和<C,G>;此时,由于F有依赖顶点D,G有依赖顶点A,因此不对F和G进行处理。
    第2步:将A,D依次加入到排序结果中。
        第1步访问之后,A,D都是没有依赖顶点的,根据存储顺序,先访问A,然后访问D。访问之后,删除顶点A和顶点D的出边。
    第3步:将E,F,G依次加入到排序结果中。

    因此访问顺序是:B -> C -> A -> D -> E -> F -> G

    扑排序的代码说明

    拓扑排序是对有向无向图的排序。下面以邻接表实现的有向图来对拓扑排序进行说明。

    1. 基本定义

    // 邻接表中表对应的链表的顶点
    typedef struct _ENode
    {
        int ivex;                   // 该边所指向的顶点的位置
        struct _ENode *next_edge;   // 指向下一条弧的指针
    }ENode, *PENode;
    
    // 邻接表中表的顶点
    typedef struct _VNode
    {
        char data;              // 顶点信息
        ENode *first_edge;      // 指向第一条依附该顶点的弧
    }VNode;
    
    // 邻接表
    typedef struct _LGraph
    {
        int vexnum;             // 图的顶点的数目
        int edgnum;             // 图的边的数目
        VNode vexs[MAX];
    }LGraph;
    

    (01) LGraph是邻接表对应的结构体。 vexnum是顶点数,edgnum是边数;vexs则是保存顶点信息的一维数组。
    (02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据,而firstedge是该顶点所包含链表的表头指针。
    (03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引,而next
    edge是指向下一个节点的。

    2. 拓扑排序

    /*
     * 拓扑排序
     *
     * 参数说明:
     *     G -- 邻接表表示的有向图
     * 返回值:
     *     -1 -- 失败(由于内存不足等原因导致)
     *      0 -- 成功排序,并输入结果
     *      1 -- 失败(该有向图是有环的)
     */
    int topological_sort(LGraph G)
    {
        int i,j;
        int index = 0;
        int head = 0;           // 辅助队列的头
        int rear = 0;           // 辅助队列的尾
        int *queue;             // 辅组队列
        int *ins;               // 入度数组
        char *tops;             // 拓扑排序结果数组,记录每个节点的排序后的序号。
        int num = G.vexnum;
        ENode *node;
    
        ins  = (int *)malloc(num*sizeof(int));  // 入度数组
        tops = (char *)malloc(num*sizeof(char));// 拓扑排序结果数组
        queue = (int *)malloc(num*sizeof(int)); // 辅助队列
        assert(ins!=NULL && tops!=NULL && queue!=NULL);
        memset(ins, 0, num*sizeof(int));
        memset(tops, 0, num*sizeof(char));
        memset(queue, 0, num*sizeof(int));
    
        // 统计每个顶点的入度数
        for(i = 0; i < num; i++)
        {
            node = G.vexs[i].first_edge;
            while (node != NULL)
            {
                ins[node->ivex]++;
                node = node->next_edge;
            }
        }
    
        // 将所有入度为0的顶点入队列
        for(i = 0; i < num; i ++)
            if(ins[i] == 0)
                queue[rear++] = i;          // 入队列
    
        while (head != rear)                // 队列非空
        {
            j = queue[head++];              // 出队列。j是顶点的序号
            tops[index++] = G.vexs[j].data; // 将该顶点添加到tops中,tops是排序结果
            node = G.vexs[j].first_edge;    // 获取以该顶点为起点的出边队列
    
            // 将与"node"关联的节点的入度减1;
            // 若减1之后,该节点的入度为0;则将该节点添加到队列中。
            while(node != NULL)
            {
                // 将节点(序号为node->ivex)的入度减1。
                ins[node->ivex]--;
                // 若节点的入度为0,则将其"入队列"
                if( ins[node->ivex] == 0)
                    queue[rear++] = node->ivex;  // 入队列
    
                node = node->next_edge;
            }
        }
    
        if(index != G.vexnum)
        {
            printf("Graph has a cycle\n");
            free(queue);
            free(ins);
            free(tops);
            return 1;
        }
    
        // 打印拓扑排序结果
        printf("== TopSort: ");
        for(i = 0; i < num; i ++)
            printf("%c ", tops[i]);
        printf("\n");
    
        free(queue);
        free(ins);
        free(tops);
        return 0;
    }
    

    折叠

    说明:
    (01) queue的作用就是用来存储没有依赖顶点的顶点。它与前面所说的Q相对应。
    (02) tops的作用就是用来存储排序结果。它与前面所说的T相对应。

    拓扑排序的完整源码和测试程序

    拓扑排序源码(list_dg.c)

    展开全文
  • 拓扑排序(附例题)

    千次阅读 2021-11-23 15:19:06
    ACWING848 拓扑排序 给定一个 n nn 个点 m mm 条边的有向图,点的编号是 1 11 到 n nn,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 − 1 -1−1。 若一个由图中所有点...

    思想

    拓扑排序本质上就是把一个有向无环图(DAG)变成一个线性序列,给定DAG中两个点u,v,若<u,v>∈E(G),那么在线性序列中,u一定在v前面。
    有向无环图一定可以拓扑排序,有向有环图一定不能拓扑排序。

    例题

    ACWING848 拓扑排序
    在这里插入图片描述

    输入样例:

    3 3
    1 2
    2 3
    1 3
    

    输出样例:

    1 2 3
    

    AC代码

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int h[N], e[N], ne[N], q[N], d[N], idx, n, m;
    void add(int a, int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    int toposort()
    {
        int hh = 0, tt = -1;
        for(int i = 1; i <= n; i++)
        {
            if(!d[i])
                q[++tt] = i;
        }
        while(hh <= tt)
        {
            int t = q[hh++];
            for(int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                d[j]--;
                if(!d[j])
                    q[++tt] = j;
            }
        }
        return tt == n - 1;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int a, b;
        memset(h, -1, sizeof h);
        cin >> n >> m;
        while(m--)
        {
            cin >> a >> b;
            add(a, b);
            d[b]++;
        }
        if(toposort())
            for(int i = 0; i < n; i++)
                cout << q[i] << ' ';
        else
            cout << "-1" << '\n';
        return 0;
    }
    
    

    核心思想与注意点:

    • 调用toposort()函数后,如果队列中的元素个数等于给定图的元素个数,则说明该图是有向无环图,可以拓扑排序。
    • 每次输入一条有向边,就将有向边末尾的元素入度加一。
    • 拓扑排序时,先把入度为0的点全部入队,然后出队一个元素,bfs,把这个元素的邻接点入度全部减一,如果它的邻接点入度变为0,那么把它的邻接点也入队。
    展开全文
  • 事实证明的确是这样,拓扑排序的概念与实现都是非常简单的。别被看上去高大上的名字吓到了。 拓扑序列概念介绍 首先,我们给出一个如图的有向图 然后我们给出一个序列a={1,2,3,4},我们随便在有向图中选择一条边...
  • 拓扑排序详解及例题

    2022-02-21 19:52:39
    对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序...简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。(若图中存在环路则不可能排出一个线性次序) 总结起来.
  • 除普通排序算法外,它还提供了分组拓扑排序的几种实现方式,这意味着您可以传递具有将在排序中分组在一起的类型的项目。 通过使用字符串而不是数组的实现,其速度比常规实现快20倍以上。它是什么? 拓扑排序对于...
  • 拓扑排序

    万次阅读 多人点赞 2021-02-02 17:50:31
    拓扑排序 一、拓扑排序的定义: 先引用一段百度百科上对于拓扑排序的定义: 对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序,是将 G 中所有顶点排成一个线性序列,使得图中任意一对顶点 u ...
  • 拓扑排序应用:拓扑排序是应用在有向图中,对所有的节点进行排序。 思路: 1.首先统计所有节点的入度,把其加入一个入度表中; 2.维护一个队列,讲入度为0的节点入队;并且维护一个邻接表用于存储每个节点相关联...
  • 图算法入门3之活动网络-AOV网络,AOV网络的基本概念以及拓扑排序的代码实现。
  • 拓扑排序-java实现

    2021-07-23 11:00:31
    拓扑排序 参考 https://blog.csdn.net/sinat_22013331/article/details/52046101 上面那个链接中代码有错误,下面是更正之后的 package com.example.javapractice2.tree; import org.springframework.util....
  • 这个概念很好理解,我们先来看一个生活中的拓扑排序例子。日常生活中,我们在穿衣服的时候都有一定的顺序,我们可以把这种顺序想成,衣服与衣服之间有一定的依赖关系。比如说,你必须先穿袜子才能穿鞋,先穿内裤...
  • 拓扑排序理解

    2021-09-29 20:16:41
    拓扑排序首先要简单介绍一下AOV网。AOV网指的是顶点表示活动,有向边表示活动之间的次序(比如:a->b指的是a发生后b才可以发生)。可以将AOV网联想到一个建筑的施工图(A:买材料,B:打地基,C:盖楼)就可以有一...
  • 超详细讲解实现拓扑排序、关键路径

    千次阅读 多人点赞 2022-03-26 11:07:49
    今天,小编带着大家来学习图中非常重要的一环,拓扑排序和关键路径! 首先,我们需要知道的是,拓扑排序是关键路径的基础,正因如此,当我们知道了关键路径在生活中的应用,相信大家也就明白这两个算法的重要性了!...
  • 本章介绍图的拓扑排序。和以往一样,本文会先对拓扑排序的理论知识进行介绍,然后给出C语言的实现。后续再分别给出C++和Java版本的实现。...下面通过简单例子进行说明!例如,一个项目包括A、B、C、D...
  • 前面分别介绍了拓扑排序的C和C++实现,本文通过Java实现拓扑排序。目录1.拓扑排序介绍2.拓扑排序的算法图解3.拓扑排序的代码说明4. 拓扑排序的完整源码和测试程序拓扑排序介绍拓扑排序(Topological Order)是指,将一...
  • 图的拓扑排序

    2022-07-24 22:07:55
    图的拓扑排序的代码实现
  • 先看一个例子,大学排课(整理出先后依赖顺序),以计算机专业为例,如下表所示,想线上数据结构时候,必选先修C1和C2。如果课程比较少可以人肉排下,如果课程比较多,就需要借助相应工具或者算法来解决。 可以使用...
  • 图论算法之拓扑排序

    2020-11-13 21:25:37
    拓扑排序总结: 1、AOV网 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子...
  • 数据结构与算法—拓扑排序

    万次阅读 多人点赞 2019-09-04 11:51:55
    目录介绍拓扑排序算法分析 介绍 拓扑排序,很多人都可能听说但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。而实质上它是对有向图的...
  • 拓扑排序-C语言详解

    千次阅读 2022-03-28 16:33:42
    拓扑排序-C语言详解
  • 文章目录前言一、拓扑排序规则二、卡恩算法实现1....拓扑排序即把出度为0的结点一个一个找出来,看下例子就知道了: 上图中1入度为0,所以1排在前面,此时拓扑排序为{1},将1指出去的箭头都擦去,.
  • 拓扑排序及其应用

    2020-06-01 17:00:33
    拓扑排序: 在AOV网没有环路的情况下,将这些活动排成一个满足所有边的先后顺序条件线性序列。 排序算法: 1)选择AOV网中一个没有前驱的结点输出; 2)将输出结点从图中删除(并删除与当前结点相连的所有边) ...
  • 拓扑排序详解与实现

    2020-05-17 21:22:07
    拓扑排序详解与实现 介绍 拓扑排序,很多人都可能听说但是不了解的一种算法。或许很多人只知道它是图论的一种排序,至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。而实质上它是对有向图的顶点排...
  • 拓扑排序(Topological sorting)

    千次阅读 2022-04-18 23:59:48
    拓扑排序指的是有向无环图(DAG); 学过计算机网络的知道计算机网络中有一个拓扑结构; 下面就是一个拓扑结构; 那拓扑序就是,图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前 我们...
  • 拓扑排序讲解

    2019-08-03 18:31:49
    拓扑排序 1.什么是拓扑排序 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任 意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,...
  • 看下面这个例子 节点 5 和 4 不依赖任何节点,因此在输出队列里也靠前,而 0 和 1 分别有 2 个依赖的节点,因此需要靠后处理,经过拓扑排序后的结果: 5 4 2 3 1 0 需要注意的是拓扑排序的结果可能不唯一,起点通常...
  • 拓扑排序常出现在涉及偏序关系的问题中,例如时序的先后、事物的依赖等。针对这些问题拓扑排序通常能有效地给出可行解。为了便于理解,我们先来看一个实例,开源软件常使用GNU make工具来管理项目的构建,这里的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,063
精华内容 4,425
热门标签
关键字:

拓扑排序简单的例子