⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用

这篇具有很好参考价值的文章主要介绍了⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

 一、原理

1. 引例:207.课程表

 2. 应用场景

3. 代码思路

二、代码模板

三、练习

1、210.课程表Ⅱ🟢

2、2392.给定条件下构造举证🟡

3、310.最小高度树🟡

4、 2603.收集树中金币 🔴


 一、原理

1. 引例:207.课程表

就如大学课程安排一样,如果要学习数据结构与算法、机器学习这类课程,肯定要先学习C语言、Python、离散数学、概率论等等,我们将类似的“推导”关系建如下有向简单图⬇️

⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用,进阶算法,算法,图论

 2. 应用场景

根据节点的入度大小,拓扑排序主要用于处理先后问题(拓扑序列),以及判断图中是否有环的问题;

3. 代码思路

用大小为节点个数的数组记录每个节点的入度,用队列存放入度为0的节点,遍历这些节点,将这些节点指向的节点的入度-1,最后在记录入度减为0的节点,重复上述步骤;

①拓扑序列:在循环过程中向一数组中push入度为0的节点,排在数组前的节点即为入度先被减为0的节点;

②是否存在环:若拓扑序列数组大小等于节点总个数则说明图中无环;反之,这说明图有环

二、代码模板

/*这里用课程表一题的代码当作模板*/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        int in_degree[numCourses];   //记录节点的入度
        memset(in_degree, 0, sizeof(in_degree));
        for (auto& e : prerequisites) {
            int x = e[0], y = e[1];    //建图
            g[x].push_back(y);
            in_degree[y]++;     // x -> y ,则y节点入度+1
        }
        vector<int> order;
        queue<int> q;
        for(int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);    //将入度为0的节点加入到队列中
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            order.push_back(x);    //push到拓扑序列中
            for (auto y : g[x]) {
                in_degree[y]--;     //x -> y , 即将y入度-1
                if (in_degree[y] == 0) q.push(y);
            }
        }
        return order.size() == numCourses;   //判断是否有环
    }
};

三、练习

1、210.课程表Ⅱ🟢

现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。

  • 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完成所有课程,返回 一个空数组 。

示例:

输入:numCourses = 2, prerequisites = [[1,0]]
输出:[0,1]
解释:总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。

解题思路: 与课程表Ⅰ思路基本一样,依次取出入度为0的节点加入到答案数组中,若数组大小与总结点个数不相同,则说明图中有环,返回空数组。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(numCourses);
        int in_degree[numCourses];
        memset(in_degree, 0, sizeof(in_degree));
        for (auto& e : prerequisites) {
            int x = e[1], y = e[0];
            g[x].push_back(y);
            in_degree[y]++;
        }
        vector<int> order;
        queue<int> q;
        for(int i = 0; i < numCourses; i++) if (in_degree[i] == 0) q.push(i);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            order.push_back(x);
            for (auto y : g[x]) {
                in_degree[y]--;
                if (in_degree[y] == 0) q.push(y);
            }
        }
        return order.size() == numCourses ? order : vector<int>();
    }
};

2、2392.给定条件下构造举证🟡

给你一个  整数 k ,同时给你:

  • 一个大小为 n 的二维整数数组 rowConditions ,其中 rowConditions[i] = [abovei, belowi] 
  • 一个大小为 m 的二维整数数组 colConditions ,其中 colConditions[i] = [lefti, righti] 。

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵,1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件:

  • 对于所有 0 到 n - 1 之间的下标 i ,数字 abovei 所在的  必须在数字 belowi 所在行的上面。
  • 对于所有 0 到 m - 1 之间的下标 i ,数字 lefti 所在的  必须在数字 righti 所在列的左边。

返回满足上述要求的 任意 矩阵。如果不存在答案,返回一个空的矩阵。

示例:

⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用,进阶算法,算法,图论

输入:k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出:[[3,0,0],[0,0,1],[0,2,0]]
解释:上图为一个符合所有条件的矩阵。
行要求如下:
- 数字 1 在第 1 行,数字 2 在第 2 行,1 在 2 的上面。
- 数字 3 在第 0 行,数字 2 在第 2 行,3 在 2 的上面。
列要求如下:
- 数字 2 在第 1 列,数字 1 在第 2 列,2 在 1 的左边。
- 数字 3 在第 0 列,数字 2 在第 1 列,3 在 2 的左边。
注意,可能有多种正确的答案。

解题思路:该题很明显是处理先后的问题,我们分别处理行与列,分别得到行与列拓扑序列,最后通过一个数组转换,将下标作为节点,对应的值作为该节点位于行/列的位置;

