Day 55 || 图相关理论、深度优先搜索、广度优先搜索

以下内容均来自“代码随想录”

图的种类:整体上一般分为 有向图 和 无向图。

度:无向图中有几条边连接该节点,该节点就有几度。

在有向图中,每个节点有出度和入度。

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

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

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

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

连通分量:在无向图中的极大连通子图称之为该图的一个连通分量。

强连通分量:在有向图中极大强连通子图称之为该图的强连通分量。

图一般使用邻接表邻接矩阵来表示。

深度优先搜索

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

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择:本节点所连接的其他节点) {处理节点;dfs(图,选择的节点); // 递归回溯,撤销处理结果}
}

深度搜索练习题目链接:卡码网题目链接(ACM模式)

广度优先搜索

广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路。

那么用队列,还是用栈都是可以的

用队列的话,就是保证每一圈都是一个方向去转,例如统一顺时针或者逆时针。因为队列是先进先出,加入元素和弹出元素的顺序是没有改变的。

如果用栈的话,就是第一圈顺时针遍历,第二圈逆时针遍历,第三圈有顺时针遍历。因为栈是先进后出,加入元素和弹出元素的顺序改变了。

import java.util.*;public class Main {// 表示四个方向static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // grid 是地图,也就是一个二维数组// visited 标记访问过的节点,不要重复访问// x, y 表示开始搜索节点的下标public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {Queue<int[]> queue = new LinkedList<>(); // 定义队列queue.offer(new int[]{x, y}); // 起始节点加入队列visited[x][y] = true; // 加入队列后立即标记为已访问while (!queue.isEmpty()) { // 遍历队列中的元素int[] cur = queue.poll(); // 从队列取出元素int curx = cur[0];int cury = cur[1]; // 当前节点坐标for (int i = 0; i < 4; i++) { // 遍历当前节点的四个方向int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周围四个方向的坐标// 检查边界条件if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) {continue; // 坐标越界,跳过}// 如果节点未被访问过if (!visited[nextx][nexty]) {queue.offer(new int[]{nextx, nexty}); // 将节点加入队列visited[nextx][nexty] = true; // 加入队列后立即标记为已访问}}}}public static void main(String[] args) {// 示例使用char[][] grid = {{'1', '1', '0', '0'},{'1', '0', '0', '1'},{'0', '0', '1', '1'}};boolean[][] visited = new boolean[grid.length][grid[0].length];// 从(0, 0)开始搜索bfs(grid, visited, 0, 0);}
}

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

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

相关文章

CulturalBench :一个旨在评估大型语言模型在全球不同文化背景下知识掌握情况的基准测试数据集

2024-10-04&#xff0c;为了提升大型语言模型在不同文化背景下的实用性&#xff0c;华盛顿大学、艾伦人工智能研究所等机构联合创建了CulturalBench。这个数据集包含1,227个由人类编写和验证的问题&#xff0c;覆盖了包括被边缘化地区在内的45个全球区域。CulturalBench的推出&…

python登录功能实现

一.用python实现基本的登录功能 #-----------------1.基本登录功能------------------- nameinput("qq账号&#xff1a;") if name"jc":passwdinput("密码&#xff1a;")if passwd"123456":print("登录成功")else:print(&q…

如何使用Python管理环境变量

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 环境变量 📒📝 环境变量简介📝 Python 中的环境变量操作📝 获取环境变量📝 设置环境变量🔖 临时设置🔖 永久设置📝 删除环境变量📝 临时删除📝 永久删除📝 小结⚓️ 相关链接 ⚓️📖 介绍 📖 环境变量…

设置允许多用户远程登录 Windows 云服务器

操作场景 本文档以 Windows Server 2016 操作系统云服务器为例&#xff0c;指导您配置多用户远程登录 Windows 云服务器。 注意&#xff1a; 微软提供的多用户远程登录功能试用期为120天&#xff0c;若未购买多用户登录授权&#xff08;RDS CALs&#xff09;&#xff0c;则试…

喜报!景联文科技成功通过DCMM数据管理能力成熟度二级认证

10月30日&#xff0c;中国电子信息行业联合会公示了新一批DCMM贯标企业&#xff0c;景联文科技成功通过DCMM数据管理能力成熟度二级认证&#xff08;乙方认证&#xff09;。 DCMM是《数据管理能力成熟度评估模型》的简称&#xff0c;是我国在数据管理领域首个正式发布的国家标准…

Android setContentView执行流程(1)-生成DecorView

setContentView的流程主要就是讲在Activity的onCreate方法中调用setContentView方法之后&#xff0c;我们自定义的xml文件加载的过程&#xff0c;学习它可以让我们对整个View树的理解更加透彻&#xff0c;并且通过源码的学习&#xff0c;我们可以从根本上理解一些问题&#xff…

《操作系统 - 清华大学》2 -1:操作系统的启动

文章目录 0. 内容摘要1. 计算机体系机构概述2.启动2.1 启动时计算机内存和磁盘布局2.2. 内存映射 3. 系统调用、异常、中断3.1 定义3.2 背景3.3 中断、异常和系统调用的不同点3.3.1 源头3.3.2 处理时间3.3.3 响应 0. 内容摘要 两部分的内容 第一部分是启动。知道操作系统怎么是…

