【算法基础】拓扑排序及实战

这篇具有很好参考价值的文章主要介绍了【算法基础】拓扑排序及实战。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一 、概览

这里涉及到图的概念,感兴趣的同学请移驾 –>图<–
下面还有两个相关概念,大概说一下:

1.1 有向无环图

定义:在图论中,如果一个有向图从任意顶点出发无法经过若干条边回到该点,则这个图是一个有向无环图(DAG,Directed Acyclic Graph)
每条边都带有从一个顶点指向另一个顶点的方向的图为有向图。有向图中的道路为一系列的边,系列中每条边的终点都是下一条边的起点。
如果一条路径的起点是这条路径的终点,那么这条路径就是一个环。有向无环图即为没有环出现的有向图

1.2 拓扑结构

定义:将实体抽象成点,将实体间的链接抽象成线,进而以图形的关系呈现这些点与线之间的关系。其目的在于研究这些点、线之间的相连关系。表示点和线之间关系的图被称为拓扑结构 图

比较常用的是网络拓扑结构
【算法基础】拓扑排序及实战

背景:
一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的结束为先决条件的,但有些子工程没有先决条件,可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。通常,我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。

二、拓扑排序(顶点的线性排序)

定义:在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列

例如,一个项目包括A、B、C、D四个子部分来完成,并且A依赖于B和D,C依赖于D。现在要制定一个计划,写出A、B、C、D的执行顺序。这时,就可以利用到拓扑排序,它就是用来确定事物发生的顺序的。

且该序列必须满足下面两个条件:

  • 每个顶点出现且只出现一次。
  • 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
  • 有向无环图(DAG)才有拓扑排序

度数: 由一个顶点出发,有几条边就称该顶点有几度,或者该顶点的度数是几
出度: 由一个顶点出发的边的总数
入度: 指向一个顶点的边的总数

拓扑排序使用深度优先算法,时间复杂度为O ( V + E )

拓扑排序通常有几种实现方式:

2.1 入度表(直接遍历)

【算法基础】拓扑排序及实战
于是,得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。
通常,一个有向无环图可以有一个或多个拓扑排序序列。

2.2 通过DFS(深度)和栈实现

思路:

找到顶点,递归遍历到最后的结点,通过回溯将遍历到的点入栈,那么先进栈的必定是只有入度的结点,只有出度的结点必定在最后进栈,最后通过出栈可以得到排序后的顺序。

具体代码请看 实战 2

2.3 通过队列实现

思路:

  • 通过遍历,将所有入度为0的进入队列。并将与之相连的结点的入度-1。
  • 然后一个一个的出队列,出队列的同时判断与出队列结点相连的结点是否入度为0,为0则进栈。
  • 循环第一二步,直到所有节点被选择或者栈空。(其实栈空的时候,所有节点就是被选择了)

不废话,直接上代码:

/**
 * 图的存储
 * 邻接矩阵 二维数组
 */
public static class GrapMatrix {


    /**
     * 节点个数
     */
    public int size;

    /**
     * 顶点名称
     */
    char [] nodeName;

    /**
     * 排序后的顺序
     */
    List result;

    /**
     * 图关系矩阵
     */
    int [][] matrix;

    /**
     *
     * @param nodeName 节点
     * @param edgs 节点关系
     */
    public GrapMatrix(char[] nodeName, char[][] edgs) {
        size = nodeName.length;
        this.nodeName = nodeName;
        // 设置图关系矩阵大小
        this.matrix = new int[size][size];
        result = new ArrayList<Integer>();

        // 初始化图关系矩阵
        for (char[] node: edgs) {
            matrix[getPosition(node[0])][getPosition(node[1])] = 1;
            System.out.println(node);
        }

        // 输出图的邻接矩阵
        for(int i = 0; i < size; i ++) {
            for (int j = 0; j < size; j ++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println("");
        }
    }

    // 排序
    public void tuopuSort() {
        System.out.println("\n");
        // 一个一维数组,用来保存顶点的入度
        int indegree[] = new int[size];
        boolean indegreeV[] = new boolean[size];


        // 给入度输入值
        for(int i = 0; i < size; i ++) {
            indegreeV[i] = false;
            for (int j = 0; j < size; j ++) {
                if (matrix[i][j] == 1) {
                    indegree[j] = indegree[j] + 1;
                }
            }
        }
        System.out.println("\n");

        //开始进行遍历
        LinkedList<String> nodes = new LinkedList<String>();

        // 将入度为 0 的节点入队列
        for (int x = 0; x < size; x ++) {
            if (indegree[x] == 0) {
                System.out.println(nodeName[x]);
                nodes.add(String.valueOf(nodeName[x]));
            }
        }

        int j = 0;
        while (!nodes.isEmpty()) {
            for (int x = 0; x < size; x ++) {
                System.out.println("\n 数组 x = " + x + ", ");
                if (indegree[x] == 0 && !indegreeV[x]) {

                    indegreeV[x] = true;
                    String s = nodes.poll();
                    System.out.println("add = " +s);
                    result.add(s);

                    // 找到跟它相关的节点,,入度 -1
                    for (int y = 0; y < size; y ++) {
                        if (matrix[x][y] == 1) {
                            System.out.println("相关的节点 -1 = " + y);
                            indegree[y] = indegree[y] - 1;
                            if (indegree[y] == 0) {
                                System.out.println("相关的节点 -1 后, 入度为0, " + nodeName[y]);
                                nodes.add(String.valueOf(nodeName[y]));
                            }
                        }
                    }
                } else {

                }
            }
            j ++;
        }


        System.out.println(result);

    }

    public int getPosition(char pos) {
        for (int i = 0; i < nodeName.length; i ++) {
            if (nodeName[i] == pos) {
                return i;
            }
        }
        return -1;
    }
}

三、实战

应用:
拓扑排序通常用来“排序”具有依赖关系的任务。
eg: 关键路径
选课系统
等这些任务有先后顺序的图。

