蓝桥杯备考——算法

一、排序

冒泡排序、选择排序、插入排序、 快速排序、归并排序、桶排序

 

二、枚举

三、二分查找与二分答案

四、搜索(DFS)

DFS(DFS基础、回溯、剪枝、记忆化)

1.DFS算法(深度优先搜索算法)

深度优先搜索( DFS )是一种用于遍历或搜索图或树的算法,它从起始节点开始,沿着一条路径一直深入直到无法继续为止,然后回溯到上一个节点继续探索。 DFS 使用来记录遍历的路径,它优先访问最近添加到栈的节点。

DFS 的主要优点是简单且易于实现,它不需要额外的数据结构来记录节点的访问情况,仅使用栈来存储遍历路径。然而, DFS 可能会陷入无限循环中,因为它不考虑节点是否已经访问过。

  对于一个连通图,深度优先搜索遍历的过程如下:

(1)从图中某个顶点v出发,访问v;

(2)找到刚访问过的顶点的第一个未被访问的邻接点,访问该顶点。 以该顶点为新顶点,重 复此步骤, 直至刚访问过的顶点没有未被访问的邻接点为止。

(3)返回前一个访问过的且仍有未被访问的邻接点的顶点,找出该顶点的下一个未被访问的邻接点, 访问该顶点。

(4)重复步骤 (2) 和(3), 直至图中所有顶点都被访问过,搜索结束。 

677c768ab5eb8b76c9f1c64d779c35b6.png

顶点访问序列:v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7

DFS 使用来记录遍历的路径,它优先访问最近添加到栈的节点。

 显然, 深度优先搜索遍历连通图是一个递归的过程。 为了在遍历过程中便千区分顶点是否已

 被访问,需附设访问标志数组 visited[n] , 其初值为 "false", 一旦某个顶点被访问,则其相应的分

量置为 "true"。  

python语言:

# 图的DFS遍历
def dfs(graph, start, visited):# 访问当前节点print(start, end=' ')# 标记当前节点为已访问visited[start] = True# 遍历当前节点的邻居节点for neighbor in graph[start]:# 如果邻居节点未被访问,则继续深度优先搜索if not visited[neighbor]:dfs(graph, neighbor, visited)# 图的邻接表表示
graph = {'1': ['2', '3'],'2': ['2', '4', '5'],'3': ['1', '6', '7'],'4': ['2','8'],'5': ['2','8'],'6': ['3','7'],'7': ['3','6'],'8': ['4','5']
}# 标记节点是否已访问的列表
visited = {node: False for node in graph}# 从节点A开始进行DFS遍历
print("DFS遍历结果:")
dfs(graph, '1', visited)

C++ / C语言:

算法1.深度优先搜索遍历连通图

// 1. 深度优先搜索遍历连通图
bool visited[MVNum];         // 访问标志数组,其初值设为“false”
void DFS(Graph G, int v)
{    // 从第v个顶点出发 递归地深度优先遍历图Gcout << v; visited[v] = true;for (w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))// 依次检查v的所有邻接点w,FirstAdjVex(G,v)表示v的第一个邻接点// NextAdjVex(G,v,w)表示v相对于w的下一个邻接点,w>=0表示存在邻接点if (!visited[w])    DFS(G,w);      // 对v的尚未访问的邻接点w递归调用DFS
}

算法2.深度优先搜索遍历 非连通图

若是非连通图, 上述遍历过程执行之后, 图中一定还有顶点未被访间,需要从图中另选

一个未被访问的顶点作为起始点 , 重复上述深度优先搜索过程, 直到图中所有顶点均被访问

过为止。这样, 要实现对非连通图的遍历,需要循环调用算法 1, 具体实现如算法 2所示。

void DFSTraverse(Graph G) 
{ //对非连通图G做深度优先遍历for(v=O;v<G.vexnum;++v)    visited[v]=false;    // 访问标志数组初始化for(v=O;v<G.vexnum;++v)     // 循环调用算法1if(!visited[v])    DFS(G,v);     // 对尚未访问的顶点调用DFS
}

