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

DFS算法查找所有路径详解

DFS算法查找所有路径详解

算法介绍

深度优先搜索(Depth-First Search,DFS)是一种图遍历算法,它从起始节点开始,沿着一条路径尽可能深入,直到达到最深的节点,然后回溯到前一节点,继续探索下一条路径。DFS通常使用递归或栈(非递归)来实现。

以下是DFS算法的基本步骤:

  • 选择起始节点: 从图中选择一个起始节点作为当前节点;
  • 标记节点: 标记当前节点为已访问,以防止重复访问;
  • 探索邻居节点: 对于当前节点的未访问邻居节点,选择一个邻居节点作为新的当前节点,然后重复步骤2和步骤3;
  • 回溯: 如果当前节点没有未访问的邻居节点,回溯到上一节点,重复步骤3;
  • 重复过程: 重复步骤3和步骤4,直到所有节点都被访问。

递归实现的伪代码

function DFS(node):if node is not visited:mark node as visitedfor each neighbor of node:DFS(neighbor)

非递归实现的伪代码

DFS的非递归实现通常使用栈来模拟递归调用的过程,具体步骤如下:

  • 创建一个空栈,并将起始节点压入栈中;
  • 进入循环,直到栈为空;
  • 弹出栈顶节点作为当前节点;
  • 如果当前节点未访问,标记为已访问;
  • 遍历当前节点的邻居节点,将未访问的邻居节点压入栈中;
  • 重复步骤3到步骤5,直到栈为空为止。

注意:在处理连通图时可能导致栈溢出,因此在实际应用中可能需要注意栈深度的问题。
伪代码如下:

function DFS_non_recursive(start):stack = empty stackpush start onto stackwhile stack is not empty:current = pop from stackif current is not visited:mark current as visitedfor each neighbor of current:push neighbor onto stack

具体算法实现

由于可能存在非常多的路径,我们设置一个maxLength,表示限制经过的节点个数。