      比如,要想升职加薪,就要先拍马屁

3.1 选课系统

我们现在以课程排序来做代码测试,
假定一个计算机专业的学生必须完成下图所列出的全部课程。
在这里,课程代表活动,学习一门课程就表示进行一项活动,学习每门课程的先决条件是学完它的全部先修课程。
【算法基础】拓扑排序及实战
我们用图的方式,将他们的先后顺序及依赖关系表示如下:
【算法基础】拓扑排序及实战
对于—> 图 的存储结构,常用的是"邻接矩阵"和"邻接表",

拓扑排序的动态表示
https://www.cs.usfca.edu/~galles/visualization/TopoSortIndegree.html

3.2 Android冷启动优化,有向无环图启动器

Application中初始化应用所需的业务、工具、UI等组件,导致耗时,导致冷启动会比较慢,需要进行优化处理,
【算法基础】拓扑排序及实战
我们要做的就是把主线程的串行任务变成并发任务,在将所有任务整理出来后,进行一个排序,

1、每一个业务模块当成一个任务,再梳理任务之间的关系。有的必须要在所以任务之前初始化,有的必须要在主线程初始化,有的可以有空在初始化,有的必须要在有的任务执行完毕再初始化,将这些任务的先后顺序及依赖关系用图画出来。
【算法基础】拓扑排序及实战

主进程执行, eg:推送,就不需要判断进程
主线程执行,eg:有的要主线程,有的要子线程

2、代码Task化,启动逻辑抽象为Task;
3、根据所有任务依赖关系排序生成一个有向无环图;
4、多线程按照排序后的优先级依次执行

关健代码文章来源地址https://www.toymoban.com/news/detail-479719.html

public class AppStartTaskSortUtil {
    /**
     * 拓扑排序
     * taskIntegerHashMap每个Task的入度(key= Class < ? extends AppStartTask>)
     * taskHashMap每个Task            (key= Class < ? extends AppStartTask>)
     * taskChildHashMap每个Task的孩子  (key= Class < ? extends AppStartTask>)
     * deque 入度为0的Task
     */
    public static List<AppStartTask> getSortResult(List<AppStartTask> startTaskList, HashMap<Class<? extends AppStartTask>, AppStartTask> taskHashMap, HashMap<Class<? extends AppStartTask>, List<Class<? extends AppStartTask>>> taskChildHashMap) {
        List<AppStartTask> sortTaskList = new ArrayList<>();
        HashMap<Class<? extends AppStartTask>, TaskSortModel> taskIntegerHashMap = new HashMap<>();
        Deque<Class<? extends AppStartTask>> deque = new ArrayDeque<>();
        for (AppStartTask task : startTaskList) {
            if (!taskIntegerHashMap.containsKey(task.getClass())) {
                taskHashMap.put(task.getClass(), task);
                taskIntegerHashMap.put(task.getClass(), new TaskSortModel(task.getDependsTaskList() == null ? 0 : task.getDependsTaskList().size()));
                taskChildHashMap.put(task.getClass(), new ArrayList<Class<? extends AppStartTask>>());
                //入度为0的队列
                if (taskIntegerHashMap.get(task.getClass()).getIn() == 0) {
                    deque.offer(task.getClass());
                }
            } else {
                throw new RuntimeException("任务重复了: " + task.getClass());
            }
        }
        //把孩子都加进去
        for (AppStartTask task : startTaskList) {
            if (task.getDependsTaskList() != null) {
                for (Class<? extends AppStartTask> aclass : task.getDependsTaskList()) {
                    taskChildHashMap.get(aclass).add(task.getClass());
                }
            }
        }
        //循环去除入度0的,再把孩子入度变成0的加进去
        while (!deque.isEmpty()) {
            Class<? extends AppStartTask> aclass = deque.poll();
            sortTaskList.add(taskHashMap.get(aclass));
            for (Class<? extends AppStartTask> classChild : taskChildHashMap.get(aclass)) {
                taskIntegerHashMap.get(classChild).setIn(taskIntegerHashMap.get(classChild).getIn() - 1);
                if (taskIntegerHashMap.get(classChild).getIn() == 0) {
                    deque.offer(classChild);
                }
            }
        }
        if (sortTaskList.size() != startTaskList.size()) {
            throw new RuntimeException("出现环了");
        }
        return sortTaskList;
    }
}

到了这里,关于【算法基础】拓扑排序及实战的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法学习系列(二十一):拓扑排序

