面试题-DAG 有向无环图

article2024/11/24 23:40:21/文章来源:https://blog.csdn.net/zhaoyqcsdn/article/details/135416540

有向无环图用于解决前后依赖问题，在Apollo中用于各个组件的依赖管理。

在算法面试中，有很多相关题目

比如排课问题，有先修课
比如启动问题，需要先启动1，才能启动2

概念

在这里插入图片描述

顶点：

图中的一个点，比如顶点 1，顶点 2。
边：连接两个顶点的线段叫做边，edge。

入度：

代表当前有多少边指向它。

解题思路

以课程表问题为例，
需要先修的课程在前，作为key，后修的课程在后，作为value
先构建有向无环图
然后再进行深度或广度优先遍历
所有节点都能遍历到，就是所有课程都能学完

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

shell exit和return的区别

exit和return的区别 exit 可放在shell脚本中任意位置。表示随时结束运行程序的这个进程，并删除进程使用的内存空间，同时把错误信息返回给父进程。 return 是调用堆栈的返回，返回函数值并退出函数，一般用在函数方法体内。 [Ref]…

编译原理-2022期末考试解析

【前言】这是2022年的期末考试卷，题目还是比较正的，涵盖了词法分析，语法分析，语法制导翻译，优化。从这一年开始，优化的部分分值开始提高（这是最后学的部分）。一、词法分析&#xf…

数学经典教材有什么？

有本书叫做《自然哲学的数学原理》，是牛顿写的，读完之后你就会感叹牛顿的厉害之处! 原文完整版PDF：https://pan.quark.cn/s/5d5eac2e56af 那玩意真的是人写出来的么… 现代教材把牛顿力学简化成三定律，当然觉得很简单。只有读了原…

GNSS最终、快速、超快速星历下载地址汇总

GNSS最终、快速、超快速星历下载地址汇总 igs综合产品 ftp://cddis.gsfc.nasa.gov/pub/gps/products GPS单系统 igs 最终产品 igr 快速产品（rapid） igu 超快速产品（Ultra Rapid） ftp://cddis.gsfc.nasa.gov/pub/glonass/produc…

从学习投研流程的角度学习Qlib

许多同学只是把Qlib当做一个简单的工具来学习。其实Qlib隐含了一套正规的投研流程，从投研流程的视角去学习Qlib,则不仅能加深对Qlib的理解，而且能够掌握正确的投研流程，哪怕以后不使用Qlib而是使用其他系统了，这套流程还是适用的。…

React之自定义路由组件

开篇 react router功能很强大，可以根据路径配置对应容器组件。做到组件的局部刷新，接下来我会基于react实现一个简单的路由组件。代码自定义路由组件 import {useEffect, useState} from "react"; import React from react // 路由配置 e…

基于Springboot的课程答疑系统（有报告）。Javaee项目，springboot项目。

演示视频： 基于Springboot的课程答疑系统（有报告）。Javaee项目，springboot项目。项目介绍： 采用M（model）V（view）C（controller）三层体系结构&…

（25）Linux IPC 进程间通信系统调用:pipe接口

一、进程间通信（IPC） 1、为什么要进程间通信？ 我们在之前讲过 "进程之间是具有独立性" 的，如果进程间想交互数据，成本会非常高！ 因为独立性之本质即 "封闭"，进程们你封闭…

极客时间-读多写少型缓存设计

背景内容是极客时间-徐长龙老师的高并发系统实战课的个人学习笔记，欢迎大家学习！https://time.geekbang.org/column/article/596644 总览内容如下： 缓存性价比一般来说，只有热点数据放到缓存才更有价值数据量查询频率命中…

2000-2021年全国各省环境相关指标数据（890+指标）

2000-2021年全国各省环境相关指标数据（890指标） 1、指标时间：2000-2021年 2、范围：31省市 3、来源：2001-2022年环境统计年鉴 4、指标：工业废水排放总量、工业废水排放达标量、工业废水处理量、化学需氧…

// GetWeekTimeCycleForGBT74082005 获取星期周期中华人民共和国国家标准 GB/T 7408-2005 // 参数 year 年份 GB/T 7408-2005 func GetWeekTimeCycleForGBT74082005(year int) (*[]TimeCycle, error) {var yearstart time.Time //当年最开始一天var yearend time.Time //当年…

Python知识点（史上最全）

Python期末考试知识点（史上最全） python简介 Python是一种解释型语言 Python使用缩进对齐组织代码执行，所以没有缩进的代码，都会在载入时自动执行数据类型：整形 int 无限大浮点型 float…

Javaweb之SpringBootWeb案例开发规范的详细解析

1.2 开发规范了解完需求也完成了环境搭建了，我们下面开始学习开发的一些规范。开发规范我们主要从以下几方面介绍： 1、开发规范-REST 我们的案例是基于当前最为主流的前后端分离模式进行开发。在前后端分离的开发模式中，前后端开发人员…

Vue3 父事件覆盖子事件，Vue2 的 v-on=“$listeners“ 的替代方案

在 Vue3 中，$listeners 被删除子组件代码，需要特别注意的是事件名为 on 开头，例如 onBack。不确定的可以通过给父组件传递事件或属性，再打印子组件的 attrs useAttrs()，来确定传值 // template v-bind"newA…

Netty-Netty组件了解

EventLoop 和 EventLoopGroup 回想一下我们在 NIO 中是如何处理我们关心的事件的？在一个 while 循环中 select 出事件，然后依次处理每种事件。我们可以把它称为事件循环，这就是 EventLoop 。 interface io.netty.channel. EventLoo…