在服务器里安装2个conda

1、安装新的conda 下载地址&#xff1a;Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 本文选择&#xff1a;Anaconda3-2023.03-1-Linux-x86_64.sh 安装&#xff1a;Ubuntu安装Anaconda详细步骤&#xff08;Ubuntu22.04.1&#xff…

【系统集成项目管理工程师】知识点汇总

十五矩阵图 ITTO&#xff08;Input - Tools & Techniques - Output&#xff09;一览图 整合管理、范围管理 进度管理、成本管理 成本管理&#xff08;续&#xff09;、质量管理、资源管理 沟通管理、风险管理 风险管理&#xff08;续&#xff09;、采购管理、干系人管理

Java | Leetcode Java题解之第552题学生出勤记录II

题目&#xff1a; 题解&#xff1a; class Solution {static final int MOD 1000000007;public int checkRecord(int n) {long[][] mat {{1, 1, 0, 1, 0, 0},{1, 0, 1, 1, 0, 0},{1, 0, 0, 1, 0, 0},{0, 0, 0, 1, 1, 0},{0, 0, 0, 1, 0, 1},{0, 0, 0, 1, 0, 0}};long[][] re…

极品模板内容付费管理系统(PHP内容知识付费系统)

极品模板内容付费管理系统是一款基于PHP和MySQL技术开发的源码产品&#xff0c;旨在为用户提供一个功能全面、易于管理和扩展的内容付费平台。该系统支持多种付费模式&#xff0c;具备强大的内容管理功能&#xff0c;适合各类内容创作者和企业家构建知识付费、会员服务、在线教…

设计者模式之策略模式

前言 在软件构建过程中&#xff0c;某些对象使用的算法可能多种多样&#xff0c;经常改变&#xff0c;如果将这些算法都写在对象中&#xff0c;将会使对象变得异常复杂&#xff1b;而且有时候支持不频繁使用的算法也是一个性能负担。 如何在运行时根据需要透明地更改对象的算…

【AIGC】如何通过ChatGPT轻松制作个性化GPTs应用

创建个性化的GPTs应用是一个涉及技术、设计和用户体验的过程。以下是详细步骤&#xff1a; ###1.确定应用目标和用户群体 在开始之前&#xff0c;你需要明确你的应用的目标和目标用户。这将帮助你在设计、开发和个性化方面做出相应的决策。例如&#xff0c;如果你的应用是为了…

LeetCode 热题 100之 堆

1.数组中第k个最大元素 和Acwing 786 第k个数一模一样 排序 思路分析1&#xff1a;此题要求时间复杂度未为O(n)。虽然库函数sort和快速排序都能过&#xff0c;但是时间复杂度不满足条件。下面优化快速排序&#xff0c;写一个快速选择算法。我们可以引入随机化来加速这个过程&…

redis笔记-数据结构

zset zset一方面它是一个 set&#xff0c;保证了内部value 的唯一性&#xff0c;另一方面它可以给每个 value 赋予一个 score&#xff0c;代表这个 value 的排序权重。 zset的底层是由字典和跳表实现。 字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提…

day20-21之间的项目实战:若依ruoyi开发(可以跳过)

一&#xff0c;项目概述 官网文档地址&#xff1a;http://doc.ruoyi.vip/ rouyi是一个后台管理系统&#xff0c;基于经典技术组合&#xff08;spring boot&#xff0c;apache shiro&#xff0c;mybatis&#xff0c;thymeleaf&#xff09;主要是让开发者注重专注业务&#xff0…

【Android】名不符实的Window类

1.“名不符实”的Window类 Window 是一个窗口的概念&#xff0c;是所有视图的载体&#xff0c;不管是 Activity&#xff0c;Dialog&#xff0c;还是 Toast&#xff0c;他们的视图都是附加在 Window 上面的。例如在桌面显示一个悬浮窗&#xff0c;就需要用到 Window 来实现。Wi…

SDL事件相关

文章目录 事件相关的函数和数据结构用户自定义事件代码相关&#xff1a; 事件相关的函数和数据结构 SDL_WaitEvent :等待一个事件SDL_PushEvent 发送一个事件SDL_PumpEvents(): 将硬件设备产生的时间放入事件队列 &#xff0c;用于读取事件&#xff0c;在调用该函数之前&#…

机器人课程——使用TIA Portal V15博图软件进行西门子组态——带显示屏

一.打开TIA Portal V15博图软件创建项目 1.选择创建新项目 创建完成后选择PLC 二.创建完成后选择设备PLC (此处以S7-1200 1214FC DC/DC/DC 为例) 三.添加扩展板&#xff08;如有——这里以223-1BL32-0XB0为例&#xff09; 四.更改扩展版地址 五.添加触摸屏&#xff08;这里以…

【数据集】【YOLO】【目标检测】道路结冰数据集 1527 张,YOLO目标检测实战训练教程!

数据集介绍 【数据集】道路结冰数据集 1527 张&#xff0c;目标检测&#xff0c;包含YOLO/VOC格式标注。数据集中包含2种分类&#xff1a;“clear_road, ice_road”。数据集来自国内外图片网站和视频截图&#xff0c;部分数据经过数据增强处理。检测范围监控视角检测、无人机视…