当前位置: 首页 > 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智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

第14节 Node.js 全局对象

JavaScript 中有一个特殊的对象&#xff0c;称为全局对象&#xff08;Global Object&#xff09;&#xff0c;它及其所有属性都可以在程序的任何地方访问&#xff0c;即全局变量。 在浏览器 JavaScript 中&#xff0c;通常 window 是全局对象&#xff0c; 而 Node.js 中的全局…...