2023/2/10总结
拓扑排序
拓扑排序是在一个有向无环图(DAG)所有顶点的线性排序。
拓扑排序核心思想非常简单,就是先找一个入度为0的顶点输出,再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。
入度:指的是能访问到该节点的其他节点总数。
出度:指的是该节点能访问到其他节点的总数。
拓扑排序说起来简单代码实现就不一定咯。
有俩种方法:
第一种:
卡恩算法。
- 先遍历图,记住图的入度。
- 再找到一个 入 度 为0的 删掉它(把它标记为-1)
- 并且把由入度为0能访问的节点的入度减去1.
- 如果有些节点没有出来,说明这个图存在环。
第二种:
dfs方法。
- 我们设立一个数组visted[N];当visited数组值为0,表示还未访问,为1表示正在访问,为-1表示访问结束
- 递归访问节点,将该节点状态设置为1
- 递归访问该节点的后续节点
- 将该节点状态设置为-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总结
拓扑排序 拓扑排序是在一个有向无环图(DAG)所有顶点的线性排序。 拓扑排序核心思想非常简单,就是先找一个入度为0的顶点输出,再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。 入度…...
2023最新版!宝塔面板Docker自建Bitwarden密码管理
Powered by:NEFU AB-IN 请一定要结合B站视频食用!!!!,下面的博客总体来说只是起到提纲作用 B站视频链接!!! 文章目录2023最新版!宝塔面板Docker自建Bitwarden密码管理前…...
【Hello Linux】 Linux基础命令
作者:小萌新 专栏:Linux 作者简介:大二学生 希望能和大家一起进步! 本篇博客简介:介绍Linux的基础命令 Linux基础命令ls指令lsls -als -dls -ils -sls -lls -nls -Fls -rls -tls -Rls -1总结思维导图pwd指令whoami指令…...
151、【动态规划】leetcode ——2. 01背包问题:二维数组+一维数组(C++版本)
题目描述 原题链接:2. 01背包问题 解题思路 (1)二维dp数组 动态规划五步曲: (1)dp[i][j]的含义: 容量为j时,从物品1-物品i中取物品,可达到的最大价值 (2…...
2023-02-09 - 3 Elasticsearch基础操作
本章主要介绍ES的基础操作,具体包括索引、映射和文档的相关操作。其中,在文档操作中将分别介绍单条操作和批量操作。在生产实践中经常会通过程序对文档进行操作,因此在介绍文档操作时会分别介绍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账户,用于数据收集3.4 启动mysql_exporter3.5 配…...
电脑分盘怎么分?分盘详细教程来了,图文教学
电脑作为小伙伴日常生活使用的工具,很多事情都需要使用电脑来进行处理。虽然小伙伴使用电脑比较多,但是还是有不少的小伙伴不知道电脑分盘怎么分?其实电脑分盘很简单,下面小编就以图文教学的方式,详细的向小伙伴介绍电…...
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:零件法 重点:通过工作平面面板上的设置工作平面命令选取正确的面取消勾选通过原始分类的材质,如图1所示 方法2:拆分构造层绘制一道墙体,选择创建的墙体,单击…...
【Linux operation 56】Linux 系统验证端口连通性
linux 系统验证端口连通性 1、前提 Linux系统有时候需要测试某个端口的连通性,然而ping命令只能测试某个IP通不通,不能测试某端口的连通性。 因为ping命令是基于ICMP协议,是计算机网络中的网络层的协议,但是想要测试某个的连通…...
@Valid注解配合属性校验注解完成参数校验并且优化异常处理
Valid注解配合属性校验注解完成参数校验并且优化参数校验异常处理1 Valid注解配合属性校验注解完成参数校验2 优化参数校验异常处理1 Valid注解配合属性校验注解完成参数校验 向数据库商品分类表中新增商品分类字段,并校验传入的参数 不使用注解的传统方法…...
每天一道大厂SQL题【Day08】
每天一道大厂SQL题【Day08】 大家好,我是Maynor。相信大家和我一样,都有一个大厂梦,作为一名资深大数据选手,深知SQL重要性,接下来我准备用100天时间,基于大数据岗面试中的经典SQL题,以每日1题…...
朗润国际期货:2023/2/10今日期市热点及未来焦点
2023/2/10今日期市热点及未来焦点 1月份人 民币贷款增加4.9万亿元 创历史新高 中国央行: 1月份人民币贷款增加4.9万亿元,同比多增9227亿元。分部门看,住户贷款增加2572亿元,其中,短期贷款增加341亿元,中长期贷款增加…...
TLV73312PQDRVRQ1稳压器TPS622314TDRYRQ1应用原理图
一、TLV73312PQDRVRQ1低压差稳压器 1.2V 300MATLV733 300mA 低压差稳压器是有 300mA 拉电流能力的超小型、低静态电流 LDO,具有良好的线路和负载瞬态性能。这些器件具有 1% 的典型精度。TLV733 系列设计具有先进的无电容器结构,确保无需输入或输出电容器…...
课程回顾|以智能之力,加速媒体生产全自动进程
本文内容整理自「智能媒体生产」系列课程第二讲:视频AI与智能生产制作,由阿里云智能视频云高级技术专家分享视频AI原理,AI辅助媒体生产,音视频智能化能力和底层原理,以及如何利用阿里云现有资源使用音视频AI能力。课程…...
C库函数文件操作(fopen、fread、fwrite、fclose)
C库函数 C文件操作用库函数实现,包含在stdio.h中,系统自动打开和关闭三个标准文件: 标准输入-键盘(stdin)标准输出-显示器(stdout)标准出错输出-显示器(stderr) 文件打…...
【Java|golang】1798. 你能构造出连续值的最大数目
给你一个长度为 n 的整数数组 coins ,它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币,它们的和为 x ,那么称,你可以 构造 出 x 。 请返回从 0 开始(包括 0 )&a…...
VB 消息、消息队列、事件
windows是图像化界面,多任务消息windows系统将消息(大的结构)发给其他应用程序Windows消息包含了所有的外部输入或者计算机内部信息,应用程序的消息队列先进先出,Windows消息的循环--每个应用程序里有自己的消息循环外…...
Linux实用指令记录
du Linux du(英文全拼:disk usage)命令用于显示目录或文件的大小。du 会显示指定的目录或文件所占用的磁盘空间。用例:当前路径/home/hzf/Voice/wespeaker-master$ du -h -d 1 371G ./examples 52K ./tools 280K ./run…...
Jetpack Compose中的绘制流程和自定义布局
Jetpack Compose中绘制流程的三个阶段 与大多数其他界面工具包一样,Compose 会通过几个不同的“阶段”来渲染帧。如果我们观察一下 Android View 系统,就会发现它有 3 个主要阶段:测量、布局和绘制。Compose 和它非常相似,但开头…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