class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> roworder, colorder;
        function<bool(vector<vector<int>>&, vector<int>&)> topo_sort = [&](vector<vector<int>>& edge, vector<int>& order) -> bool{
            vector<vector<int>> g(k);
            int in_deg[k];
            memset(left, 0, sizeof(left));
            for (auto& e : edge) {
                int x = e[0]-1, y = e[1] - 1;
                g[x].push_back(y);
                in_deg[y]++;
            }

            queue<int> q;
            for(int i = 0; i < k; i++) if (in_deg[i] == 0) q.push(i);
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                order.push_back(x);
                for (auto y : g[x]) {
                    in_deg[y]--;
                    if (in_deg[y] == 0) q.push(y);
                }
            }
            return order.size() == k;
        };

        vector<vector<int>> ans(k, vector<int>(k, 0));
        if (!topo_sort(rowConditions, roworder) || !topo_sort(colConditions, colorder)) return {};
        int row[k], col[k];
        for (int i = 0; i < k; i++) {
            row[roworder[i]] = i;
            col[colorder[i]] = i;
        }
        for (int i = 0; i < k; i++) {
            ans[row[i]][col[i]] = i + 1;
        }
        return ans;
    }
};

3、310.最小高度树🟡

树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表(每一个边都是一对标签),其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时,设结果树的高度为 h 。在所有可能的树中,具有最小高度的树(即,min(h))被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

示例:

⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用,进阶算法,算法,图论

输入:n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出:[3,4]

解题思路: 本题思路较为复杂,可以大致理解为贪心,证明过程可以参考力扣官方答案。每次去掉节点入度最小的节点,到最后剩余1-2个节点即为可以作为最小高度树的根节点

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        unordered_map<int, vector<int>> g;
        vector<int> degree(n);
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
            degree[x]++;
            degree[y]++;
        }        

        vector<int> ans;
        queue<int> q;
        for (int i = 0; i < n; i++) if (degree[i] == 1) q.push(i);
        while(!q.empty()) {
            vector<int> tmp;
            int size = q.size();
            while(size--) {
                int x = q.front();
                q.pop();
                tmp.push_back(x);
                for(auto y : g[x]) {
                    if (--degree[y] == 1) q.push(y);
                }
            }
            ans = move(tmp);
        }
        return ans;
    }
};

4、2603.收集树中金币 🔴

给你一个 n 个节点的无向无根树,节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ,其中 coins[i] 可能为 0 也可能为 1 ,1 表示节点 i 处有一个金币。

一开始,你需要选择树中任意一个节点出发。你可以执行下述操作任意次:

  • 收集距离当前节点距离为 2 以内的所有金币,或者
  • 移动到树中一个相邻节点。

你需要收集树中所有的金币,并且回到出发节点,请你返回最少经过的边数。

如果你多次经过一条边,每一次经过都会给答案加一。

示例 1:

⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用,进阶算法,算法,图论

输入:coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出:2
解释:从节点 0 出发,收集节点 4 和 3 处的金币,移动到节点 2 处,收集节点 7 处的金币,移动回节点 0 。

 解题思路:

步骤1: 持续删除没有金币的子树,若该子树没有金币,那么也就没有必要访问这个子树的所有节点(拓扑排序思路,记录各个节点的入度)

⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用,进阶算法,算法,图论

步骤2: 因为可以从一个节点查询到离该节点距离为2的所有节点,所以可以将这些可以其他节点间接访问的节点删除;通过连续两次循环,将每次入度为1的叶子节点删除。

⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用,进阶算法,算法,图论

 步骤3: 通过上述两个步骤,剩余节点的叶子节点为必须被访问的节点,易证得,从任意节点开始访问所有剩余叶子节点并返回最初节点所经过得边数均为最后这颗树(通过步骤1、2删除节点之后的树)的边数的两倍。文章来源地址https://www.toymoban.com/news/detail-671362.html

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        vector<vector<int>> g(n);
        //拓扑排序所用的记录入度的数组,在后面的循环中可以得知,入度减为-1的节点即为删除的节点
        vector<int> indegree(n);         
        for (auto& e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y); g[y].push_back(x);
            indegree[x]++; indegree[y]++;
        }

        //步骤1
        queue<int> q;
        for (int i = 0; i < n; i++) if (coins[i] == 0 && indegree[i] == 1) q.push(i);
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            indegree[x]--;
            for (auto y : g[x]) {
                indegree[y]--;
                若当y为当前树的叶子节点且没有金币,则加入队列中,继续循环删除
                if (indegree[y] == 1 && coins[y] == 0) q.push(y);  
            }
        }

        //步骤2
        for(int i = 0; i < n; i++) if (coins[i] == 1 && indegree[i] == 1) q.push(i);
        int t = 2;
        while(t--) {
            int size = q.size();
            while(size--) {
                int x = q.front();
                q.pop();
                indegree[x]--;
                for (auto y : g[x]) {
                    indegree[y]--;
                    if (indegree[y] == 1) q.push(y);
                }
            }
        }

        //步骤3:
        int st = -1;    //寻找dfs的入口
        for (int i = 0; i < n; i++) if (indegree[i] > 0) {
            st = i;
            break;
        }
        vector<int> vis(n, 0);
        int ans = 0;
        function<void(int)> dfs = [&](int x) -> void {
            vis[x] = true;
            for (auto y : g[x]) {
                if (indegree[y] > 0 && !vis[y]) {        //indegree[i] <= 0 表示该节点已删除
                    vis[y] = true;
                    ans++;
                    dfs(y);
                }
            }
        };
        if (st != -1) dfs(st);
        return ans * 2;
    }
};

