C++学习/复习补充记录 --- 图论(深搜,广搜)

图的度

无向图:

连接某节点的边数,即为该节点的【度】。

(无向图中,有5条边连接节点4,则节点4的度为5。)

有向图:

出度:从该节点出发的边的个数。

入度:指向该节点边的个数。

(有向图中,

从节点3出发的边的个数是2,则节点3的入度为2;

指向节点3的边的个数是5,则出度为5)

连通性

(无向图)

连通图:在无向图中,任何两个节点都是可以到达的图。

非连通图:在无向图中,存在有节点不能到达其他节点的图。

连通图
非连通图(节点1 不能到达节点4)

(有向图)

强连通图:在有向图中,任何两个节点是可以相互到达的图。

图的存储

邻接表

邻接矩阵

一、深搜 与 广搜

数据结构与算法 | 深搜(DFS)与广搜(BFS)_深搜广搜算法-CSDN博客

深度优先搜索理论基础

深搜和广搜的区别

(通俗版)

        广搜(bfs)是一圈一圈的搜索过程,

        深搜(dfs)是一条路跑到黑然后再回溯。

  • dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,再换方向(换方向的过程就涉及到了回溯)。
  • bfs是先把本节点所连接的所有节点遍历一遍,走到下一个节点的时候,再把连接节点的所有节点遍历一遍,搜索方向更像是广度,四面八方的搜索过程。

二叉树的递归法,就是dfs。

二叉树的迭代法,就是bfs(广度优先搜索)。

所以dfs,bfs其实是基础搜索算法,也广泛应用与其他数据结构与算法中

深度优先搜索(Depth First Search)

深搜dfs关键就两点:

  • 搜索方向,是认准一个方向搜,直到碰壁之后再换方向
  • 换方向是撤销原路径,改为节点链接的下一个路径,回溯的过程。

因为dfs搜索可一个方向,并需要回溯,所以用递归的方式来实现是最方便的。

回溯链接:C++学习/复习补充记录 --- 递归、回溯_c++中回溯是啥-CSDN博客

深搜三部曲

1、确认递归函数,参数

2、确认终止条件

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


深搜代码模板:

//1、确认递归函数,参数
vector<vector<int>> result; // 保存符合条件的所有路径(存放结果组合的vector)
vector<int> path; // 起点到终点的路径(单个组合结果)void dfs (图,目前搜索的节点)  {if (剪枝条件) return;//剪枝//2、确认终止条件if (终止条件) {result.push_back(path);//存放结果;return;}//3、处理目前搜索节点出发的路径for (选择:本层节点所连接的其他节点) {处理节点;(做选择)dfs(图,选择的节点); // 递归回溯,撤销处理结果(撤销选择)}
}

(回溯撤销处理结果其实就是:撤回一步,回到上一步重新走另一个方向。)

广度优先搜索(Breadth First Search)

1、应用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路

2、实现方式

用队列的话,就是保证每一圈都是一个方向去转,例如统一顺时针或者逆时针

因为队列是先进先出,加入元素和弹出元素的顺序是没有改变的。

如果用栈的话,就是第一圈顺时针遍历,第二圈逆时针遍历,第三圈有顺时针遍历

因为栈是先进后出,加入元素和弹出元素的顺序改变了。

广搜不需要注意 转圈搜索的顺序 !

广搜代码模板:

int dir[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 }; // 表示四个方向
// grid 是地图,也就是一个二维数组
// visited标记访问过的节点,不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({ x, y }); // 起始节点加入队列visited[x][y] = true; // 只要加入队列,立刻标记为访问过的节点while (!que.empty()) { // 开始遍历队列里的元素pair<int, int> cur = que.front(); que.pop(); // 从队列取元素int curx = cur.first;int cury = cur.second; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了,直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({ nextx, nexty });  // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记,避免重复访问}}}
}

(该模板针对的是如下图的四方格地图)

实际应用

输入数据的含义:

例一

输入:graph = [[1,2],[3],[3],[]]

节点0可链接到的节点有:节点1,节点2;

节点1可链接到的节点有:节点3;

节点2可链接到的节点有:节点3;

节点3可链接到的节点有:无。

例二

输入:graph = [[4,3,1],[3,2,4],[3],[4],[]]

节点0可链接到的节点有:节点4,节点3,节点1;

节点1可链接到的节点有:节点3,节点2,节点4;

