c语言数据结构--------拓扑排序和逆拓扑排序(Kahn算法和DFS算法实现)
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>//使用卡恩算法(Kahn)和深度优先算法(DFS)实现//拓扑排序和逆拓扑排序//拓扑排序和逆拓扑排序顶点顺序相反//图，邻接矩阵存储
#define MaxVertexNum 100 //最大顶点数typedef struct {int vex[MaxVertexNum]; //顶点表int edge[MaxVertexNum][MaxVertexNum]; //边表int vernum, arcnum; //记录当前图的顶点数量和边数
} MGraph;int vexIndex(MGraph G, int x);void visit(int i);//初始化图
MGraph InitMgraph() {MGraph graph;memset(graph.edge, 0, sizeof(graph.edge));graph.arcnum = 0;graph.vernum = 0;return graph;
}//带头节点
//链队列节点
typedef struct Linknode {int data;struct Linknode *next;
} Linknode;//链队列
typedef struct {//队头指针Linknode *front;//队尾指针Linknode *rear;
} LinkQueue;//初始化队列
void InitQueue(LinkQueue *Q) {//创建头结点Linknode *temp = (Linknode *) malloc(sizeof(Linknode));Q->front = temp;Q->rear = temp;
}//入队
void EnQueue(LinkQueue *Q, int data) {//创造节点Linknode *temp = (Linknode *) malloc(sizeof(Linknode));//赋值temp->data = data;temp->next = NULL;//连接插入节点Q->rear->next = temp;//队尾指针更换Q->rear = temp;
}//出队
bool DeQueue(LinkQueue *Q, int *e) {//队列为空if (Q->rear == Q->front) {return false;}//要出队的节点Linknode *temp = Q->front->next;*e = temp->data;//队头指针更换Q->front->next = temp->next;free(temp);//最后一个节点出队if (temp == Q->rear) {//队尾指针更换Q->rear = Q->front;}return true;
}/
//借助队列实现拓扑排序
//卡恩算法
bool TopologicalSort(MGraph G) {//初始化队列LinkQueue *linkQueue = (Linknode *) malloc(sizeof(linkQueue));InitQueue(linkQueue);//当前顶点的入度int indegree[G.vernum];//记录拓扑排序int print[G.vernum];memset(indegree, 0, sizeof(indegree));//初始化入度数组for (int i = 0; i < G.vernum; ++i) {for (int j = 0; j < G.vernum; j++) {if (G.edge[j][i] == 1) {indegree[i]++;}}}//初始化print数组memset(print, -1, sizeof(print));//度为0的顶点索引入队列for (int i = 0; i < G.vernum; i++) {if (indegree[i] == 0) {EnQueue(linkQueue, i);indegree[i] = -1;}}//记录顶点个数int count = 0;int *e = malloc(sizeof(int));while (linkQueue->rear != linkQueue->front) {DeQueue(linkQueue, e);print[count] = G.vex[*e];count++;for (int i = 0; i < G.vernum; ++i) {if (G.edge[*e][i] == 1) {indegree[i]--;}if (indegree[i] == 0) {EnQueue(linkQueue, i);indegree[i] = -1;}}}if (count < G.vernum)return false;else {for (int i = 0; i < G.vernum; i++) {printf("%d ", print[i]);}return true;}}int time;
int finalTime[100];
int visited[100];//DFS算法实现拓扑排序
//v为入度为0的顶点
void DFSTopologicalSort(MGraph G, int i) {//对i做已访问标记visited[vexIndex(G, i)] = 1;//找到i的所有邻接点for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0 && G.edge[vexIndex(G, i)][j] == 1) {DFSTopologicalSort(G, G.vex[j]);}}(time)++;finalTime[vexIndex(G, i)] = time;}//使用后visited会被重新赋值，需重置
//建议用一个变量临时保存原有图
void DFSTraverseTopologicalSort(MGraph G, int i) {time = 0;for (int j = 0; j < G.vernum; j++) {visited[j] = 0;}DFSTopologicalSort(G, i);for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0) {DFSTopologicalSort(G, G.vex[j]);}}for (int j = 0; j < G.vernum; j++) {printf("%d ", finalTime[j]);}
}//有向图深度优先搜索
void niDFSTopologicalSort(MGraph G, int i) {//对i做已访问标记visited[vexIndex(G, i)] = 1;//找到i的所有邻接点for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0 && G.edge[vexIndex(G, i)][j] == 1) {niDFSTopologicalSort(G, G.vex[j]);}}printf("%d ", i);
}//使用后visited会被重新赋值，需重置
//建议用一个变量临时保存原有图
//连通图和非连通图的深度优先搜索(改进)
void niDFSTraverseTopologicalSort(MGraph G, int i) {for (int j = 0; j < G.vernum; j++) {visited[j] = 0;}niDFSTopologicalSort(G, i);for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0) {niDFSTopologicalSort(G, G.vex[j]);}}
}int main(void) {//有向图//初始化图MGraph graph = InitMgraph();//图添加元素//顶点集添加1,2,3,4,5for (int i = 0; i < 5; i++) {graph.vex[i] = i + 1;graph.vernum++;}//边集加边<1,2>,<1,4>,<2,3>,<2,4>,<3,5>,<4,3>,<4,5>graph.edge[0][1] = 1;graph.edge[0][3] = 1;graph.edge[1][2] = 1;graph.edge[1][3] = 1;graph.edge[2][4] = 1;graph.edge[3][2] = 1;graph.edge[3][4] = 1;graph.arcnum = 7;printf("拓扑排序序列:\n");TopologicalSort(graph);printf("\n");printf("tineFinal数组:\n");DFSTraverseTopologicalSort(graph, 1);printf("\n");printf("逆拓扑排序序列:\n");niDFSTraverseTopologicalSort(graph, 5);
}//返回x在顶点表的索引
int vexIndex(MGraph G, int x) {int index = -1;for (int i = 0; i < G.vernum; i++) {if (G.vex[i] == x) {index = i;break;}}return index;
}
测试用例
相关文章：
)
c语言数据结构--------拓扑排序和逆拓扑排序(Kahn算法和DFS算法实现)
#include <stdio.h> #include <string.h> #include <stdbool.h> #include <stdlib.h>//使用卡恩算法(Kahn)和深度优先算法(DFS)实现//拓扑排序和逆拓扑排序//拓扑排序和逆拓扑排序顶点顺序相反//图，邻接矩阵存储 #define MaxVertexNum 100 …...
日期类的实现
本文运用c类和对象中的构造函数， 析构函数 ，拷贝构造函数 ， 赋值运算符重载等为大家模拟实现日期类的操作 #define _CRT_SECURE_NO_WARNINGS 1 #include"date.h" void Date:: showinfo() {cout << _year << "年&…...
3dgs通俗讲解
3d gaussian splatting：基于splatting和机器学习的三维重建方法。 特点： 无深度学习简单的机器学习大量的CG知识复杂的线性代数对GPU的高性能编程 一、什么是splatting 1、选择“雪球”； 为什么使用核（雪球） 各向…...
源码分析之Leaflet比例尺控件Control.Scale实现原理
概述 Control.Scale 是一个用于显示地图比例尺的控件，是 Leaflet 中实现比例尺控件的核心逻辑，用于在地图上动态显示公制（米/千米）和英制（英尺/英里）的比例尺。 源码分析 源码实现 Control.Scale的源码…...
【无标题 langsmith
【GPT入门】第32课 langsmith介绍与实战 1.lang smith作用2.lang smith配置方法3. 上手第一个lang smith3.1 可运行代码3.2 lang smith 官网，个人项目下 1.lang smith作用 LangSmith是由LangChain开发的一个平台，主要用于构建生产级LLM应用程序…...
智能建造新范式：装配式建筑 4.0 的数字化进阶
在全球数字化与可持续发展的浪潮中，建筑业正经历着第四次工业革命的深刻变革。装配式建筑4.0的出现，标志着建筑行业从传统的“钢筋水泥时代”迈向“数据驱动时代”，其核心在于通过技术融合重构建筑全生命周期的生产方式，实现从设计…...
)
从标准输入中读取所有内容sys.stdin.read()
sys.stdin.read().strip() 用于从标准输入中读取所有内容并去除首尾的空白字符。 1. sys.stdin.read() 作用：从标准输入流中读取所有内容，直到遇到文件结束符（EOF）。在命令行中，EOF 可以通过 CtrlD（Linux…...
网络：华为数通HCIA学习：静态路由基础
文章目录 前言静态路由基础静态路由应用场景 静态路由配置静态路由在串行网络的配置静态路由在以太网中的配置 负载分担配置验证 路由备份（浮动静态路由）配置验证 缺省路由配置验证 总结 华为HCIA 基础实验－静态路由 & eNSP静态路由 基础…...
DAY 35 leetcode 202--哈希表.快乐数
题号202 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1&a…...
Linux Command nmap 网络扫描
tags: 网络 文章目录 简介原理端口状态选项基本扫描发现扫描禁用DNS名称解析无ping扫描 端口扫描版本检测防火墙规避技术故障排除和调试NMAP 脚本 简介 Nmap（“ Network Mapper ”）是一个用于网络探索和安全审计的开源工具。它旨在快速扫描大型网络&…...
根据源码分析vue中nextTick的实现原理
根据源码分析vue中nextTick的实现原理 一. 核心变量定义二. 异步策略选择（降级处理）1. 微任务优先2. 降级到 MutationObserver3. 降级到宏任务 三、回调执行逻辑四、 nextTick 函数实现五、 与 Vue 更新流程的结合六、关键设计…...
Linux内核TCP/IP协议栈中的设计模式：从面向对象到系统级软件的跨界实践
引言 设计模式（Design Patterns）自GoF（Gang of Four）在1994年提出以来，已成为软件工程领域的核心概念。尽管其经典定义基于面向对象编程（OOP），但设计模式的本质是解决复杂问题的经验总结，而非局限于特定编程范式。本文以Linux内核的TCP/IP协议栈为例，探讨设计模式在…...
风云可测：华为AI天气大模型将暴雨预测误差缩至3公里内
华为云正式发布全球首个气象专用人工智能大模型"盘古气象"，实现台风路径24小时预测误差<30公里、暴雨落区72小时精度91%，较传统数值预报效率提升10000倍。本文基于对西北太平洋10个台风回溯测试、全国2360个气象站验证数据，解析…...
DeepSeek-R1 面试题汇总
Deepseek-r1 面试宝典 原文地址：https://articles.zsxq.com/id_91kirfu15qxw.html DeepSeek-R1 面试题汇总 DeepSeek-R1 面试题汇总 GRPO（Group Relative Policy Optimization）常见面试题汇总篇 DeepSeek-R1 DeepSeek-R1-Zero 常见面试题汇总…...
ASM1042A型CANFD芯片通信可靠性研究
摘要 本文旨在深入探讨ASM1042A型CAN-FD芯片在多节点通信中的可靠性表现。通过对芯片的电气特性、测试环境、多节点通信测试结果等多方面进行分析，结合实验数据与理论研究，全面评估其在复杂通信场景下的性能与可靠性。研究结果表明，ASM1042A…...
Java8 到 Java21 系列之 Stream API：数据处理的新方式（Java 8）
Java 8 到 Java 21 系列之 Stream API：数据处理的新方式（Java 8） 系列目录 Java8 到 Java21 系列之 Lambda 表达式：函数式编程的开端（Java 8）Java 8 到 Java 21 系列之 Stream API：数据处理的…...
【每日一个知识点】分布式数据湖与实时计算
在现代数据架构中，分布式数据湖（Distributed Data Lake） 结合 实时计算（Real-time Computing） 已成为大数据处理的核心模式。数据湖用于存储海量的结构化和非结构化数据，而实时计算则确保数据能够被迅速处理…...
接口自动化学习三：参数化parameterize
使用parametrize之前： def add(x,y):return xy class TestAddFunction(object):def test01(self):resadd(2,4)assert 6resdef test02(self):resadd(4,6)assert 10resparametrize参数化之后： import pytest def add(x,y):return xydata[(10,20,30),(200…...
呼叫中心系统压力测试文档
前期准备 用户需要准备两台配置相同的服务器，A服务器和B服务器。我们在这两台服务器上部署相同授权的程序。 配置流程 1. 创建话术 A服务器和B服务器都需要创建压力测试放音的话术，用于放音。按图操作： 2. 线路和线路组配置 A服务器&am…...
从0开始的构建的天气预报小时钟（基于STM32F407ZGT6，ESP8266 + SSD1309）——第1章 简单的介绍一下ESP8266和他的编程指令
目录 ESP8266编程指令前导——三种工作模式 ESP8266编程指令 工作确认指令（用于非穿透模式下） 设置工作模式：ATCWMODEX 两个重要的复位 硬复位ATRESTORE 软复位ATRST 加入Wifi ATCWJAP 开始一次TCP通信 进入和退出穿透模式 进入 ES…...
Cadence Integrity 3D-IC的解密
Early System-Level Analysis and Signoff Flow 请看下期发布...
清晰易懂的 Flutter 开发环境搭建教程
Flutter 是 Google 推出的跨平台应用开发框架，支持 iOS/Android/Web/桌面应用开发。本教程将手把手教你完成 Windows/macOS/Linux 环境下的 Flutter 安装与配置，从零到运行第一个应用，全程避坑指南！ 一、安装 Flutter SDK 1. 下载…...
)
NO.63十六届蓝桥杯备战|基础算法-⼆分答案|木材加工|砍树|跳石头(C++)
⼆分答案可以处理⼤部分「最⼤值最⼩」以及「最⼩值最⼤」的问题。如果「解空间」在从⼩到⼤的「变化」过程中，「判断」答案的结果出现「⼆段性」，此时我们就可以「⼆分」这个「解空间」，通过「判断」，找出最优解。 这个「⼆分答案…...
Python星球日记 - 第1天：欢迎来到Python星球
🌟引言： 上一篇：Python星球日记专栏介绍（持续更新ing） 名人说：莫听穿林打叶声，何妨吟啸且徐行。—— 苏轼《定风波莫听穿林打叶声》 创作者：Code_流苏(CSDN)（一个喜欢古诗…...
去中心化交易所（DEX）
核心概念与DEX类型 DEX vs CEX 中心化交易所（CEX）风险：资产托管风险（如2019年超2.9亿美元被盗）、隐私泄露（如50万用户信息泄漏）。 DEX优势：用户自持资产（非托管&#x…...
HTTP数据传输的几个关键字Header
本文着重针对http在传输数据时的几种封装方式进行描述。 1. Content-Type(描述body内容类型以及字符编码) HTTP的Content-Type用于定义数据传输的媒体类型（MIME类型），主要分为以下几类： (一)、基础文本类型 text/plain …...
Redis 的 Raft 选举协议
Redis 的 Raft 选举协议 主要用于 Redis Sentinel 和 Redis Cluster 的高可用实现中（尽管 Redis Cluster 默认使用类似 Gossip 的协议，但 Raft 的思想在 Sentinel 的领导者选举中有体现）。以下是关于 Raft 协议在 Redis 中的应用及脑裂问题的详细解析： 一、Redis 中的 Raft…...
sshd启动报错“Failed to start OpenSSH Server daemon”
“systemctl restart sshd”启动sshd服务异常，报错“Failed to start OpenSSH Server daemon”。 使用sshd -t命令检查sshd配置文件，返回关键信息gssapikexalgorithms相关错误。 解决方法 禁用 GSSAPI 相关的 KEX 算法 编辑sshd配置文件，注…...
)
MIT6.828 Lab3-2 Print a page table (easy)
实验内容 实现一个函数来打印页表的内容，帮助我们更好地理解 xv6 的三级页表结构。 修改内容 kernel/defs.h中添加函数声明，方便其它函数调用 void vmprint(pagetable_t);// lab3-2 Print a page tablekernel/vm.c中添加函数具体定义 采用…...
AI本地部署之ragflow
Ubunturagflowdeepseek本地部署目录 一、配置说明1. 软件配置说明2. 硬件配置说明 二、RagFlow安装和部署1. 前置条件2. 安装注：如果发现没有出现这个界面，可以进入ragflow/docker/ragflow-logs这个路径，查看ragflow_server.log文件中的内容&…...
源码分析之Leaflet属性控件Control.Attribution实现原理
概述 Control.Attribution 是一个 Leaflet 地图控件，用于显示地图的版权信息。它可以显示地图提供者的名称和链接，以及地图上的图层的版权信息。 源码分析 源码实现 Control.Attribution的源码实现如下 var ukrainianFlag <svg aria-hidden"…...
)
NO.62十六届蓝桥杯备战|基础算法-二分查找|查找元素的第一个和最后一个位置|牛可乐和魔法封印|A-B数对|烦恼的高考意愿(C++)
⼆分算法是我觉得在基础算法篇章中最难的算法。⼆分算法的原理以及模板其实是很简单的，主要的难点在于问题中的各种各样的细节问题。因此，⼤多数情况下，只是背会⼆分模板并不能解决题⽬，还要去处理各种乱七⼋糟的边界问题 34. 在…...
开源模型应用落地-Qwen2.5-Omni-7B模型-部署 “光速” 指南
一、前言 2025年3月，阿里巴巴通义千问团队开源的全模态大模型Qwen2.5-Omni-7B，犹如一记惊雷划破AI领域的长空。这个仅70亿参数的"小巧巨人"，以端到端的架构实现了对文本、图像、音频、视频的全模态感知，更通过创新的Thinker-Talker双核架构，将人类"接收-思…...
顺序容器 -forward list单链表
forward list单链表是C11加入到STL的。 使用forward list，必须包含头文件<forward_list> #include <forward_list> 这个头文件被定义在命名空间std内。 namespace std {template <typename T,typename Allocator allocator<T> >class …...
C++：算术运算符
程序员Amin 🙈作者简介：练习时长两年半，全栈up主 🙉个人主页：程序员Amin 🙊 P S : 点赞是免费的，却可以让写博客的作者开心好久好久😎 📚系列专栏：Java全…...
缺页异常导致的iowait打印出相关文件的绝对路径
一、背景 在之前的博客 增加等IO状态的唤醒堆栈打印及缺页异常导致iowait分析-CSDN博客 里，我们进一步优化了D状态和等IO状态的事件的堆栈打印，补充了唤醒堆栈打印，也分析了一种比较典型的缺页异常filemap_fault导致的iowait的情况。 在这篇…...
【Centos】centos7内核升级-亲测有效
相关资源 通过网盘分享的文件：脚本升级 链接: https://pan.baidu.com/s/1yrCnflT-xWhAPVQRx8_YUg?pwd52xy 提取码: 52xy –来自百度网盘超级会员v5的分享 使用教程 将脚本文件上传到服务器的一个目录 执行更新命令 yum install -y linux-firmware执行脚本即可 …...
多模态模型：专栏概要与内容目录
文章目录 多模态模型📚 核心内容模块Stable Diffusion基础教程Stable Diffusion原理深度解析部署与环境配置其他多模态模型实践 多模态模型 🔥 专栏简介 | 解锁AI绘画与多模态模型的技术奥秘 探索多模态AI技术，掌握Stable Diffusion等流行框…...
1. 购物车
1. 购物车 咱们购物车基于 V2 装饰器进行开发，底气来源于 自定义组件混用场景指导 1.1. 素材整合 observedv2和Trace 数据模型和页面 // 其他略 // 购物车 export interface CartGoods {count: number;id: string;name: string;picture: string;price: number;…...
frp 让服务器远程调用本地的服务（比如你的java 8080项目）
1、服务器上安装frp 2、本地安装frp 服务器上 frps.toml 配置信息： bindPort 30000auth.token "密码" # 客户端连接密码vhostHTTPPort 8082 本地 frpc.toml serverAddr "服务器ip" serverPort 30000 auth.token "服务器上设置的…...
《AI大模型应知应会100篇》第56篇：LangChain快速入门与应用示例
第56篇：LangChain快速入门与应用示例 前言 最近最火的肯定非Manus和OpenManus莫属，因为与传统AI工具仅提供信息不同，Manus能完成端到端的任务闭环。例如用户发送“筛选本月抖音爆款视频”，它会自动完成： 爬取平台数据…...
大模型——如何在本地部署微软的OmniParser V2
微软的 OmniParser V2 是一款尖端的人工智能屏幕解析器，可通过分析屏幕截图从图形用户界面中提取结构化数据，使人工智能代理能够与屏幕元素进行无缝交互。该工具是构建自主图形用户界面代理的完美选择，它改变了自动化和工作流程优化的游戏规则。在本指南中，我们将介绍如何在…...
Oracle触发器使用（一）：DML触发器
Oracle触发器使用（一）：DML触发器 DML触发器条件谓词触发器INSTEAD OF DML触发器复合DML触发器Oracle数据库中的触发器（Trigger）本质上也是PL/SQL代码，触发器可以被Enable或者Disable，但是不能像存储过程那样被直接调用执行。 触发器不能独立存在，而是定义在表、视图、…...
智慧园区大屏如何实现全局监测：监测意义、内容、方式
智慧园区的价值不容小觑呀，可以说园区的大部分数据都在这个大屏上，监测数据越多，那么大屏的价值就越大。很多小伙伴拿到需求后感觉无从下手，本文在这里智慧园区大屏可以监测哪些内容、监测的意义、监测的方式等，欢迎点…...
LeetCode 解题思路 31（Hot 100）
解题思路： 递归参数： 字符串 s、结果集 result、当前路径 path、回文子串数组 dp、开始位置 start。递归过程： 当当前路径 path 的长度等于 s.length() 时，说明已经分割完成，加入结果集。若当前起止位置满足回文条件…...
fastAPI详细介绍以及使用方法
FastAPI是一个现代的Python web框架，它提供快速构建API的能力。它具有高性能、易用性和文档自动生成的特点，使得开发者能够快速开发高效的API服务。 以下是一些FastAPI的主要特点和优势： 快速：FastAPI基于Python 3.6的异步框架St…...
数字人训练数据修正和查看 不需要GPU也能运行的DH_live-加载自己训练-
自己训练模pth报错 le "D:\ai\dh_live\app.py", line 42, in demo_mini interface_mini(asset_path, wav_path, output_video_name) File "D:\ai\dh_live\demo_mini.py", line 21, in interface_mini renderModel_mini.loadModel("checkpoi…...
WGAN-GP 原理及实现（pytorch版）
WGAN-GP 原理及实现 一、WGAN-GP 原理1.1 WGAN-GP 核心原理1.2 WGAN-GP 实现步骤1.3 总结二、WGAN-GP 实现2.1 导包2.2 数据加载和处理2.3 构建生成器2.4 构建判别器2.5 训练和保存模型2.6 图片转GIF一、WGAN-GP 原理 Wasserstein GAN with Gradient Penalty (WGAN-GP) 是对原…...
chromium魔改——navigator.webdriver 检测
chromium源码官网 https://source.chromium.org/chromium/chromium/src 说下修改的chromium源码思路： 首先在修改源码过检测之前，我们要知道它是怎么检测的，找到他通过哪个JS的API来做的检测，只有知道了如何检测，我们…...
Sentinel[超详细讲解]-7 -之 -熔断降级[异常比例阈值]
📖 主要讲解熔断降级之 --- 异常比例阈值 🚀 1️⃣ 背景 Sentinel 以流量作为切入点，提供了很多的丰富的功能，例如🤗： 流量控制，熔断降级等，它能够有效的适用各个复杂的业务场景&am…...