算法 3  采用 邻接矩阵 表示图的深度优先搜索遍历

void DFS_AM(AMGraph G,int v) 
{    // 图G为 邻接矩阵类型,从第v个顶点出发深度优先搜索遍历图Gcout<<v; visited[v]=true;     // 访问第v个顶点,并置访问标志数组相应分址值为truefor(w=O; w<G.vexnum; w++)     // 依次检查邻接矩阵 v所在的行if((G.arcs[v][w] !=O) && (!visited[w]))    DFS(G,w);  //G.arcs[v][w] ! =0表示w是v的邻接点, 如果w未访问, 则递归调用DFS
}

算法 4 采用邻接表表示图的深度优先搜索遍历

void DFS_AL (ALGraph G,int v) 
{    //图G为 邻接表 类型, 从第v个顶点出发深度优先搜索遍历图Gcout<<v; visited[v]=true;  // 访问第v个顶点,并置访问标志数组相应分量值为truep=G.vertices[v] .firstarc;   //p指向v的边链表的第一个边结点while(p!=NULL)     // 边结点非空{w=p->adjvex;           // 表示w是v的邻接点if(!visited[w])    DFS(G,w);    // 如果w未访问, 则递归调用DFSp=p->nextarc;         //p指向下一个边结点}
}

例题:1.最大连通

问题描述:(填空题)

小兰有一个30行60列的数字矩阵,矩阵中的每个数都是0或1。


110010000011111110101001001001101010111011011011101001111110010000000001010001101100000010010110001111100010101100011110 001011101000100011111111111010000010010101010111001000010100 101100001101011101101011011001000110111111010000000110110000 010101100100010000111000100111100110001110111101010011001011 010011011010011110111101111001001001010111110001101000100011 101001011000110100001101011000000110110110100100110111101011 101111000000101000111001100010110000100110001001000101011001 001110111010001011110000001111100001010101001110011010101110 001010101000110001011111001010111111100110000011011111101010 011111100011001110100101001011110011000101011000100111001011 011010001101011110011011111010111110010100101000110111010110 001110000111100100101110001011101010001100010111110111011011 111100001000001100010110101100111001001111100100110000001101 001110010000000111011110000011000010101000111000000110101101 100100011101011111001101001010011111110010111101000010000111 110010100110101100001101111101010011000110101100000110001010 110101101100001110000100010001001010100010110100100001000011 100100000100001101010101001101000101101000000101111110001010 101101011010101000111110110000110100000010011111111100110010 101111000100000100011000010001011111001010010001010110001010 001010001110101010000100010011101001010101101101010111100101 001111110000101100010111111100000100101010000001011101100001 101011110010000010010110000100001010011111100011011000110010 011110010100011101100101111101000001011100001011010001110011 000101000101000010010010110111000010101111001101100110011100 100011100110011111000110011001111100001110110111001001000111 111011000110001000110111011001011110010010010110101000011111 011110011110110110011011001011010000100100101010110000010011 010011110011100101010101111010001001001111101111101110011101

 如果从一个标为1的位置可以通过上下左右走到另一个标为1的位置,则称两个位置连通。与某一个标为1的位置连通的所有位置(包括自己)组成一个连通分块。

请问矩阵中最大的连通分块有多大?

答案:

import os
import sysdef dfs(x, y, num): # x,y是当前的位置,num是最大连通的数量vis[x][y] = 1   # 表明这个位置已经被搜素过了for dx,dy in [(1, 0), (-1, 0), (0,1), (0, -1)]:   # 标准的上下左右搜索current_x = x + dxcurrent_y = y + dyif 0 <= current_x < 30 and 0 <= current_y <60:  # 边界限制try:if vis[current_x][current_y] != 1 and data[current_x][current_y] == '1':  # 上下左右有位置没有被探索同时还是字符串的'1'num = dfs(current_x,current_y,num)except:   # 这里是方便找到如果输入错误是在哪,用来检查循环条件是否写错print(current_x)print(current_y)return num + 1    # 本身的1加上所有与它相连的numdata =[
"110010000011111110101001001001101010111011011011101001111110","010000000001010001101100000010010110001111100010101100011110","001011101000100011111111111010000010010101010111001000010100","101100001101011101101011011001000110111111010000000110110000","010101100100010000111000100111100110001110111101010011001011","010011011010011110111101111001001001010111110001101000100011","101001011000110100001101011000000110110110100100110111101011","101111000000101000111001100010110000100110001001000101011001","001110111010001011110000001111100001010101001110011010101110","001010101000110001011111001010111111100110000011011111101010","011111100011001110100101001011110011000101011000100111001011","011010001101011110011011111010111110010100101000110111010110","001110000111100100101110001011101010001100010111110111011011","111100001000001100010110101100111001001111100100110000001101","001110010000000111011110000011000010101000111000000110101101","100100011101011111001101001010011111110010111101000010000111","110010100110101100001101111101010011000110101100000110001010","110101101100001110000100010001001010100010110100100001000011","100100000100001101010101001101000101101000000101111110001010","101101011010101000111110110000110100000010011111111100110010","101111000100000100011000010001011111001010010001010110001010","001010001110101010000100010011101001010101101101010111100101","001111110000101100010111111100000100101010000001011101100001","101011110010000010010110000100001010011111100011011000110010","011110010100011101100101111101000001011100001011010001110011","000101000101000010010010110111000010101111001101100110011100","100011100110011111000110011001111100001110110111001001000111","111011000110001000110111011001011110010010010110101000011111","011110011110110110011011001011010000100100101010110000010011","010011110011100101010101111010001001001111101111101110011101"]
res = 0
vis = [[0 for i in range(60)] for j in range(30)]   # 标记数组
for i in range(30):  # i和j是位置for j in range(60):if data[i][j] == '1' and vis[i][j] == 0:num = 0num = dfs(i,j,num)res = max(num, res)
print(res)

例题2.

 

2. 广度优先搜索( BFS )算法

是一种用于遍历或搜索图或树的算法,它从起始节点开始,逐层地向外扩展,先访问当前节点的所有邻居节点,然后再访问邻居节点的邻居节点,直到遍历完所有节点。

BFS 使用队列来记录遍历的路径,它优先访问最早添加到队列的节点。 BFS 的主要优点是能够找到起始节点到目标节点的最短路径,因为它是逐层遍历的。

677c768ab5eb8b76c9f1c64d779c35b6.png

python语言

from collections import deque# 图的BFS遍历
def bfs(graph, start):# 使用队列来记录遍历路径queue = deque([start])# 标记节点是否已访问的集合visited = set([start])while queue:     # 当栈不为空node = queue.popleft()    # 左端出栈print(node, end=' ')for neighbor in graph[node]:if neighbor not in visited:queue.append(neighbor)    # 右端进栈visited.add(neighbor)# 图的邻接表表示
graph = {'1': ['2', '3'],'2': ['2', '4', '5'],'3': ['1', '6', '7'],'4': ['2','8'],'5': ['2','8'],'6': ['3','7'],'7': ['3','6'],'8': ['4','5']
}# 从节点A开始进行BFS遍历
print("BFS遍历结果:")
bfs(graph, '1')      # 1 2 3 4 5 6 7 8

python: collections模块——双向队列(deque)
类似于list的容器,可以快速的在队列头部和尾部添加、删除元素

 

3.  DFS 与 BFS 的对比

DFSBFS 是两种不同的图遍历算法,在不同的应用场景下具有不同的优势:

  • DFS 适用于找到起始节点到目标节点的路径,但不一定是最短路径。它通过递归的方式深入探索图的分支,因此对于深度较小的图或树, DFS 通常表现较好。
  • BFS 适用于找到起始节点到目标节点的最短路径。它通过逐层遍历图的节点,从而保证找到的路径是最短的。在需要寻找最短路径的情况下, BFS 是更好的选择

 

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

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

