图的深度、广度优先探索(数据结构)
深度:
#include <stdio.h>
#include <stdlib.h>
#define MAX 20typedef struct ANode
{int adjver,len;struct ANode*next;
} ArcNode;typedef struct VNode
{int data;ArcNode*firstarc;
} VertexNode;typedef struct
{VertexNode vers[MAX+1];int vernum,arcnum;
} AdjList;void Create(AdjList*AL);
void Deepth(AdjList AL,int v0,int v1);int sign;
int visited[MAX];int main()
{AdjList A;Create(&A);for(int i=1; i<=A.vernum; i++)visited[i]=0;int v0,v1;scanf("%d %d",&v0,&v1);Deepth(A,v0,v1);if(sign)printf("yes");else printf("no");return 0;
}void Create(AdjList*AL)
{scanf("%d %d",&(AL->vernum),&(AL->arcnum));for(int i=1; i<=AL->vernum; i++)scanf("%d",&(AL->vers[i].data));for(int i=1; i<=AL->vernum; i++){int v1,v2;scanf("%d %d",&v1,&v2);ArcNode*ins=(ArcNode*)malloc(sizeof(ArcNode));ins->adjver=v2;ins->next=AL->vers[v1].firstarc;AL->vers[v1].firstarc=ins;}
}void Deepth(AdjList AL,int v0,int v1)
{visited[v0]=1;if(v0==v1){sign=1;return;}ArcNode*p=AL.vers[v0].firstarc;for(; p!=NULL; p=p->next){if(visited[p->adjver]==0)Deepth(AL,p->adjver,v1);}
}
广度:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100typedef struct
{int data[MAX];int front,rear;//队头,队尾
}Queue;typedef struct ArcNode
{int adjver;//弧指向的顶点struct ArcNode* nextarc;//下一条弧的指针
}ArcNode;typedef struct VertexNode
{int data;//顶点数据ArcNode*firstarc;//该顶点的一条弧的指针
}VertexNode;typedef struct
{VertexNode vertexs[MAX];//顶点数组int vernum,arcnum;//顶点总数,弧总数
}AdjList,*AList;void CreateAdjList(AList *g);//创建邻接表
void BreadthSearch(AdjList g,int vi,int vj);//广度优先搜索int visited[MAX]={0};//全局变量,标记是否查询过
Queue q;//队列,按顺序存储应该访问的顶点int main()
{AList g;int vi,vj;//要查询的两个顶点q.rear=q.front=0;//队初始化CreateAdjList(&g);//创建邻接表scanf("%d %d",&vi,&vj);BreadthSearch(*g,vi,vj);//广度优先搜索if(visited[vj]==1)printf("yes");else printf("no");return 0;
}/*创建邻接表*/
void CreateAdjList(AList *g)
{int vn,an,v1,v2;//分别是顶点总数,弧总数, 弧的前后两个顶点(*g)=(AList)malloc(sizeof(AdjList));scanf("%d %d",&vn,&an);(*g)->arcnum=an;(*g)->vernum=vn;for(int i=0;i<vn;i++){scanf("%d",&((*g)->vertexs[i].data));}for(int i=0;i<an;i++){scanf("%d %d",&v1,&v2);//弧的前后两个顶点ArcNode *p=(ArcNode*)malloc(sizeof(ArcNode));//插入的弧结点p->adjver=v2;p->nextarc=(*g)->vertexs[v1].firstarc;(*g)->vertexs[v1].firstarc=p;//完成弧节点的插入}
}/*广度优先搜索*vi:起始点*vj:终止点*/
void BreadthSearch(AdjList g,int vi,int vj)
{if(q.front>q.rear)//如果队已经没有元素,则结束return;visited[vi]=0;if(vi==vj)//找到 vj ,结束return;ArcNode*search=(ArcNode*)malloc(sizeof(ArcNode));for(search=g.vertexs[vi].firstarc;search!=NULL;search=search->nextarc)//把 vi 顶点的所有邻接点遍历{int v=search->adjver;if(visited[v]==0){visited[v]=1;q.data[q.rear++]=v;//把先访问的邻接点放在队中if(v==vj)//找到 vj ,结束return;}}BreadthSearch(g,q.data[q.front++],vj);//递归遍历
}
相关文章:
图的深度、广度优先探索(数据结构)
深度: #include <stdio.h> #include <stdlib.h> #define MAX 20typedef struct ANode {int adjver,len;struct ANode*next; } ArcNode;typedef struct VNode {int data;ArcNode*firstarc; } VertexNode;typedef struct {VertexNode vers[MAX1];int ver…...
c语言小知识点
文章目录 int main()与int main(void)符号常量常变量无符号赋值将占字节多的赋值给字节少的类型赋初值 表达式预处理格式符e格式符 循环for 输入长度相关输出文件管理 int main()与int main(void) int main(void) 指的是此函数的参数为空,不能传入参数,…...
C++ - 模板分离编译
模板分离编译 我们先来看一个问题,我们用 stack 容器的声明定义分离的例子来引出这个问题: // stack.h // stack.h #pragma once #include<deque>namespace My_stack {template<class T, class Container std::deque<T>>class stack…...
如何把非1024的采样数放入aac编码器
一. aac对数据规格要求 二、代码实现 1.初始化 2.填入数据 3.取数据 三.图解 一. aac对放入的采样数要求 我们知道aac每次接受的字节数是固定的,在之前的文章里有介绍libfdk_aac音频采样数和编码字节数注意 它支持的采样数和编码字节数分别是: fdk_aac …...
linux安装nodejs和vue
下载nodejs 打开 下载地址页面中下载**Linux Binaries (x64)**的二进制包设置安装目录 sudo mkdir -p /usr/local/lib/nodejs # 解压 如下载的 node-v18.17.0-linux-x64.tar.xz sudo tar -xJvf node-v18.17.0-linux-x64.tar.xz -C /usr/local/lib/nodejs 加入到PATH #######…...
spring整合mybatis
所需配置: <dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.12</version><scope>test</scope></dependency><dependency><groupId>m…...
Spring指定bean在哪个应用加载
1.背景 某项目,spring架构,有2个不同的WebAppApplication入口,大部分service类共用,小部分类有区别,只需要在一个应用中加载,不需要在另一个应用中加载. 2.实现代码 自定义限制注解 package mis.shared.annotation;import java.lang.annotation.ElementType; import java.lan…...
二维网格划分 LRU缓存设计
背景 有大量的二维矩形需要存储查看点在哪些矩形中给定一个矩形 查看与哪些矩阵相交项目背景与图形图像基本无关,只涉及大文件分块读取,所以不用实现游戏行业中的物理引擎 设计思路 使用空间划分算法:二维栅格将整个空间划分为多个小区域。…...
C++中使用 sizeof 确定变量的长度
C中使用 sizeof 确定变量的长度 变量长度指的是程序员声明变量时,编译器将预留多少内存,用于存储赋给该变量的数据。变量的长度随类型而异, C 提供了一个方便的运算符——sizeof,可用于确定变量的长度(单位为字节&…...
我们的衣物收纳商品政策
本政策涵盖的衣物收纳商品 衣物收纳商品是指带有抽屉或铰链门的家具商品,用于存放衣物。此政策适用于独立式衣物收纳商品,包括但不限于高度为 27 英寸(69 厘米或 686 毫米)或更高(从地面到商品顶部测量)的…...
代码随想录算法训练营第25天| 第七章 回溯算法part02: leetcode 216、leetcode 17
Part I : 回溯算法基础 对回溯算法不清楚的可以参看前一篇:代码随想录算法训练营第24天| 第七章 回溯算法part01 理论基础、leetcode 77 Part II: 相关题目 Leetcode 216.组合总和III 解决问题:在数字1~9之间,找出k个数且它们的和为n从而…...
WebAPI文档与自动化测试
目录 1、控制器,项目属性里需要勾选输出Xml文档选项: 2、下载文档的网页数据 3、运行访问网址 4、接口测试: 5、批量测试: 6、微服务文档 总结: 本篇介绍框架的WebAPI文档与自动化测试 1、控制器,项…...
netty架构
https://zhuanlan.zhihu.com/p/181239748 https://cloud.tencent.com/developer/article/1754078...
拉普拉斯平滑算法
原理 最简单的拉普拉斯平滑算法的原理是将每个顶点都移动到相邻顶点的平均位置上。公式 示例(UE5代码片段) 参考 https://blog.csdn.net/mrbaolong/article/details/105859109...
Java课题笔记~ IoC 控制反转
二、IoC 控制反转 控制反转(IoC,Inversion of Control),是一个概念,是一种思想。指将传统上由程序代码直接操控的对象调用权交给容器,通过容器来实现对象的 装配和管理。控制反转就是对对象控制权的转移&a…...
【Spring】Spring中的设计模式
文章目录 责任链模式工厂模式适配器模式代理模式模版方法观察者模式构造器模式 责任链模式 Spring中的Aop的通知调用会使用责任链模式责任链模式介绍 角色:抽象处理者(Handler)具体处理者(ConcreteHandler1)客户类角…...
【ChatGLM_02】LangChain知识库+Lora微调chatglm2-6b模型+提示词Prompt的使用原则
经验沉淀 1 知识库1.1 Langchain知识库的主要功能(1) 配置知识库(2) 文档数据测试(3) 知识库测试模式(4) 模型配置 2 微调2.1 微调模型的概念2.2 微调模型的方法和步骤(1) 基于ptuning v2 的微调(2) 基于lora的微调 3 提示词3.1 Prompts的定义及原则(1) Prompts是什么…...
构建未来移动应用:探索安卓、iOS和HarmonyOS的技术之旅
安卓、iOS和HarmonyOS的比较分析 在移动应用开发领域,安卓、iOS和HarmonyOS是三个常见的操作系统。本文将对它们进行比较分析,并展示一些相关的代码示例。 安卓(Android) 安卓是由Google开发的移动操作系统,基于Lin…...
【新版系统架构补充】-嵌入式软件
嵌入式软件 嵌入式软件是指应用在嵌入式计算机系统当中的各种软件,除了具有通用软件的一般特性,还具有一些与嵌入式系统相关的特点,包括:规模较小、开发难度大、实时性和可靠性要求高、要求固化存储。 嵌入式软件分类࿱…...
【云原生】K8S超详细概述
目录 一、Kubernets概述1.1 K8S什么1.2为什么要用K8S 二、Kubernetes 集群架构与组件2.1Master组件Kube-apiserverKube-controller-managerKube-scheduler 2.2 配置存储中心etcd 2.3 Node 组件KubeletKube-Proxydocker 或 rocket 三、 Kubernetes 核心概念3.1Pod3.2Pod 控制器K…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
