图的遍历DFSBFS-有向图无向图
西江月・证明
即得易见平凡,仿照上例显然。留作习题答案略,读者自证不难。
反之亦然同理,推论自然成立。略去过程Q.E.D.,由上可知证毕。
有向图的遍历可以使用深度优先搜索(DFS)和广度优先搜索(BFS)两种算法来实现。
有向图的遍历
1.DFS遍历有向图的步骤:
- 选择一个起始节点,标记为已访问。
- 访问其邻接节点中第一个未被访问的节点,标记为已访问。
- 以该节点为起始节点,重复步骤2,直到没有未访问的邻接节点。
- 回溯到上一个节点,重复步骤2和步骤3,直到所有节点都被访问。
DFS遍历可以使用递归或栈来实现。
#include<bits/stdc++.h>
using namespace std;// 建立有向图
void build_graph(vector<vector<int>>& graph, int num_edges) {for (int i = 0; i < num_edges; i++) {int from, to;cin >> from >> to;graph[from].push_back(to);}
}// 有向图的深度优先遍历
void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited, stack<int>& result) {visited[node] = true;for (int i = 0; i < graph[node].size(); i++) {int next_node = graph[node][i];if (!visited[next_node]) {dfs(graph, next_node, visited, result);}}result.push(node);
}// 输出拓扑排序结果
void print_topological_order(stack<int>& result) {while (!result.empty()) {cout << result.top() << " ";result.pop();}
}int main() {int num_nodes, num_edges;cin >> num_nodes >> num_edges;// 建立有向图vector<vector<int>> graph(num_nodes);build_graph(graph, num_edges);// 定义visited数组vector<bool> visited(num_nodes, false);// 定义结果栈stack<int> result;// 对每个未被遍历的节点进行深度优先遍历for (int i = 0; i < num_nodes; i++) {if (!visited[i]) {dfs(graph, i, visited, result);}}// 输出拓扑排序结果print_topological_order(result);return 0;
}
2.BFS遍历有向图的步骤:
- 选择一个起始节点,标记为已访问,并将其加入队列。
- 从队列中取出第一个节点,访问其邻接节点中第一个未被访问的节点,标记为已访问,并将其加入队列。
- 重复步骤2,直到队列为空。
- 如果还有未访问的节点,选择其中一个作为新的起始节点,重复步骤1~3。
BFS遍历可以使用队列来实现。
#include<bits/stdc++.h>
using namespace std;void bfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {queue<int> q;visited[start] = true;q.push(start);while (!q.empty()) {int curr = q.front();cout << curr << " ";q.pop();for (int neighbor : graph[curr]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}
}int main() {int n = 6; // number of nodes// adjacency list representation of the graphvector<vector<int>> graph(n);graph[0] = {1, 2};graph[1] = {0, 2, 3, 4};graph[2] = {0, 1, 3};graph[3] = {1, 2, 4};graph[4] = {1, 3, 5};graph[5] = {4};// mark all nodes as not visitedvector<bool> visited(n, false);// perform BFS traversal starting from node 0bfs(graph, visited, 0);return 0;
}
无向图的遍历
无向图的遍历有两种方法:深度优先搜索(DFS)和广度优先搜索(BFS)。
1. 深度优先搜索(DFS)
深度优先搜索是一种递归的搜索方式,从一个起点出发,沿着一条路径一直往下搜索直到走到尽头,然后回溯到之前的节点,继续搜索其他未被访问的节点。具体步骤如下:
(1)访问起点节点,并将其标记为已访问。
(2)从起点节点出发,搜索与其直接相邻的未被访问的节点。
(3)如果找到了一个未被访问的节点,就继续以该节点为起点递归搜索,直到无法再继续搜索为止。
(4)当所有与当前节点直接相邻的节点都被访问过,回溯到之前的节点,继续搜索其他未被访问的节点。
(5)重复上述步骤,直到所有节点都被访问过。
#include<bits/stdc++.h>
using namespace std;void dfs(int u, vector<bool>& visited, vector<vector<int>>& adjList) {visited[u] = true; // 标记节点u为已访问cout << u << " "; // 输出节点u// 遍历所有与节点u相邻的节点for (int v : adjList[u]) {if (!visited[v]) {dfs(v, visited, adjList); // 递归访问节点v}}
}void dfsTraversal(int n, vector<vector<int>>& adjList) {vector<bool> visited(n + 1, false); // 初始化所有节点为未访问状态for (int i = 1; i <= n; i++) {if (!visited[i]) { // 如果节点i未被访问过,从节点i开始DFS遍历dfs(i, visited, adjList);}}
}int main() {int n, m;cin >> n >> m; // 读入节点数和边数vector<vector<int>> adjList(n + 1); // 邻接表for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v; // 读入一条边的两个端点adjList[u].push_back(v);adjList[v].push_back(u); // 无向图,所以需要两条边}dfsTraversal(n, adjList); // DFS遍历return 0;
}
2. 广度优先搜索(BFS)
广度优先搜索是一种迭代的搜索方式,从一个起点出发,依次访问其所有相邻的节点,并将这些节点加入一个队列中,在队列中按照先进先出的顺序继续访问队列中的节点,直到队列为空为止。具体步骤如下:
(1)访问起点节点,并将其标记为已访问。
(2)将起点节点放入一个队列中。
(3)从队列中取出第一个节点,并访问其所有未被访问的相邻节点,并将这些节点加入队列中。
(4)重复步骤(3),直到队列为空为止。
(5)所有被访问过的节点组成了图的遍历。
#include<bits/stdc++.h>
using namespace std;void bfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {queue<int> q;visited[start] = true;q.push(start);while (!q.empty()) {int curr = q.front();cout << curr << " ";q.pop();for (int neighbor : graph[curr]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}
}int main() {int n = 6; // number of nodes// adjacency list representation of the graphvector<vector<int>> graph(n);graph[0] = {1, 2};graph[1] = {0, 2, 3, 4};graph[2] = {0, 1, 3};graph[3] = {1, 2, 4};graph[4] = {1, 3, 5};graph[5] = {4};// mark all nodes as not visitedvector<bool> visited(n, false);// perform BFS traversal starting from node 0bfs(graph, visited, 0);return 0;
}
相关文章:
图的遍历DFSBFS-有向图无向图
西江月・证明 即得易见平凡,仿照上例显然。留作习题答案略,读者自证不难。 反之亦然同理,推论自然成立。略去过程Q.E.D.,由上可知证毕。 有向图的遍历可以使用深度优先搜索(DFS)和广度优先搜索(…...
【NLP】深入浅出全面回顾注意力机制
深入浅出全面回顾注意力机制 1. 注意力机制概述2. 举个例子:使用PyTorch带注意力机制的Encoder-Decoder模型3. Transformer架构回顾3.1 Transformer的顶层设计3.2 Encoder与Decoder的输入3.3 高并发长记忆的实现self-attention的矩阵计算形式多头注意力(…...
Linux应用编程的read函数和Linux驱动编程的read函数的区别
Linux应用编程的read函数用于从文件描述符(文件、管道、套接字等)中读取数据。它的原型如下: ssize_t read(int fd, void *buf, size_t count);其中,fd参数是文件描述符,buf是用于存储读取数据的缓冲区,co…...
Kubernetes(K8s)从入门到精通系列之十:使用 kubeadm 创建一个高可用 etcd 集群
Kubernetes K8s从入门到精通系列之十:使用 kubeadm 创建一个高可用 etcd 集群 一、etcd高可用拓扑选项1.堆叠(Stacked)etcd 拓扑2.外部 etcd 拓扑 二、准备工作三、建立集群1.将 kubelet 配置为 etcd 的服务管理器。2.为 kubeadm 创建配置文件…...
使用动态规划实现错排问题-2023年全国青少年信息素养大赛Python复赛真题精选
[导读]:超平老师计划推出《全国青少年信息素养大赛Python编程真题解析》50讲,这是超平老师解读Python编程挑战赛真题系列的第15讲。 全国青少年信息素养大赛(原全国青少年电子信息智能创新大赛)是“世界机器人大会青少年机器人设…...
大规模向量检索库Faiss学习总结记录
因为最近要使用到faiss来做检索和查询,所以这里只好抽出点时间来学习下,本文主要是自己最近学习的记录,来源于网络资料查询总结,仅用作个人学习总结记录。 Faiss的全称是Facebook AI Similarity Search,是FaceBook的A…...
SpringCloudAlibaba之Sentinel(一)流控篇
前言: 为什么使用Sentinel,这是一个高可用组件,为了使我们的微服务高可用而生 我们的服务会因为什么被打垮? 一,流量激增 缓存未预热,线程池被占满 ,无法响应 二,被其他服务拖…...
哪种模式ip更适合你的爬虫项目?
作为一名爬虫程序员,对于数据的采集和抓取有着浓厚的兴趣。当谈到爬虫ip时,你可能会听说过两种常见的爬虫ip类型:Socks5爬虫ip和HTTP爬虫ip。但到底哪一种在你的爬虫项目中更适合呢?本文将帮助你进行比较和选择。 首先,…...
优维低代码实践:对接数据
优维低代码技术专栏,是一个全新的、技术为主的专栏,由优维技术委员会成员执笔,基于优维7年低代码技术研发及运维成果,主要介绍低代码相关的技术原理及架构逻辑,目的是给广大运维人提供一个技术交流与学习的平台。 优维…...
docker 离线模式-部署容器
有网络的情况下下载需要的镜像 比如(下面以tomcat为例子,其他镜像类似) docker pull tomcat打包镜像文件到本地 docker save tomcat -o tomcat.tar将tomcat.tar 上传到内网服务器(无外网环境) 导入镜像 docker load -i tomcat.tar创建容器…...
MDN-HTTP
参考资料 文章目录 HTTP简介HTTP 和 HTTPSHTTP消息典型的HTTP会话HTTP响应状态HTTP安全HTTP CookieHTTP压缩 HTTP简介 HTTP(Hypertext Transfer Protocol)是一种用于在计算机网络中传输超文本和其他资源的应用层协议。他是互联网的基础协议之一&#x…...
【数据库】PostgreSQL中使用`SELECT DISTINCT`和`SUBSTRING`函数实现去重查询
在PostgreSQL中,我们可以使用SELECT DISTINCT和SUBSTRING函数来实现对某个字段进行去重查询。本文将介绍如何使用这两个函数来实现对resource_version字段的去重查询。 1. SELECT DISTINCT语句 SELECT DISTINCT语句用于从表中选择不重复的记录。如果没有指定列名&…...
笔记本WIFI连接无网络【实测有效,不用重启电脑】
笔记本Wifi连接无网络实测有效解决方案 问题描述: 笔记本买来一段时间后,WIFI网络连接开机一段时间还正常连接,但是过一段时间显示网络连接不上,重启电脑太麻烦,选择编写重启网络脚本解决。三步解决问题。 解决方案&a…...
Java课题笔记~ Spring 概述
Spring 框架 一、Spring 概述 1、Spring 框架是什么 Spring 是于 2003 年兴起的一个轻量级的 Java 开发框架,它是为了解决企业应用开发的复杂性而创建的。Spring 的核心是控制反转(IoC)和面向切面编程(AOP)。 Spring…...
2022 robocom 世界机器人开发者大赛-本科组(国赛)
RC-u1 智能红绿灯 题目描述: RC-u1 智能红绿灯 为了最大化通行效率同时照顾老年人穿行马路,在某养老社区前,某科技公司设置了一个智能红绿灯。 这个红绿灯是这样设计的: 路的两旁设置了一个按钮,老年人希望通行马路时会…...
【雕爷学编程】Arduino动手做(195)---HT16k33 矩阵 8*8点阵屏模块6
37款传感器与模块的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的&#x…...
Typescript]基础篇之 tsc 命令解析
[Typescript]基础[TOC]([Typescript]基础篇之 tsc 命令解析 tsc 命令概览编译参数说明--declaration--watch 这里是对 tsc 的一个详细介绍 tsc 命令概览 安装 Typescript 后可以使用 tsc 编译 ts 文件,tsc 命令是否支持其它参数 如果需要查看 tsc 支持的命令,或者…...
测试人员简单使用Jenkins
一、测试人员使用jenkins干什么? 部署测试环境 二、相关配置说明 一般由开发人员进行具体配置 1.Repository URL:填写git地址 2.填写开发分支,测试人员可通过相应分支进行测试环境的构建部署 当多个版本并行时,开发人员可以通过…...
使用RecyclerView构建灵活的列表界面
使用RecyclerView构建灵活的列表界面 1. 引言 在现代移动应用中,列表界面是最常见的用户界面之一,它能够展示大量的数据,让用户可以浏览和操作。无论是社交媒体的动态流、商品展示、新闻列表还是任务清单,列表界面都扮演着不可或…...
linux ubuntu安装mysql
在 Ubuntu 上安装 MySQL 的步骤如下: 更新系统软件包列表: sudo apt update 安装 MySQL 服务器: sudo apt install mysql-server 安装完成,可以使用以下命令检查 MySQL 服务器是否正在运行: sudo systemctl status mysql 如果 MyS…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