节点2可链接到的节点有:节点3;

节点3可链接到的节点有:节点4;

节点4可链接到的节点有:无。

1.1 所有可能的路径 (深搜)

给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序

 graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。

class Solution {vector<vector<int>> result;//符合条件的路径集合vector<int> path;//0节点到终点的路径void dfs(vector<vector<int>>& graph, int cur) {//cur为当前遍历到的节点if (cur == graph.size() - 1) {//要求从节点0到节点n-1的路径并输出,所以是 graph.size() - 1result.push_back(path);return;//已找到一条符合条件的路径}for (int i = 0; i < graph[cur].size(); i++) {//遍历当前节点可链接到的所有节点path.push_back(graph[cur][i]);//当前选择的链接节点尝试加入dfs(graph, graph[cur][i]);//加入下一层递归path.pop_back();//当前选择的链接节点走不通,不带上玩,腾出位置尝试另一个}}
public:vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);//所有路径皆是从节点0出发dfs(graph, 0);//开始遍历return result;}
};

1.2 

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

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

相关文章

Idea_服务器自动化部署_傻瓜式教程

使用Alibaba Cloud Toolkit 在 IntelliJ IDEA 中一键部署项目到服务器 1. 安装 Alibaba Cloud Toolkit 插件 确保 IntelliJ IDEA 版本为 2018.3 或以上。打开 IntelliJ IDEA&#xff0c;进入 File -> Settings -> Plugins&#xff0c;搜索并安装 Alibaba Cloud Toolkit…

【Python基础】字典类型

本文收录于 《Python编程入门》专栏&#xff0c;从零基础开始&#xff0c;分享一些Python编程基础知识&#xff0c;欢迎关注&#xff0c;谢谢&#xff01; 文章目录 一、前言二、Python 字典类型2.1 访问字典里的值2.2 修改字典2.3 删除字典元素2.4 字典键值的特性2.5 遍历字典…

Vision Transformer (ViT) + 代码【详解】

文章目录 1、Vision Transformer (ViT) 介绍2、patch embedding3、代码3.1 class embedding Positional Embedding3.2 Transformer Encoder3.3 classifier3.4 ViT总代码 1、Vision Transformer (ViT) 介绍 VIT论文的摘要如下&#xff0c;谷歌翻译如下&#xff1a; 虽然 Transf…

《JavaEE进阶》----10.<SpringMVC应用分层:【三层架构】>

本篇博客我们主要讲解 1.应用的分层&#xff1a;三层架构 2.Spring MVC和三层架构的区别和联系 3.软件设计原则&#xff1a;高内聚低耦合 4.应用分层的好处 5.通过应用分层后的代码示例 一、三层架构简介 阿里开发手册中,关于工程结构部分,定义了常见工程的应用分层结构: 上图…

【Java 基础】:三大特征之多态

✨ 杏花疏影里&#xff0c;吹笛到天明 &#x1f30f; &#x1f4c3;个人主页&#xff1a;island1314 &#x1f525;个人专栏&#xff1a;java学习 ⛺️ 欢迎关注&#xff1a;&#x1f44d;点赞 &#x1f442;&…

u盘格式化数据还能恢复吗?点击了解实用教程

U盘是电子数据存储设备&#xff0c;我们主要用它来转移数据、随身携带数据等。同时U盘在使用过程中常会遇到问题&#xff0c;比如U盘中毒&#xff0c;U盘中毒会导致里面保存的数据文件无法读取&#xff0c;我们需要进行U盘格式化。格式化之后的U盘才可以继续使用&#xff0c;那…

软件测试-Selenium+python自动化测试

目录 会用到谷歌浏览器Chrome测试,需要下载一个Chromedriver(Chrome for Testing availability)对应自己的浏览器版本号选择。 一、元素定位 对html网页中的元素进行定位,同时进行部分操作。 1.1一个简单的模板 from selenium import webdriver from selenium.webdrive…

本地部署AList并挂载小雅超集结合内网穿透实现无公网IP远程访问

文章目录 前言1. 本地部署AList2. AList挂载网盘3. 部署小雅alist3.1 Token获取3.2 部署小雅3.3 挂载小雅alist到AList中 4. Cpolar内网穿透安装5. 创建公网地址6. 配置固定公网地址 &#x1f4a1; 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff…

42.接雨水

42.接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1…

一文搞懂微服务架构之限流

