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

2023/2/10总结

拓扑排序

拓扑排序是在一个有向无环图(DAG)所有顶点的线性排序。

拓扑排序核心思想非常简单,就是先找一个入度为0的顶点输出,再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。

入度:指的是能访问到该节点的其他节点总数。

出度:指的是该节点能访问到其他节点的总数。

拓扑排序说起来简单代码实现就不一定咯。

有俩种方法:

第一种:

卡恩算法。

  1. 先遍历图,记住图的入度。
  2. 再找到一个 入 度 为0的 删掉它(把它标记为-1)
  3. 并且把由入度为0能访问的节点的入度减去1.
  4. 如果有些节点没有出来,说明这个图存在环。

第二种: 

dfs方法。

  1. 我们设立一个数组visted[N];当visited数组值为0,表示还未访问,为1表示正在访问,为-1表示访问结束
  2. 递归访问节点,将该节点状态设置为1
  3. 递归访问该节点的后续节点
  4. 将该节点状态设置为-1,并且输出(输出结果是逆序)

卡恩算法和dfs算法,dfs算法像是卡恩算法的逆序操作,他们的时间复杂度是一样的。

最好使用邻接表存储

下面是我自己写出的卡恩算法和dfs算法:

我在dfs算法里面没有判断出现环路的情况。

#include<stdio.h>
#include<malloc.h>
#define N 100
#define MAX 999999
int m,n,stin[N],visted[N],res[N],nox;
typedef struct node
{int v;struct node *next;
}NODE;
NODE k[N];
int fun(NODE *head,int v)
{NODE *p,*q;if(head==NULL){head=(NODE *)malloc(sizeof(NODE));head->v=v;head->next=NULL;}p=head;while(p!=NULL){q=p;p=p->next;}p=(NODE *)malloc(sizeof(NODE));p->v=v;q->next=p;p->next=NULL;
}
int put(NODE *head)
{head=head->next;while(head){printf("%d ",head->v);head=head->next;}puts("");
}
int kahn()
{int i,flag=1;NODE *p;while(flag){flag=0;for(i=1;i<=n;i++){if(stin[i]==0) {stin[i]=-1;flag=i;break;}}if(flag) printf("%d ",flag);p=k+flag;p=p->next;while(p!=NULL){stin[p->v]--;p=p->next;}}puts("");
}
int dfs(int x)
{int i;NODE *p=k+x;p=p->next;while(p!=NULL){if(visted[p->v]==0){dfs(p->v);visted[p->v]=1;}p=p->next;}res[nox++]=x;return 0;
}
int main()
{int i,j,u,v;puts("请输入顶点数量:");scanf("%d",&n);puts("请输入边的数量:");scanf("%d",&m);for(i=0;i<=n;i++){k[i].v=0;k[i].next=NULL;}for(i=0;i<m;i++){scanf("%d%d",&u,&v);stin[v]++;fun(k+u,v);}puts("邻接表为:");for(i=1;i<=n;i++){printf("%d-> ",i);put(k+i);}puts("拓扑排序为:");//	kahn();for(i=1;i<=n;i++){if(stin[i]==0)dfs(i);}for(i=nox-1;i>=0;i--)printf("%d ",res[i]);return 0;
}

相关文章:

2023/2/10总结

拓扑排序 拓扑排序是在一个有向无环图&#xff08;DAG&#xff09;所有顶点的线性排序。 拓扑排序核心思想非常简单&#xff0c;就是先找一个入度为0的顶点输出&#xff0c;再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。 入度&#xf…...

2023最新版!宝塔面板Docker自建Bitwarden密码管理

Powered by:NEFU AB-IN 请一定要结合B站视频食用&#xff01;&#xff01;&#xff01;&#xff01;&#xff0c;下面的博客总体来说只是起到提纲作用 B站视频链接&#xff01;&#xff01;&#xff01; 文章目录2023最新版&#xff01;宝塔面板Docker自建Bitwarden密码管理前…...

【Hello Linux】 Linux基础命令

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;介绍Linux的基础命令 Linux基础命令ls指令lsls -als -dls -ils -sls -lls -nls -Fls -rls -tls -Rls -1总结思维导图pwd指令whoami指令…...

151、【动态规划】leetcode ——2. 01背包问题:二维数组+一维数组(C++版本)

题目描述 原题链接&#xff1a;2. 01背包问题 解题思路 &#xff08;1&#xff09;二维dp数组 动态规划五步曲&#xff1a; &#xff08;1&#xff09;dp[i][j]的含义&#xff1a; 容量为j时&#xff0c;从物品1-物品i中取物品&#xff0c;可达到的最大价值 &#xff08;2…...

2023-02-09 - 3 Elasticsearch基础操作

本章主要介绍ES的基础操作&#xff0c;具体包括索引、映射和文档的相关操作。其中&#xff0c;在文档操作中将分别介绍单条操作和批量操作。在生产实践中经常会通过程序对文档进行操作&#xff0c;因此在介绍文档操作时会分别介绍DSL请求形式和Java的高级REST编码形式。 1 索引…...

云原生系列之使用 prometheus监控MySQL实战

文章目录前言一. 实验环境二. 安装MySQL5.72.1 配置yum源2.2 安装MySQL之前的环境检查2.3 开始使用yum安装2.4 启动MySQL并测试三. 安装MySQL_exporter3.1 MySQL_exporter的介绍3.2 mysql_exporter的安装3.3 设置MySQL账户&#xff0c;用于数据收集3.4 启动mysql_exporter3.5 配…...

电脑分盘怎么分?分盘详细教程来了,图文教学