相关文章

【网络面试篇】其他面试题——Cookie、Session、DNS、CDN、SSL/TLS、加密概念

目录 一、HTTP 相关问题 1. Cookie 和 Session 是什么&#xff1f; &#xff08;1&#xff09;Cookie &#xff08;2&#xff09;Session 2. Cookie 的工作原理&#xff1f; 3. Session 的工作原理&#xff1f; 4. Cookie 和 Session 有什么区别&#xff1f; 二、其他问…

隧道论文阅读2-采用无人融合扫描数据的基于深度学习的垂直型隧道三维数字损伤图

目前存在的问题&#xff1a; 需要开发新的无人测量系统测量垂直隧道图像数据量巨大&#xff0c;基于深度学习完成损伤评估跟踪获取图像位置的困难&#xff0c;对大型基础设施感兴趣区域(roi)的2d和3d地图建立进行了研究&#xff0c;对整个目标结构的损伤定位仍然具有挑战性。为…

CCF-A类 HPCA 2025 重磅揭晓:录取数据公布

近日&#xff0c;第31届国际计算机体系结构领域顶级会议HPCA (International Symposium on High Performance Computer Architecture) 正式发布了2025年会议的录用通知&#xff01;本届会议共收到了534 篇提交论文&#xff0c;其中&#xff0c;112篇论文被接收&#xff0c;整体…

Linux应用——线程池

1. 线程池要求 我们创建线程池的目的本质上是用空间换取时间&#xff0c;而我们选择于 C 的类内包装原生线程库的形式来创建&#xff0c;其具体实行逻辑如图 可以看到&#xff0c;整个线程池其实就是一个大型的 CP 模型&#xff0c;接下来我们来完成它 2. 整体模板 #pragma …

IDM扩展添加到Edge浏览器

IDM扩展添加到Edge浏览器 一般情况下&#xff0c;当安装IDM软件后&#xff0c;该软件将会自动将IDM Integration Module浏览器扩展安装到Edge浏览器上&#xff0c;但在某些情况下&#xff0c;需要我们手动安装&#xff0c;以下为手动安装步骤 手动安装IDM扩展到Edge浏览器 打…

docker 拉取MySQL8.0镜像以及安装

目录 一、docker安装MySQL镜像 搜索images 拉取MySQL镜像 二、数据挂载 在/root/mysql/conf中创建 *.cnf 文件 创建容器,将数据,日志,配置文件映射到本机 检查MySQL是否启动成功&#xff1a; 三、DBeaver数据库连接 问题一、Public Key Retrieval is not allowed 问题…

深入探索Waymo自动驾驶技术发展:从DARPA挑战赛到第五代系统的突破

引言 自动驾驶技术正引领着未来出行方式的革命&#xff0c;而Waymo作为全球自动驾驶领域的先锋&#xff0c;始终走在技术发展的最前沿。本文基于Waymo联席CEO德米特里多尔戈夫&#xff08;Dmitri Dolgov&#xff09;在No Priors节目中的访谈&#xff0c;全面介绍Waymo的技术发展…

鸿蒙移动应用开发-------初始arkts

一. 什么是arkts ArkTS是HarmonyOS优选的主力应用开发语言。 ArkTS围绕应用开发在TypeScript&#xff08;简称TS&#xff09;生态基础上做了进一步扩展&#xff0c;保持了TS的基本风格&#xff0c;同时通过规范定义强化开发期静态检查和分析&#xff0c;提升程序执行稳定性和…

c++ 输入三条边 绘制三角形

安装图形库 参考 #include "graphics.h" // 就是需要引用这个图形库 #include <conio.h> #include <stdio.h> #include <math.h>// 判断是否可以构成三角形 int isTriangle(int a, int b, int c) {return (a b > c) && (a c >…

A20红色革命文物征集管理系统

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

Logrus入门