void Graph::DFS(int current, int end, std::unordered_set<int>& visited, std::vector<int>& path, int maxLength)
{static int currentLength = 0;static int i = 1;visited.insert(current);path.push_back(current);if (path.size() <= maxLength) {if (current == end){// 生成路径for (int node : path) {std::cout<<node<<' ';}std::cout<<"路径总长度为:"<<currentLength<<std::endl;}else{for (int neighbor = 0; neighbor < V; ++neighbor){if (adjMatrix[current][neighbor] != INF && visited.find(neighbor) == visited.end()) {int edgeWeight = adjMatrixLength[current][neighbor];currentLength += edgeWeight;DFS(neighbor, end, visited, path, maxLength);currentLength -= edgeWeight; // 回溯时减去当前边的长度}}}}visited.erase(current);path.pop_back();
}

相关文章:

DFS算法查找所有路径详解

DFS算法查找所有路径详解 算法介绍 深度优先搜索&#xff08;Depth-First Search&#xff0c;DFS&#xff09;是一种图遍历算法&#xff0c;它从起始节点开始&#xff0c;沿着一条路径尽可能深入&#xff0c;直到达到最深的节点&#xff0c;然后回溯到前一节点&#xff0c;继…...

单片机的存储、堆栈与程序执行方式

一、单片机存储区域 如图所示位STM32F103ZET6的参数&#xff1a; 单片机的ROM&#xff08;内部FLASH&#xff09;&#xff1a;512KB&#xff0c;用来存放程序代码的空间。 单片机的RAM&#xff1a;64KB&#xff0c;一般都被分配为堆、栈、变量等的空间。 二、堆和栈的概念 …...

Web3开发成本和主要特性

多年来&#xff0c;技术不断进步&#xff0c;可帮助您的业务领先于竞争对手。如今&#xff0c;您可以看到许多更新和变化&#xff0c;使技术更加先进&#xff0c;对企业更加有用。到现在为止&#xff0c;web1.2和2.0比较流行&#xff0c;但是要知道web 3才是技术之父&#xff0…...

【数学建模美赛M奖速成系列】Matplotlib绘图技巧(一)

Matplotlib图像基础 写在前面1 基本绘图实例&#xff1a;sin、cos函数图2 plot()函数详解**kwargs参数&#xff1a; 3 matplotlib中绘图的默认配置4 设置图的横纵坐标的上下界5 设置横纵坐标上的记号6 调整图像的脊柱7 添加图例8 给一些特殊点加注释9 子图最后 写在前面 前面我…...

005、数据类型

1. 关于数据类型 Rust中&#xff0c;每个值都有其特定的数据类型&#xff0c;Rust会根据数据的类型来决定如何处理它们。 Rust是一门静态类型语言&#xff0c;它在编译程序的过程中就需要知道所有变量的具体类型。在大部分情况下&#xff0c;编译器可以根据我们如何绑定、使用变…...

软考网络工程师考试大纲(2018年最新版)

本书是全国计算机专业技术资格考试办公室组织编写的网络工程师考试大纲,本书除大纲内容外,还包括了人力资源和社会保障部、工业和信息化部的有关文件以及考试简介。 网络工程师考试大纲是针对本考试的计算机网络中级资格制定的。通过本考试的考生,可被用人单位择优聘任为工…...

【数据结构】栈【详解】

目录 栈的定义&#xff1a; 栈的声明与定义&#xff1a; 头文件的包含&#xff1a; 对栈的基本操作&#xff1a; 栈的初始化&#xff1a; 摧毁栈: 入栈&#xff1a; ​编辑 出栈&#xff1a; ​编辑 输出栈顶位置&#xff1a; 输出栈的当前大小&#xff1a; 判空操…...

CSS 纵向底部往上动画

<template><div class"container" mouseenter"startAnimation" mouseleave"stopAnimation"><!-- 旋方块 --><div class"box" :class"{ scale-up-ver-bottom: isAnimating }"><!-- 元素内容 --&g…...

常用的 MySQL 可视化客户端

数据库可视化客户端&#xff08;GUI&#xff09;让用户在和数据库进行交互时&#xff0c;能直观地查看、创建和修改对象&#xff0c;如&#xff1a;表、行和列。让数据库操作变得更方便了。 今天&#xff0c;我们来了解下目前市场上最常用的 MySQL 可视化客户端。 官方&#x…...

C#使用SyntaxTree获取.cs文件中的属性名和注释

有时候&#xff0c;我们可能需要获取.cs文件中的属性和对应的注释来生成一些代码&#xff0c;比如SQL查询什么的。 但使用正则匹配有时候会不准确。搜索了下&#xff0c;发现微软提供了代码解析的API。 具体如下两个方法&#xff1a; /// <summary> /// 获取所有属性和…...

基于价值认同的需求侧电能共享分布式交易策略(matlab完全复现)

目录 1 主要内容 2 部分程序 3 程序结果 4 下载链接 1 主要内容 该程序完全复现《基于价值认同的需求侧电能共享分布式交易策略》&#xff0c;针对电能共享市场的交易机制进行研究&#xff0c;提出了基于价值认同的需求侧电能共享分布式交易策略&#xff0c;旨在降低电力市…...

门控循环单元(GRU)-多输入回归预测

目录 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 亮点与优势&#xff1a; 二、实际运行效果&#xff1a; 三、部分程序&#xff1a; 四、全部代码数据分享&#xff1a; 一、程序及算法内容介绍&#xff1a; 基本内容&#xff1a; 本代码基于Matlab平台编译…...

电池管理系统BMS中SOC算法通俗解析(二)

下面简单介绍下我们BMS保护板使用的SOC估算方法。我们算法的主要是针对电流积分法计算SOC的局限性进行改进&#xff1a; ●电池包第一次上电使用开路电压法估算SOC。第一次上电&#xff0c;根据电池包厂家给出的电压和剩余容量二维关系图大概估算出目前电池包的剩余容量即SOC。…...

YOLOv5改进 | 2023主干篇 | 华为最新VanillaNet主干替换Backbone实现大幅度长点

一、本文介绍 本文给大家来的改进机制是华为最新VanillaNet网络&#xff0c;其是今年最新推出的主干网络&#xff0c;VanillaNet是一种注重极简主义和效率的神经网络架构。它的设计简单&#xff0c;层数较少&#xff0c;避免了像深度架构和自注意力这样的复杂操作(需要注意的是…...

爬虫工作量由小到大的思维转变---<第三十三章 Scrapy Redis 23年8月5日后会遇到的bug)>

前言: 收到回复评论说,按照我之前文章写的: 爬虫工作量由小到大的思维转变---&#xff1c;第三十一章 Scrapy Redis 初启动/conn说明书)&#xff1e;-CSDN博客 在启动scrapy-redis后,往redis丢入url网址的时候遇到: TypeError: ExecutionEngine.crawl() got an unexpected …...

PostgreSQL | 概念 | 什么是OLTPOLAP?

什么是OLTP&OLAP&#xff1f; 大白话理解&#xff1a;业务系统都可以称作OLTP&#xff0c;基于业务系统产生的数据进行数据分析和决策的都可以称为OLAP。 OLTP OLTP&#xff08; Online Transaction Processing&#xff09;在线事务处理系统 用途&#xff1a; 用于支持日…...

2023年成都市中等职业学校学生技能大赛“网络搭建及应用”赛项竞赛样卷

2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 &#xff08;总分1000分&#xff09; 目录 2023年成都市中等职业学校学生技能大赛 “网络搭建及应用”赛项竞赛样卷 网络建设与调试项目&#xff08;500分&#xff09; 服务器搭建与运维项目&#xff08;…...

Angular进阶之六:Progressive rendering

简介 Progressive Rendering 是一种提高 Web 应用性能的方法&#xff0c;允许页面在加载过程中逐步呈现&#xff0c;以提高用户体验。在本文中&#xff0c;我们将探讨如何在 Angular 中通过自定义指令实现 Progressive Rendering&#xff0c;特别是处理从服务器获取大量数据的…...

机器人中的数值优化之线性共轭梯度法

欢迎大家关注我的B站&#xff1a; 偷吃薯片的Zheng同学的个人空间-偷吃薯片的Zheng同学个人主页-哔哩哔哩视频 (bilibili.com) 本文ppt来自深蓝学院《机器人中的数值优化》 目录 1.无约束优化方法对比 2.Hessian-vec product 3.线性共轭梯度方法的步长​编辑 4.共轭梯度…...

嵌入式Linux C语言介绍

目录 一.前言 二.C语言的特点 一.前言 开发工具通常依赖于操作系统提供的各种功能和服务。许多开发工具都基于操作系统的API&#xff08;应用程序接口&#xff09;进行开发&#xff0c;这些API提供了文件处理、网络通信、图形界面等核心功能。没有操作系统的支持&#xff0c;…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...