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

目录

 一、原理

1. 引例:207.课程表

 2. 应用场景

3. 代码思路

二、代码模板

三、练习

1、210.课程表Ⅱ🟢

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

3、310.最小高度树 🟡


 一、原理

1. 引例:207.课程表

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

 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入度-1if (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 所在列的左边。

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

示例:

输入: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))被称为 最小高度树 。

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

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

示例:

输入: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;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/105795.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【android12-linux-5.1】【ST芯片】HAL移植后没调起来

ST传感器芯片HAL按官方文档移植后&#xff0c;测试一直掉不起来&#xff0c;加的日志没出来。经过分析&#xff0c;是系统自带了一个HAL&#xff0c;影响的。 按照官方文档&#xff0c;移植HAL后&#xff0c;在/device/<vendor\>/<board\>/device.mk*路径增加PROD…

Goland 配置go modules 环境变量

我的配置&#xff0c;仅供参考&#xff1a; GOPROXYhttps://goproxy.cn,direct;GO111MODULEon;GOSUMDBoff;GONOSUMDB*

【业务功能篇82】微服务SpringCloud-ElasticSearch-Kibanan-docke安装-进阶实战

四、ElasticSearch进阶 https://www.elastic.co/guide/en/elasticsearch/reference/7.4/getting-started-search.html 1.ES中的检索方式 在ElasticSearch中支持两种检索方式 通过使用REST request URL 发送检索参数(uri检索参数)通过使用 REST request body 来发送检索参数…

iOS HealthKit 介绍

文章目录 一、简介二、权限配置1. 在开发者账号中勾选HealthKit2. 在targets的capabilities中添加HealthKit。3. infoPlist需要配置权限 三、创建健康数据管理类1. 引入头文件2. 健康数据读写权限3. 检查权限4. 读取步数数据5. 写入健康数据 四、运行获取权限页面 一、简介 He…

1 Hadoop入门

1.Hadoop是什么&#xff1f; (1)Hadoop是一个由Apache基金会所开发的分布式系统基础架构。 (2)主要解决&#xff0c;海量数据的存储和海量数据的分析计算问题。 (3)广义上来说&#xff0c;Hadoop通常是指一个更广泛的概念——Hadoop生态圈 2.Hadoop的优势 3 Hadoop组成 4 HDF…

DevOps之自动化测试

什么是自动化测试&#xff1f; 明确一下自动化测试不是什么。自动化测试不是指自动化生成测试代码&#xff0c;而是自动化地执行由开发人员或测试人员编写的测试代码。正如下面这句谚语&#xff1a;“绝不要手工去做任何可以被自动化处理的事情。——Curt Hibbs” 之前是由人…

【C++】—— c++11新的类功能

目录 &#xff08;一&#xff09;默认成员函数 1、 移动构造函数 2、代码辅助理解 3、移动赋值运算符重载 &#xff08;二&#xff09;default关键字 &#xff08;三&#xff09;delete关键字 &#xff08;四&#xff09;委托构造函数 1、优势 2、缺点 总结 &#x…

ubuntu学习(四)----文件写入操作编程

1、write函数的详解 ssize_t write(int fd,const void*buf,size_t count); 参数说明&#xff1a; fd:是文件描述符&#xff08;write所对应的是写&#xff0c;即就是1&#xff09; buf:通常是一个字符串&#xff0c;需要写入的字符串 count&#xff1a;是每次写入的字节数…

vue中实现echarts三维散点图

需要安装 echarts 同时引入 echarts-gl 我安装的版本&#xff1a; "echarts": "^5.3.2", "echarts-gl": "^2.0.9", import Vue from "vue"; import * as echarts from "echarts"; Vue.prototype.$echarts echa…

温故知新之:代理模式,静态代理和动态代理(JDK动态代理)

0、前言 代理模式可以在不修改被代理对象的基础上&#xff0c;通过扩展代理类&#xff0c;进行一些功能的附加与增强。 1、静态代理 静态代理是一种代理模式的实现方式&#xff0c;它在编译期间就已经确定了代理对象&#xff0c;需要为每一个被代理对象创建一个代理类。静态代…

36、springboot --- 对 tomcat服务器 和 undertow服务器 配置访客日志