到了这里,关于⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 图论应用——拓扑排序

    拓扑排序的原理和宽度优先搜索差不多

    2024年04月26日
    浏览(56)
  • 【图论】拓扑排序

     拓扑排序是一种对有向无环图(DAG)进行排序的算法,使得图中的每个顶点在排序中都位于其依赖的顶点之后。它通常用于表示一些任务之间的依赖关系,例如在一个项目中,某些任务必须在其他任务之前完成。 拓扑排序的步骤如下: 找到入度为0的顶点:入度是指指向某

    2024年02月11日
    浏览(38)
  • 第三章 图论 No.13拓扑排序

    拓扑序和DAG有向无环图联系在一起,通常用于最短/长路的线性求解 裸题:1191. 家谱树 1191. 家谱树 - AcWing题库 差分约束+拓扑排序:1192. 奖金 1192. 奖金 - AcWing题库 由于图中所有边权都是正数,可以直接使用topsort求解差分约束问题 根据题意,要求一个最小值,使用最长路求解

    2024年02月12日
    浏览(45)
  • Sorting Algorithms in Python (排序算法)

    本篇文章主要介绍几种经典排序算法:冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、桶排序和基数排序。并给出用python实现的算法代码。 目录 一、冒泡排序 二、快速排序 三、选择排序 四、堆排序 五、插入排序 六、希尔排序 七、归并排序 八

    2024年04月15日
    浏览(42)
  • 十大排序算法(Top 10 Sorting Algorithms)

    十种常见排序算法可以分为两大类: 比较类排序 :通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。 非比较类排序 :不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因

    2024年02月08日
    浏览(46)
  • 【LeetCode 热题 100】图论 专题(bfs,拓扑排序,Trie树 字典树)

    from: https://leetcode.cn/studyplan/top-100-liked/ bfs 具有 边权为1 的最短路性质 拓扑排序,入度 Trie树, 高效存储 字符串【见鬼,不知道为什么写错,需要掌握熟练度】 dfs 写法,比较简洁 bfs 写法,有最短路性质 bfs 具有 边权为1 的最短路性质 拓扑排序 模板题 数组写法,简洁,需

    2024年02月13日
    浏览(52)
  • 搜索与图论(一)(深搜,广搜,树与图的存储遍历,拓扑排序)

    往深里搜,搜到叶子结点那里,回溯,到可以继续到叶子结点深搜的位置。 1、回溯一定要恢复现场 2、定义一个与当前递归层数有关的终止条件(题目要求的东西) 3、每层都用循环判断是否存在可以dfs的路 输出数字组合 全排列的思想解决n皇后问题,用三个bool数组描述限制

    2024年02月19日
    浏览(50)
  • C语言-算法-拓扑排序

    有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列,使得每个人的后辈都比那个人后列出。 第 1 1 1 行一个整数 N N N ( 1 ≤ N ≤ 100 1 le N le 100 1 ≤ N ≤ 100 ),表示家族的人数。接下来 N N N 行,第 i i i 行描述第 i i i

    2024年01月25日
    浏览(40)
  • 【算法基础】拓扑排序及实战

    这里涉及到图的概念,感兴趣的同学请移驾 –图– 下面还有两个相关概念,大概说一下: 定义:在图论中,如果一个有向图从任意顶点出发无法经过若干条边回到该点,则这个图是一个 有向无环图(DAG,Directed Acyclic Graph) 每条边都带有从一个顶点 指向另一个顶点 的方向

    2024年02月08日
    浏览(78)
  • 算法沉淀——拓扑排序

    首先我们需要知道什么是拓扑排序? 在正式讲解拓扑排序这个算法之前,我们需要了解一些前置知识(和离散数学相关) 1、有向无环图: 指的是一个无回路的有向图。 入度:有向图中某点作为图中边的终点的次数之和 出度:有向图中某点作为图中边的起点的次数之和 2、

    2024年04月09日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包