电脑作为小伙伴日常生活使用的工具&#xff0c;很多事情都需要使用电脑来进行处理。虽然小伙伴使用电脑比较多&#xff0c;但是还是有不少的小伙伴不知道电脑分盘怎么分&#xff1f;其实电脑分盘很简单&#xff0c;下面小编就以图文教学的方式&#xff0c;详细的向小伙伴介绍电…...

Element UI框架学习篇(四)

Element UI框架学习篇(四) 1 准备工作 1.0 创建Emp表并插入相应数据的sql语句 /*MySQL数据库*/SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;-- ---------------------------- -- Table structure for emp -- ---------------------------- DROP TABLE IF EXISTS emp; CRE…...

Revit快速材质切换:同一墙面赋予不同材质的方法

一、Revit中对同一墙面赋予不同材质的方法 方法1&#xff1a;零件法 重点&#xff1a;通过工作平面面板上的设置工作平面命令选取正确的面取消勾选通过原始分类的材质&#xff0c;如图1所示 方法2&#xff1a;拆分构造层绘制一道墙体&#xff0c;选择创建的墙体&#xff0c;单击…...

【Linux operation 56】Linux 系统验证端口连通性

linux 系统验证端口连通性 1、前提 Linux系统有时候需要测试某个端口的连通性&#xff0c;然而ping命令只能测试某个IP通不通&#xff0c;不能测试某端口的连通性。 因为ping命令是基于ICMP协议&#xff0c;是计算机网络中的网络层的协议&#xff0c;但是想要测试某个的连通…...

@Valid注解配合属性校验注解完成参数校验并且优化异常处理

Valid注解配合属性校验注解完成参数校验并且优化参数校验异常处理1 Valid注解配合属性校验注解完成参数校验2 优化参数校验异常处理1 Valid注解配合属性校验注解完成参数校验 向数据库商品分类表中新增商品分类字段&#xff0c;并校验传入的参数 不使用注解的传统方法&#xf…...

每天一道大厂SQL题【Day08】

每天一道大厂SQL题【Day08】 大家好&#xff0c;我是Maynor。相信大家和我一样&#xff0c;都有一个大厂梦&#xff0c;作为一名资深大数据选手&#xff0c;深知SQL重要性&#xff0c;接下来我准备用100天时间&#xff0c;基于大数据岗面试中的经典SQL题&#xff0c;以每日1题…...

朗润国际期货:2023/2/10今日期市热点及未来焦点

2023/2/10今日期市热点及未来焦点 1月份人 民币贷款增加4.9万亿元 创历史新高 中国央行: 1月份人民币贷款增加4.9万亿元&#xff0c;同比多增9227亿元。分部门看&#xff0c;住户贷款增加2572亿元&#xff0c;其中&#xff0c;短期贷款增加341亿元&#xff0c;中长期贷款增加…...

TLV73312PQDRVRQ1稳压器TPS622314TDRYRQ1应用原理图

一、TLV73312PQDRVRQ1低压差稳压器 1.2V 300MATLV733 300mA 低压差稳压器是有 300mA 拉电流能力的超小型、低静态电流 LDO&#xff0c;具有良好的线路和负载瞬态性能。这些器件具有 1% 的典型精度。TLV733 系列设计具有先进的无电容器结构&#xff0c;确保无需输入或输出电容器…...

课程回顾|以智能之力,加速媒体生产全自动进程

本文内容整理自「智能媒体生产」系列课程第二讲&#xff1a;视频AI与智能生产制作&#xff0c;由阿里云智能视频云高级技术专家分享视频AI原理&#xff0c;AI辅助媒体生产&#xff0c;音视频智能化能力和底层原理&#xff0c;以及如何利用阿里云现有资源使用音视频AI能力。课程…...

C库函数文件操作(fopen、fread、fwrite、fclose)

C库函数 C文件操作用库函数实现&#xff0c;包含在stdio.h中&#xff0c;系统自动打开和关闭三个标准文件&#xff1a; 标准输入-键盘&#xff08;stdin&#xff09;标准输出-显示器&#xff08;stdout&#xff09;标准出错输出-显示器&#xff08;stderr&#xff09; 文件打…...

【Java|golang】1798. 你能构造出连续值的最大数目

给你一个长度为 n 的整数数组 coins &#xff0c;它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币&#xff0c;它们的和为 x &#xff0c;那么称&#xff0c;你可以 构造 出 x 。 请返回从 0 开始&#xff08;包括 0 &#xff09;&a…...

VB 消息、消息队列、事件

windows是图像化界面&#xff0c;多任务消息windows系统将消息&#xff08;大的结构&#xff09;发给其他应用程序Windows消息包含了所有的外部输入或者计算机内部信息&#xff0c;应用程序的消息队列先进先出&#xff0c;Windows消息的循环--每个应用程序里有自己的消息循环外…...

Linux实用指令记录

du Linux du&#xff08;英文全拼&#xff1a;disk usage&#xff09;命令用于显示目录或文件的大小。du 会显示指定的目录或文件所占用的磁盘空间。用例&#xff1a;当前路径/home/hzf/Voice/wespeaker-master$ du -h -d 1 371G ./examples 52K ./tools 280K ./run…...

Jetpack Compose中的绘制流程和自定义布局

Jetpack Compose中绘制流程的三个阶段 与大多数其他界面工具包一样&#xff0c;Compose 会通过几个不同的“阶段”来渲染帧。如果我们观察一下 Android View 系统&#xff0c;就会发现它有 3 个主要阶段&#xff1a;测量、布局和绘制。Compose 和它非常相似&#xff0c;但开头…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...