当前位置: 首页 > news >正文

图的拓扑序列(BFS_如果节点带着入度信息)

 way:找入度为0的节点删除,减少其他节点的入度,继续找入度为0的节点,直到删除完所有的图节点。(遍历node的neighbors就能得到neighbors的入度信息)

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;//边结构的描述
class Edge
{
public://边的起始节点Node *from;//边的终点节点Node *to;//边的权重int weight;
public:Edge(Node *from, Node *to, int weight){this->from = from;this->to = to;this->weight = weight;}
};//点结构的描述
class Node
{
public://编号值int value;//入度int in;//出度int out;//邻接的点vector<Node*> nexts;//邻接的边vector<Edge*> edges;
public:Node(){}Node(int value){this->value = value;in = 0;out = 0;}
};//图结构的描述
class Graph
{
public:map<int, Node*> nodes;set<Edge*> edges;Graph(){}
};//利用边结构描述的图来构建图结构
//[0,7,5]   [from,to,weight]
//[0,1,3]   [from,to,weight]
Graph* createGraph(vector<vector<int>> matrix)
{Graph *graph = new Graph();int m = matrix.size();for(int i=0; i<m; i++){int from = matrix[i][0];int to = matrix[i][1];int weight = matrix[i][2];//将起点结构放到图里面if(!graph->nodes.count(from)){Node *fromNode =new Node(from);graph->nodes[from] = fromNode;}//将终点结构放到图里面if(!graph->nodes.count(to)){Node *toNode=new Node(to);graph->nodes[to] = toNode;}//将起点和终点的边结构也放到图里面(点可能已经存在过,边一定是新的)Node *fromNode = graph->nodes[from];Node *toNode = graph->nodes[to];Edge *newEdge = new Edge(fromNode, toNode, weight);fromNode->nexts.push_back(toNode);fromNode->edges.push_back(newEdge);fromNode->out++;toNode->in++;graph->edges.insert(newEdge);}return graph;
}vector<Node*> topSort(Graph *graph)
{//收集节点入度映射,将0入度放入que中map<Node*,int>indegreeMap;queue<Node*>zeroQue;for(auto pa:graph->nodes){indegreeMap[pa.second]=pa.second->in;if(indegreeMap[pa.second]==0){zeroQue.push(pa.second);}}vector<Node*>result;//开始按入度为0删除节点,同时减少其他节点入度,删除入度为0...while(!zeroQue.empty()){Node *cur=zeroQue.front();zeroQue.pop();result.push_back(cur);for(auto next: cur->nexts){indegreeMap[next]=indegreeMap[next]-1;if(indegreeMap[next]==0){zeroQue.push(next);}}}return result;
}

相关文章:

图的拓扑序列(BFS_如果节点带着入度信息)

way&#xff1a;找入度为0的节点删除&#xff0c;减少其他节点的入度&#xff0c;继续找入度为0的节点&#xff0c;直到删除完所有的图节点。&#xff08;遍历node的neighbors就能得到neighbors的入度信息&#xff09; #include<iostream> #include<vector> #incl…...

Linux常用指令集合

ls显示目录文件 选项&#xff1a; -a 所有文件&#xff08;all所有&#xff09; -l 详细信息&#xff08;Information信息&#xff09;&#xff08;自动包含-1&#xff09; 所以常用 ll -1 一行只输出一个文件。 -R 列出所有子目录下的文件。…...

前端 JS 经典:为什么需要模块化

首先&#xff0c;自我评定一下&#xff0c;一个 js 文件&#xff0c;各位兄弟&#xff0c;最多能掌控多少行&#xff0c;什么意思呢&#xff0c;就是说&#xff0c;一个 js 文件在多少行之内&#xff0c;你是可以清楚的知道这个 JS 实现了哪些业务逻辑&#xff0c;并对这些业务…...

MySQL:某字段追加随机数

在MySQL中&#xff0c;你可以使用UPDATE语句结合随机函数RAND()来为某个字段追加随机数。以下是一个示例&#xff0c;假设我们有一个表my_table&#xff0c;其中有一个字段my_field&#xff0c;我们想要为这个字段追加一个介于1到100之间的随机数&#xff1a; UPDATE my_table…...

研发管理-选择研发管理系统-研发管理系统哪个好

选择研发管理系统-研发管理系统哪个好 选择研发管理系统时&#xff0c;并没有一个绝对的“最好”的系统&#xff0c;因为每个企业的需求和情况都是独特的。然而&#xff0c;我可以向您介绍一些在市场上广受欢迎且功能强大的研发管理系统&#xff0c;供您参考&#xff1a; 1、彩…...

学校NTP时钟系统(时间同步系统)方案助力建设智慧校园

学校NTP时钟系统&#xff08;时间同步系统&#xff09;方案助力建设智慧校园 学校NTP时钟系统&#xff08;时间同步系统&#xff09;方案助力建设智慧校园 建设智慧校园也意味着校内网络设备和服务器剧增&#xff0c;如何保障智慧校园内各数字系统时序一致、维稳运行成为一大难…...

HTML中打开窗口的类型及使用方法

HTML中打开窗口是Web开发中常用的功能之一&#xff0c;可以通过不同的方式打开窗口&#xff0c;以满足不同的需求。本文将介绍HTML中打开窗口的类型及使用方法。 一、使用target属性打开窗口 target属性是HTML中打开窗口最常用的方式之一&#xff0c;可以通过设置target属性的…...

【userfaultfd+条件竞争劫持modprobe_path】TSGCTF 2021 -- lkgit

前言 入门题&#xff0c;单纯就是完成每日一道 kernel pwn 的 kpi &#x1f600; 题目分析 内核版本&#xff1a;v5.10.25&#xff0c;可以使用 userfaultfd&#xff0c;不存在 cg 隔离开启了 smap/smep/kaslr/kpti 保护开启了 SLAB_HADNERN/RANDOM 保护 题目给了源码&…...

StNet: Local and Global Spatial-Temporal Modeling for Action Recognition 论文阅读

StNet: Local and Global Spatial-Temporal Modeling for Action Recognition 论文阅读 Abstract1 Introduction2 Related Work3 Proposed Approach4 Experiments5 Conclusion 文章信息&#xff1a; 原文链接&#xff1a;https://ojs.aaai.org/index.php/AAAI/article/view/4…...

SpringBoot解决CORS跨域——WebMvcConfigurationSupport

前端请求后端报错了。 状态码&#xff1a;403 返回错误&#xff1a;Invalid coRs request 增加配置类WebMvcConfig Configuration public class WebMvcConfig extends WebMvcConfigurationSupport {Overridepublic void addCorsMappings(CorsRegistry registry) {// 允许跨域…...

Linux之内存管理-malloc \kmalloc\vmalloc\dma

1、malloc 函数 1.1分配内存小于128k,调用brk malloc是C库实现的函数&#xff0c;C库维护了一个缓存&#xff0c;当内存够用时&#xff0c;malloc直接从C库缓存分配&#xff0c;只有当C库缓存不够用&#xff1b; 当申请的内存小于128K时&#xff0c;通过系统调用brk&#xff…...

PyTorch中定义自己的数据集

文章目录 1. 简介2. 查看PyTorch自带的数据集(可视化)3. 准备材料3.1 图片数据3.2 标签数据 4. 方法 1. 简介 尽管PyTorch提供了许多自带的数据集&#xff0c;如MNIST、CIFAR-10、ImageNet等&#xff0c;但它们对于没有经验的用户来说&#xff0c;理解数据加载器的工作原理以及…...

助力数字农林业发展服务香榧智慧种植,基于YOLOv5全系列【n/s/m/l/x】参数模型开发构建香榧种植场景下香榧果实检测识别系统

作为一个生在北方但在南方居住多年的人&#xff0c;居然头一次听过香榧&#xff08;fei&#xff09;这种作物&#xff0c;而且这个字还不会念&#xff0c;查了以后才知道读音&#xff08;fei&#xff09;&#xff0c;三声&#xff0c;这着实引起了我的好奇心&#xff0c;我相信…...

2024 年 4 月区块链游戏研报:市场低迷中活跃用户数创新高

2024 年 4 月区块链游戏研报 作者&#xff1a;stellafootprint.network 数据来源&#xff1a;GameFi 研究页面 2024 年 4 月&#xff0c;Web3 游戏领域在经历 3 月创纪录的表现后&#xff0c;迎来了显著波动。比特币自历史高位回调&#xff0c;月跌幅达到 10.4%。与此同时&a…...

排序(一)----冒泡排序,插入排序

前言 今天讲一些简单的排序,冒泡排序和插入排序,但是这两个排序时间复杂度较大,只是起到一定的学习作用,只需要了解并会使用就行,本文章是以升序为例子来介绍的 一冒泡排序 思路 冒泡排序是一种简单的排序算法&#xff0c;它重复地遍历要排序的序列&#xff0c;每次比较相邻…...

springcloud简单了解及上手

springcloud微服务框架简单上手 文章目录 springcloud微服务框架简单上手一、SpringCloud简单介绍1.1 单体架构1.2 分布式架构1.3 微服务 二、SpringCloud与SpringBoot的版本对应关系2022.x 分支2021.x 分支2.2.x 分支 三、Nacos注册中心3.1 认识和安装Nacos3.2 配置Nacos3.3 n…...

Halcon与深度学习框架结合进行图像分析

Halcon 是一款强大的机器视觉软件&#xff0c;而深度学习框架如 TensorFlow 或 PyTorch 在图像识别和分类任务中表现出色。结合两者的优势&#xff0c;可以实现复杂的图像分析任务。Halcon 负责图像预处理和特征提取&#xff0c;而深度学习框架则利用这些特征进行高级分析和识别…...

STL----push,insert,empalce

push_back和emplace_back的区别 #include <iostream> #include <vector>using namespace std; class testDemo { public:testDemo(int n) :num(n) {cout << "构造函数" << endl;}testDemo(const testDemo& other) :num(other.num) {cou…...

解决OpenHarmony设备开发Device Tools工具的QUICK ACCESS一直为空

今天重新安装了OpenHarmony设备开发的环境&#xff0c;在安装过程中&#xff0c;到了工程之后&#xff0c;QUICK ACCESS一直为空。如下图红色大方框的内容一开始没有。 解决方案&#xff1a; 在此记录我的原因&#xff0c;我的原因主要是deveco device tools的远程连接的是z…...

k8s拉起一个pod底层是如何运行的

在Kubernetes中&#xff0c;当你尝试启动一个Pod时&#xff0c;底层的运行方式是由Kubelet服务来管理的。以下是Pod启动过程的简化概述&#xff1a; Kubernetes API Server接收到创建Pod的请求。 API Server将Pod的元数据存储到etcd中&#xff0c;以便于Pod的调度和跟踪。 Sc…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...