    这个拓扑排序大家应该都听说过,用的地方也是很多,考研和面试也是经常考,其实这个排序算法的思想比较简单,应用的话就是可以用来判断一个图中是否存在一个环,本文主要是介绍拓扑排序的思想,以及一个简单的模板题,来帮助了解什么是拓扑排序,以及怎么写。

    2024年01月16日
    浏览(49)
  • 拓扑排序 (算法思想+图解+模板+练习题)

    有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。 无向图没有拓扑序列。 首先我们先来解释一下什么是有向无环图: 有向就是我们两个结点之间的边是有方向的,无环的意思就是整个序列中没有几个结点通过边形成一个圆环。 下图就是一个有向无环图,它也一定

    2024年02月03日
    浏览(70)
  • 探索经典算法 拓扑排序,字符串匹配算法,最小生成树

    拓扑排序、字符串匹配算法和最小生成树是计算机科学中常用的数据结构和算法,它们在解决各种实际问题中具有重要的应用价值。在本文中,我将详细介绍这三个主题,并提供相应的示例代码和应用场景,以帮助读者更好地理解和应用这些概念。 一、拓扑排序: 拓扑排序

    2024年02月05日
    浏览(52)
  • 有向无环图的拓扑排序理解和算法

    有向无环图的拓扑排序理解和算法 有向无环图(DAG)定义 引用子维基百科的DAG定义, 在数学中,尤其是图论和计算机科学中,DAG是一类不含环的有向图(In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles). 对比之前的有向图

    2024年02月04日
    浏览(45)
  • 【数据结构与算法】图的遍历与拓扑排序

    再上一篇中我们讲了树的两种存储方式:【数据结构与算法】图——邻接表与邻接矩阵 这一篇我们可以用数组来模拟邻接表。 假设现在我们要进行n次操作,实现无向图。 首先需要一个 保存是哪个节点 的数组 e 然后就是类似指针数组的 表 h ,每个表都会连一串单链表 e,ne

    2024年02月04日
    浏览(46)
  • 算法沉淀——BFS 解决拓扑排序(leetcode真题剖析)

    Breadth-First Search (BFS) 在拓扑排序中的应用主要是用来解决有向无环图(DAG)的拓扑排序问题。拓扑排序是对有向图中所有节点的一种线性排序,使得对于每一条有向边 (u, v),节点 u 在排序中都出现在节点 v 的前面。如果图中存在环路,则无法进行拓扑排序。 BFS 解决拓扑排序

    2024年02月21日
    浏览(40)
  • Peter算法小课堂—拓扑排序与最小生成树

    讲拓扑排序前,我们要先了解什么是DAG树。所谓DAG树,就是指“有向无环图”。请判断下列图是否是DAG图 第一幅图,它不是DAG图,因为它形成了一个环。第二幅图,它也不是DAG图,因为它没有方向。第三幅图才叫真正的DAG图(DAG图不一定联通)。 那什么叫DAG图的拓扑排序呢

    2024年01月21日
    浏览(49)
  • python算法与数据结构(搜索算法和拓扑排序算法)---深度优先搜索

    了解树/图的 深度遍历,宽度遍历 基本原理; 会使用python语言编写 深度遍历,广度遍历 代码; 掌握 拓扑排序算法 搜索引擎 提到搜索两个子,大家都应该会想到搜索引擎,搜索引擎的基本工作步骤; 网页爬取 — 数据预处理 — 排序 — 查询 第一步,网页爬取,非常重要,

    2024年01月20日
    浏览(51)
  • 【C++算法模板】图论-拓扑排序,超详细注释带例题

    推荐视频链接:D01 拓扑排序 给定一张 有向无环图 ,排出所有顶点的一个序列 A A A 满足:对于图中的每条有向边 ( x , y ) (x,y) ( x , y ) , x x x 在 A A A 中都出现在 y y y 之前,则称 A A A 是该图的顶点的一个拓扑序 拓扑排序 可以判断有向图中是否有环,可以生成拓扑序列 对于下

    2024年04月15日
    浏览(41)
  • 采用DFS算法实现逆拓扑排序,并判断是否有回路

    看王道视频的时候,有一道思考题,没有找到理想的答案,所以自己思考了一下,记录一下。 问题问的是:在采用DFS算法实现AOV网的逆拓扑排序时如何判断是否有回路? 首先,要理解,在采用DFS算法(深度优先搜索)实现AOV网的拓扑排序,其本质上是对AOV网的DFS生成森林进行

    2024年02月12日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包