代码随想录算法训练营第50天 | 图论理论基础、深搜理论基础、98. 所有可达路径、广搜理论基础

图论理论基础

题目链接/文章讲解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

了解图的基本概念,连通性,图的构造,图的遍历方式

深搜理论基础

题目链接/文章讲解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E6%B7%B1%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

了解dfs 和 bfs的大体区别,dfs的搜索过程以及代码框架。

98. 所有可达路径

题目链接/文章讲解:https://www.programmercarl.com/kamacoder/0098.%E6%89%80%E6%9C%89%E5%8F%AF%E8%BE%BE%E8%B7%AF%E5%BE%84.html

深度优先搜索:

1. 确认递归函数,参数

首先我们dfs函数一定要存一个图,用来遍历的,需要存一个目前我们遍历的节点,定义为x。

还需要存一个n,表示终点,我们遍历的时候,用来判断当 x==n 时候 标明找到了终点。

代码如下:

vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 0节点到终点的路径
// x:目前遍历的节点
// graph:存当前的图
// n:终点
void dfs (const vector<vector<int>>& graph, int x, int n) {

2. 确认终止条件

什么时候我们就找到一条路径了?

当目前遍历的节点 为 最后一个节点 n 的时候 就找到了一条 从出发点到终止点的路径。

代码如下:

// 当前遍历的节点x 到达节点n 
if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;
}

3. 处理目前搜索节点出发的路径

接下来是走 当前遍历节点x的下一个节点。

首先是要找到 x节点指向了哪些节点呢? 遍历方式是这样的:

for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点if (graph[x][i] == 1) { // 找到 x指向的节点,就是节点i}
}

接下来就是将 选中的x所指向的节点,加入到 单一路径来。

path.push_back(i); // 遍历到的节点加入到路径中来

进入下一层递归

dfs(graph, i, n); // 进入下一层递归

最后就是回溯的过程,撤销本次添加节点的操作。

path.pop_back(); // 回溯,撤销本节点

广搜理论基础 

题目链接/文章讲解:https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E5%B9%BF%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

了解广度优先搜索的使用场景、过程和代码框架

总结

第50天,继续加油

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/web/96507.shtml
繁体地址,请注明出处:http://hk.pswp.cn/web/96507.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

华为HCIE-云计算培训课程有哪些?

华为HCIE云计算认证是华为公司推出的高级别认证&#xff0c;对于想要在云计算领域发展&#xff0c;提高专业技能和竞争力的人来说具备极高的价值。接下里就来聊聊华为HCIE云计算的培训课程都有哪些&#xff1f;如何高效备考呢&#xff1f;一&#xff0c;HCIE云计算培训课程1、理…

DCS控制回路优化:基于WebSocket的实时参数远程调校方法论

说起来&#xff0c;我前段时间刚啃完一个化工厂DCS控制回路优化的硬骨头&#xff0c;用WebSocket搞成了实时参数远程调校&#xff0c;现在回想起来&#xff0c;满是能跟大家唠的实操经验&#xff0c;说不定你们以后碰到类似情况&#xff0c;能少走些冤枉路。先跟大家交代下背景…

《JVM如何排查OOM》

目录 一、什么是OOM&#xff1f; 二、OOM排查的整体思路 三、OOM排查工具大全 四、实战&#xff1a;不同OOM场景的排查方法 场景1&#xff1a;Java heap space 场景2&#xff1a;Metaspace 场景3&#xff1a;GC overhead limit exceeded 五、高级排查技巧 1. 使用Arth…

ubuntu22.04 安装Docker

一、更新系统包索引sudo apt update && sudo apt upgrade -y二、安装必要依赖安装 curl、gnupg等工具&#xff0c;用于添加 Docker 官方 GPG 密钥和仓库&#xff1a;sudo apt install -y ca-certificates curl gnupg三、添加 Docker 官方 GPG 密钥sudo install -m 0755…

高低压隔离器的技术演进与行业赋能

电力电子系统的安全架构与效率升级&#xff0c;始终依赖高低压电路间的可靠隔离。高低压隔离器作为能量传输与信号控制的核心媒介&#xff0c;通过持续迭代的绝缘技术与结构创新&#xff0c;为新能源装备、工业驱动系统提供底层安全屏障。其阻断电位差传导、抑制电磁干扰的能力…

嵌入式 - ARM5

一、led点灯代码优化1. 配置寄存器volatile1.​​禁止优化​​不对该变量的读写操作进行任何优化&#xff08;如删除“冗余”读取或延迟写入&#xff09;。2.​​强制内存访问​​每次访问该变量时&#xff0c;必须直接从内存&#xff08;或硬件寄存器&#xff09;中读取或写入…

SSH登录管理

两种配置方法-密码 -密钥&#xff08;免密&#xff09;ansible 默认 rhel9 禁止 root 用密码登陆&#xff0c;不禁止用密钥登陆 ---修改方式----vim /etc/ssh/sshd_config 修改此文件#PermitRootLogin prohibit-passwordPermitRootLogin yes 改为允许systemctl res…

