当前位置: 首页 > news >正文

图的深度、广度优先探索(数据结构)

深度:

#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);//递归遍历
}

相关文章:

图的深度、广度优先探索(数据结构)

深度&#xff1a; #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) 指的是此函数的参数为空&#xff0c;不能传入参数&#xff0c;…...

C++ - 模板分离编译

模板分离编译 我们先来看一个问题&#xff0c;我们用 stack 容器的声明定义分离的例子来引出这个问题&#xff1a; // 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每次接受的字节数是固定的&#xff0c;在之前的文章里有介绍libfdk_aac音频采样数和编码字节数注意 它支持的采样数和编码字节数分别是&#xff1a; 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

所需配置&#xff1a; <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缓存设计

背景 有大量的二维矩形需要存储查看点在哪些矩形中给定一个矩形 查看与哪些矩阵相交项目背景与图形图像基本无关&#xff0c;只涉及大文件分块读取&#xff0c;所以不用实现游戏行业中的物理引擎 设计思路 使用空间划分算法&#xff1a;二维栅格将整个空间划分为多个小区域。…...

C++中使用 sizeof 确定变量的长度

C中使用 sizeof 确定变量的长度 变量长度指的是程序员声明变量时&#xff0c;编译器将预留多少内存&#xff0c;用于存储赋给该变量的数据。变量的长度随类型而异&#xff0c; C 提供了一个方便的运算符——sizeof&#xff0c;可用于确定变量的长度&#xff08;单位为字节&…...

我们的衣物收纳商品政策

本政策涵盖的衣物收纳商品 衣物收纳商品是指带有抽屉或铰链门的家具商品&#xff0c;用于存放衣物。此政策适用于独立式衣物收纳商品&#xff0c;包括但不限于高度为 27 英寸&#xff08;69 厘米或 686 毫米&#xff09;或更高&#xff08;从地面到商品顶部测量&#xff09;的…...

代码随想录算法训练营第25天| 第七章 回溯算法part02: leetcode 216、leetcode 17

Part I : 回溯算法基础 对回溯算法不清楚的可以参看前一篇&#xff1a;代码随想录算法训练营第24天| 第七章 回溯算法part01 理论基础、leetcode 77 Part II: 相关题目 Leetcode 216.组合总和III 解决问题&#xff1a;在数字1~9之间&#xff0c;找出k个数且它们的和为n从而…...

WebAPI文档与自动化测试

目录 1、控制器&#xff0c;项目属性里需要勾选输出Xml文档选项&#xff1a; 2、下载文档的网页数据 3、运行访问网址 4、接口测试&#xff1a; 5、批量测试&#xff1a; 6、微服务文档 总结&#xff1a; 本篇介绍框架的WebAPI文档与自动化测试 1、控制器&#xff0c;项…...

netty架构

https://zhuanlan.zhihu.com/p/181239748 https://cloud.tencent.com/developer/article/1754078...

拉普拉斯平滑算法

原理 最简单的拉普拉斯平滑算法的原理是将每个顶点都移动到相邻顶点的平均位置上。公式 示例&#xff08;UE5代码片段&#xff09; 参考 https://blog.csdn.net/mrbaolong/article/details/105859109...

Java课题笔记~ IoC 控制反转

二、IoC 控制反转 控制反转&#xff08;IoC&#xff0c;Inversion of Control&#xff09;&#xff0c;是一个概念&#xff0c;是一种思想。指将传统上由程序代码直接操控的对象调用权交给容器&#xff0c;通过容器来实现对象的 装配和管理。控制反转就是对对象控制权的转移&a…...

【Spring】Spring中的设计模式

文章目录 责任链模式工厂模式适配器模式代理模式模版方法观察者模式构造器模式 责任链模式 Spring中的Aop的通知调用会使用责任链模式责任链模式介绍 角色&#xff1a;抽象处理者&#xff08;Handler&#xff09;具体处理者&#xff08;ConcreteHandler1&#xff09;客户类角…...

【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是什么&#xf…...

构建未来移动应用:探索安卓、iOS和HarmonyOS的技术之旅

安卓、iOS和HarmonyOS的比较分析 在移动应用开发领域&#xff0c;安卓、iOS和HarmonyOS是三个常见的操作系统。本文将对它们进行比较分析&#xff0c;并展示一些相关的代码示例。 安卓&#xff08;Android&#xff09; 安卓是由Google开发的移动操作系统&#xff0c;基于Lin…...

【新版系统架构补充】-嵌入式软件

嵌入式软件 嵌入式软件是指应用在嵌入式计算机系统当中的各种软件&#xff0c;除了具有通用软件的一般特性&#xff0c;还具有一些与嵌入式系统相关的特点&#xff0c;包括&#xff1a;规模较小、开发难度大、实时性和可靠性要求高、要求固化存储。 嵌入式软件分类&#xff1…...

【云原生】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…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...