Logrus入门 1. 下载 go get github.com/sirupsen/logrus2. logrus常用方法 logrus.Debugln("Debugln") logrus.Infoln("Infoln") logrus.Warnln("Warnln") logrus.Errorln("Errorln") logrus.Println("Println")// 输出如…

pyspark入门基础详细讲解

1.前言介绍 学习目标&#xff1a;了解什么是Speak、PySpark&#xff0c;了解为什么学习PySpark&#xff0c;了解课程是如何和大数据开发方向进行衔接 使用pyspark库所写出来的代码&#xff0c;既可以在电脑上简单运行&#xff0c;进行数据分析处理&#xff0c;又可以把代码无缝…

权限管理练习2

1.在/home中创建一个名为 file1.txt 的文件&#xff0c;并设置权限为&#xff1a;所有者和组成员可以读写&#xff0c;但其他人只能读。 所有者和组成员可以读写 u rw- g rw- o r-- 2.在 /home 目录下创建一个名为 shared 的子目录&#xff0c;使得所有用户都可以进入&#…

面试经典 150 题:121,125

121. 买卖股票的最佳时机 【参考代码】 动态规划解决 class Solution { public:int maxProfit(vector<int>& prices) {int size prices.size();int min_price 99999, max_profit 0;for(int i0; i<size; i){if(prices[i] < min_price){min_price prices[i…

数据集划分

1、 sklearn玩具数据集介绍 数据量小&#xff0c;数据在sklearn库的本地&#xff0c;只要安装了sklearn&#xff0c;不用上网就可以获取 2 sklearn现实世界数据集介绍 数据量大&#xff0c;数据只能通过网络获取&#xff08;科学上网&#xff09; 3 sklearn加载玩具数据集 示…

图形几何之美系列:仿射变换矩阵之先转后偏

“在几何计算、图形渲染、动画、游戏开发等领域&#xff0c;常需要进行元素的平移、旋转、缩放等操作&#xff0c;一种广泛应用且简便的方法是使用仿射变换进行处理。相关的概念还有欧拉角、四元数等&#xff0c;四元数在图形学中主要用于解决旋转问题&#xff0c;特别是在三维…

刷题强训(day05) -- 游游的you、腐烂的苹果、孩子们的游戏(圆圈中最后剩下的数)

目录 1、游游的you 1.1 题目 1.2 思路 1.3 代码实现 2、腐烂的苹果 2.1 题目 2.2 思路 2.3 代码实现 3、孩子们的游戏(圆圈中最后剩下的数) 3.1 题目 3.2 思路 3.3 代码实现 3.3.1 环形链表 ​编辑3.3.2 动态规划 ​编辑 1、游游的you 1.1 题目 1.2 思路 根据题…

PyQt5超详细教程终篇

PyQt5超详细教程 前言 接&#xff1a; [【Python篇】PyQt5 超详细教程——由入门到精通&#xff08;序篇&#xff09;](【Python篇】PyQt5 超详细教程——由入门到精通&#xff08;序篇&#xff09;-CSDN博客) 建议把代码复制到pycahrm等IDE上面看实际效果&#xff0c;方便理…

并查集算法实现

模板 模板分为三大部分 初始化查询i的祖先合并i j(使他们祖先成为一个人) // 1 初始化 void init(int n) {for (int i 1; i < n; i)fa[i] i;//将该数的父节点定义为该数 }// 2 查询i的祖先 int find(int i) {if (i fa[i])return i;else{![查](../pic/并查集.png)fa[i]…

(实战)WebApi第13讲:怎么把不同表里的东西,包括同一个表里面不同的列设置成不同的实体,所有的给整合到一起?【前端+后端】、前端中点击标签后在界面中显示

一、实现全局跨域&#xff1a;新建一个Controller&#xff0c;其它的controller都继承它 1、新建BaseController 2、在后端配置&#xff0c;此处省略【详情见第12讲四、3、】 3、其它的控制器继承BaseController&#xff0c;这个时候就能够完成全局的跨域 【向后台传cookie和…