远程连接--向日葵

下载安装卸载 向日葵语言设置 点击下面的图标,点击"设置": 问题解决 向日葵被连接之后自动黑屏 取消下面的勾选框: 向日葵连接之后黑屏 检查系统的协议: echo $XDG_SESSION_TYPE 如果是: wayland 需要切换为x11. 设置永久默认使用 X11: sudo vi /etc/gdm3/custom…

Liunx执行source /etc/profile 报错, -bash: HISTTIMEFORMAT: readonly variable

今天在配置java环境变量时&#xff0c;执行source /etc/profile报错&#xff0c;系统是统信OS&#xff0c;花了好长时间才解决&#xff0c;在这记录一下&#xff0c;希望能帮助到大家问题截图提示HISTTIMEFORMAT和PROMPT_COMMAND变量时只读变量&#xff0c;不能设置属性值解决办…

什么是达林顿管?

简单来说&#xff0c;达林顿管是一个“电流放大器中的大力士”。它的核心目的是用非常小的输入电流&#xff08;基极电流&#xff09;去控制一个非常大的输出电流&#xff08;集电极电流&#xff09;。达林顿管是由两个三极管串联而成&#xff0c;放大倍数是两个三极管的放大倍…

嵌入式Linux学习_rk3588移植无线网卡驱动

记录移植无线网卡驱动遇到的各种问题&#xff1a; 从官网上下载8821的驱动源码复制一份上面的CONFIG_PLATFORM_ARM_RK2818&#xff0c;改成3588&#xff0c;然后选项改成y&#xff0c;并把autodetect关掉。 找到CONFIG_PLATFORM_ARM_RK2818&#xff0c;复制一份&#xff0c;改成…

MCP专题五、MCP 的未来趋势与展望

MCP专题五:MCP 的未来趋势与展望 5.1 引言 本专题前四章我们系统性地学习了 MCP(Model Context Protocol)的 发展背景、核心机制、Python 实战方法以及典型应用场景。可以看到,MCP 并不仅仅是一个技术标准,它更像是 大模型与外部世界沟通的桥梁,推动了 AI 应用从“实验…

C++ Dijkstra堆优化算法

时间复杂度为&#xff1a;O((nm)logn)算法特点&#xff1a;非负边权、单源最短路、顶点数、边数<1000000&#xff0c;数据结构前置&#xff1a;领接表、哈希表、二叉堆算法&#xff1a;第一步&#xff0c;建图&#xff0c;任何算法我们都要去思考&#xff0c;用什么数据结构…

网页设计作业02

<!DOCTYPE html> <html> <head><meta charset"utf-8"/><title>网页设计作业</title> </head> <body><h2>问卷调查</h2><p><strong>1、你是通过什么途径来到绿叶学习网的&#xff1f;</s…

每日算法题推送-->今日专题——双指针法

题目1&#xff1a;https://leetcode.cn/problems/move-zeroes 小编刚看到这道题的时候&#xff0c;想到的第一个方法就是建立一个与原数组等大的新的数组&#xff0c;然后遍历原数组&#xff0c;如果遇到元素值不为0的元素&#xff0c;就将这个元素放到新数组中&#xff0c;直到…

告别单次对话:上下文工程如何重塑AI应用架构

1. 前言人工智能应用开发领域正在经历一场静悄悄的变革。去年此时&#xff0c;提示工程&#xff08;Prompt Engineering&#xff09;还是各大技术论坛的热门话题&#xff0c;开发者们热衷于分享各种精心设计的提示词模板&#xff0c;试图通过单次交互获得理想的大模型输出。然而…

PM2 管理后端(设置项目自启动)

查看pm2管理pm2 list ┌────┬──────────────┬─────────────┬─────────┬─────────┬──────────┬────────┬──────┬───────────┬──────────┬──────────┬──…

CCN中商再获三项知识产权,为数字化服务添动能

上海中商网络股份有限公司&#xff08;CCN中商&#xff09;依托持续的研发投入与深厚的技术积淀&#xff0c;在知识产权领域再获重要突破——成功收获三项知识产权&#xff0c;囊括实用新型专利《一种3D霓彩智感双条光柱印刷用全自动生产线》、发明专利《一种一物一码关联系统及…

使用LTspice仿真一个异步BUCK电路

确定异步BUCK的规格 输入电压&#xff08;Vin&#xff09;&#xff1a;12V 输出电压&#xff08;Vout&#xff09;&#xff1a;6V 最大输出电流&#xff08;Iout&#xff09;&#xff1a;3A 开关频率&#xff08;fsw&#xff09;&#xff1a;400kHz 输出电压纹波&#xff08;Δ…

R语言对excel中多个sheet子表批量进行地理探测器计算

## 基本设置 ## 1) 设定你的工作目录&#xff08;保持你的原路径不变&#xff09; setwd("D:/*****/*****/******")## 2) 文件名&#xff08;与xlsx实际名字保持一致&#xff09; xlsx_file <- "驱动因素&#xff08;中低收入&#xff09;.xlsx"## 依…