springboot 配置访客日志 ★ 配置访客日志&#xff1a; 访客日志&#xff1a; Web服务器可以将所有访问用户的记录都以日志的形式记录下来&#xff0c;主要就是记录来自哪个IP的用户、在哪个时间点、访问了哪个资源。 Web服务器可将所有访问记录以日志形式记录下来&#xff…

VMware 修改ip地址 虚拟机静态ip设置 centos动态ip修改为静态ip地址 centos静态ip地址 vmware修改ip地址

虚拟机的centos服务器经常变换ip&#xff0c;测试起来有些麻烦&#xff0c;故将动态ip修改为静态ip 1. 查看vmware 虚拟机网络配置&#xff1a; 点击编辑&#xff0c;打开虚拟网络配置 2. 选中nat模式&#xff0c;点击nat设置&#xff0c;最终获取网关ip: 192.168.164.2 3. 进…

CleanMyMac2024永久版Mac清理工具

Mac电脑作为相对封闭的一个系统&#xff0c;它会中毒吗&#xff1f;如果有一天Mac电脑产生了疑似中毒或者遭到恶意不知名攻击的现象&#xff0c;那又应该如何从容应对呢&#xff1f;这些问题都是小编使用Mac系统一段时间后产生的疑惑&#xff0c;通过一番搜索研究&#xff0c;小…

CK-GW06-E03与汇川PLC的EtherNet/IP通信

准备阶段&#xff1a; CK-GWO6-E03网关POE交换机网线汇川PLC编程软件汇川AC801-0221-U0R0型号PLC 1.打开汇川PLC编程软件lnoProShop(V1.6.2)SP2 新建工程&#xff0c;选择对应的PLC型号&#xff0c;编程语言选择为“结构化文本&#xff08;ST&#xff09;语言”&#xff0c;然…

线性代数(五) 线性空间

前言 《线性代数(三) 线性方程组&向量空间》我通过解线性方程组的方式去理解线性空间。此章从另一个角度去理解 空间是什么 大家较熟悉的&#xff1a;平面直角坐标系是最常见的二维空间 空间由无穷多个坐标点组成 每个坐标点就是一个向量 反过来&#xff0c;也可说&…

kafka--技术文档--架构体系

架构体系 Kafka的架构体系包括以下几个部分&#xff1a; Producer. 消息生产者&#xff0c;就是向Kafka broker发送消息的客户端。Broker. 一台Kafka服务器就是一个Broker。一个集群由多个Broker组成。一个Broker可以容纳多个Topic。Topic. 可以理解为一个队列&#xff0c;一…

Oracle 如何给大表添加带有默认值的字段

一、讲故事 你是否遇到过开发人员添加字段&#xff0c;导致数据库锁表问题&#xff1f; 但是令开发疑惑的事&#xff0c;他们添加字段&#xff0c;有的时候很快&#xff0c;有的时候很慢&#xff1f; 为什么呢&#xff1f; 询问得知&#xff0c;**加的慢时候是带上了default默…

【洛谷】P2440 木材加工

原题链接&#xff1a;https://www.luogu.com.cn/problem/P2440 1. 题目描述 2. 思路分析 整体思路&#xff1a;二分答案 设置一个变量longest来记录最长木头的长度&#xff0c;sum记录切成的小段数量之和。 令左边界l0&#xff0c;右边界llongest。 写一个bool类型的check…

【云原生】Docker的数据管理(数据卷、容器互联)

目录 一、数据卷&#xff08;容器与宿主机之间数据共享&#xff09; 二、数据卷容器&#xff08;容器与容器之间数据共享&#xff09; 三、 容器互联&#xff08;使用centos镜像&#xff09; 总结 用户在使用Docker的过程中&#xff0c;往往需要能查看容器内应用产生的数据…

联合注入步骤

使用场景&#xff1a; 有回显&#xff0c;可以看到某些字段的回显信息 像下面的有具体的回显信息 一、判断注入位点 在原始的id&#xff08;参数&#xff09;的输入后面添加额外的条件 如果and 11 有结果&#xff0c;and10没有结果输出&#xff0c; 就说明我们添加的额外条件…