前置知识 限流是通过限制住流量大小来保护系统&#xff0c;能够解决异常突发流量打崩系统的问题。例如常见的某个攻击者在攻击你维护的系统&#xff0c;那么限流就是极大程度上保护住你的系统。 算法 限流算法也可以像负载均衡算法那样&#xff0c;划分成静态算法和动态算法…

【Java】—— Java面向对象高级:关键字static的使用

目录 1. 关键字&#xff1a;static 1.1 类属性、类方法的设计思想 1.2 static关键字 1.3 静态变量 1.3.1 语法格式 1.3.2 静态变量的特点 1.4 静态方法 1.4.1 语法格式 1.4.2 静态方法的特点 1.5 练习 1. 关键字&#xff1a;static 回顾类中的实例变量&#xff08;即…

Android - Windows平台下Android Studio使用系统的代理

这应该是第一篇Android的博文吧。以后应该会陆续更新的。记录学习Android的点点滴滴。 之前也看过&#xff0c;不过看完书就忘了&#xff0c;现在重拾Android&#xff0c;记录学习历程。 为何要用代理 因为更新gradle太慢了。 如何使用系统的代理 先找到系统代理的ip和端口。…

C++学习笔记----6、内存管理(一)---- 使用动态内存(3)

3.2、对象数组 对象数组与原型/基础类型的数组没有什么不同&#xff0c;除了元素的初始化之外。当你使用new[N]去分配N个对象&#xff0c;就把N个连续的块空间分配出去了&#xff0c;每一个块空间可以放一个单独的对象。对于对象数组&#xff0c;New[]对每一个对象自动调用0参数…

激光雷达产品介绍

与传统激光雷达线性重复式的扫描方式不同&#xff0c;Livox mid系列激光雷达扫描路径不会重复。且视场中激光照射到的区域面积会随时间增大&#xff0c;这就意味着视场覆盖率随时间推移而显著提高。 内容参考自《解构大疆旗下 Livox Mid 激光雷达非重复扫描技术》作者&#xff…

【C++11(一)之入门基础)】

文章目录 C简介统一的列表初始化&#xff5b;&#xff5d;初始化 std::initializer_liststd::initializer_list是什么类型&#xff1a;std::initializer_list使用场景&#xff1a; 声明autodecltypenullptr STL中一些变化 C简介 在2003年C标准委员会曾经提交了一份技术勘误表(…

#ARM开发 笔记

课程介绍 ARM开发 --> Linux移植 --> 驱动开发 前后联系&#xff1a;ARM和系统移植为驱动开发学习做准备工作 所需知识&#xff1a;C语言基础及STM32需要的硬件知识 学习方法 学习流程、思想和解决问题的方法即可 知道驱动的基本框架以及基本开发要求 底层课程导学 接口技…

linux小程序-进度条

文章目录 pro.hpro.cmain.cmakefile测试 pro.h #pragma once#include <stdio.h>typedef void(*callback_t)(double, double);void probar(double total, double current);pro.c #include "pro.h" #include <string.h> #include <unistd.h> #defi…

webshell绕过样本初体验

目录 一&#xff1a;前景 二&#xff1a;样本 样本一&#xff1a; 样本二&#xff1a; 样本三&#xff1a; 样本4&#xff1a; 样本5&#xff1a; 一&#xff1a;前景 在我们日常的网站中百分之一百是存在一些安全设备来拦截我们的webshell的&#xff0c;一般情况…

Kafka大厂面试14问(附答案)

怎么保证顺序消费&#xff1f; 同一个生产者发送到同一分区的消息&#xff0c;先发送的比后发送的offset要小。同一生产者发送到不同分区的消息&#xff0c;消息顺序无法保证。 怎么解决这个问题&#xff1f; 给一个topic只设置一个分区 相同key会发给一个分区 怎么保证幂…

[有彩蛋]大模型独角兽阶跃星辰文生图模型Step-1X上线,效果具说很炸裂?快来看一手实测!

先简单介绍一下阶跃星辰吧 公司的创始人兼CEO是姜大昕博士&#xff0c;他在微软担任过全球副总裁&#xff0c;同时也是微软亚洲互联网工程研究院的副院长和首席科学家。 2024年3月&#xff0c;阶跃星辰发布了Step-2万亿参数MoE语言大模型预览版&#xff0c;这是国内初创公司首…