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

数据结构-邻接表广度优先搜索(C语言版)

对于一个有向图无向图,我们下面介绍第二种遍历方式。

广度优先搜索,即优先对同一层的顶点进行遍历。

如下图所示:

该例子,我们有六个顶点, 十条边。

对于广度优先搜索,我们先搜索a,再搜索abcd,最后搜索ef。

而对于广度优先搜索,我们需要一个队列来辅助我们进行广度优先搜索(先进先出)。

同时我们还需要一个visit数组来判断某个顶点是否已经被搜索过了。

#include<stdio.h>#define MAX_NUM 100
typedef struct ArcNode{				//边 int adjvex;struct ArcNode *next;int weight;
}ArcNode;		typedef struct{						//头结点 char vertex;ArcNode *firstarc;
}VNode;typedef VNode Adjlist[MAX_NUM];			//邻接表 typedef struct{			//建立邻接表 Adjlist adjlist;int vexnum,arcnum;
}ALGraph;void DFSTraverse(ALGraph *G)		//深度优先搜索 
{int v;int visit[G->vexnum];for(v=0;v<G->vexnum;v++){visit[v] = 0;}for(v=0;v<G->vexnum;v++){if(visit[v]==0)DFS(G,v,visit);}
}void DFS(ALGraph *G,int v,int *visit)		//深度优先搜索后继结点判断 
{int w;ArcNode *p;printf("访问顶点:%c\n",G->adjlist[v].vertex);visit[v] = 1;p = G->adjlist[v].firstarc;while(p){w = p->adjvex;if(visit[w]==0)DFS(G,w,visit);p = p->next;}
}void BFSTraverse(ALGraph *G)		//广度优先搜索后继节点判断 
{int v,w,u;int Q[G->vexnum+1],r,f;int visit[G->vexnum];for(v=0;v<G->vexnum;v++)visit[v] = 0;f = 0,r = 0;for(v=0;v<G->vexnum;v++){if(visit[v]==0){visit[v] = 1;printf("第%d个结点是->%c\n",v,G->adjlist[v].vertex);Q[r] = v;r = (r+1)%(G->vexnum+1);while(f!=r){u = Q[f];f = (f+1)%(G->vexnum+1);ArcNode *p = G->adjlist[u].firstarc;while(p){if(visit[p->adjvex]==0){visit[p->adjvex] = 1;printf("第%d个结点是->%c\n",p->adjvex,G->adjlist[p->adjvex].vertex);Q[r] = p->adjvex;r = (r+1)%(G->vexnum+1);}p = p->next;}}}}
}int main()
{return 0;
}

运行结果如下:

相关文章:

数据结构-邻接表广度优先搜索(C语言版)

对于一个有向图无向图&#xff0c;我们下面介绍第二种遍历方式。 广度优先搜索&#xff0c;即优先对同一层的顶点进行遍历。 如下图所示&#xff1a; 该例子&#xff0c;我们有六个顶点&#xff0c; 十条边。 对于广度优先搜索&#xff0c;我们先搜索a&#xff0c;再搜索abc…...

Py之auto-gptq:auto-gptq的简介、安装、使用方法之详细攻略

Py之auto-gptq&#xff1a;auto-gptq的简介、安装、使用方法之详细攻略 目录 auto-gptq的简介 1、版本更新历史 2、性能对比 推理速度 困惑度&#xff08;PPL&#xff09; 3、支持的模型 3、支持的评估任务 auto-gptq的安装 auto-gptq的使用方法 1、基础用法 (1)、量…...

【Linux】Linux+Nginx部署项目(负载均衡动静分离)

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Linux的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.Nginx负载均衡 1.什么是负载均衡 2.实…...

C++笔记之vector的成员函数swap()和data()

C笔记之vector的成员函数swap()和data() 标准C中的std::vector类确实有swap()和data()这两个成员函数。下面是它们的简要描述&#xff1a; swap(): std::vector的swap()成员函数用于交换两个向量的内容&#xff0c;实现了高效的交换操作&#xff0c;不需要复制向量的元素。这…...

Linux centos环境 安装谷歌浏览器

教程 地址...

go-gin-vue3-elementPlus带参手动上传文件

文章目录 一. 总体代码流程1.1 全局Axios部分样例1.2 上传业务 二. 后端部分三. 测试样例 go的mvc层使用gin框架. 总的来说gin的formFile封装的不如springboot的好.获取值有很多的坑. 当然使用axios的formData也有不少坑.现给出较好的解决办法 以下部分仅贴出关键代码 一. 总…...

艺术的维度:洞察AI诈骗,优雅防范之艺术

当前&#xff0c;AI技术的广泛应用为社会公众提供了个性化智能化的信息服务&#xff0c;也给网络诈骗带来可乘之机&#xff0c;如不法分子通过面部替换语音合成等方式制作虚假图像、音频、视频仿冒他人身份实施诈骗、侵害消费者合法权益。 以下是一些常见的AI诈骗例子&#xf…...

JavaScript的作用域和作用域链

作用域 ● 作用域&#xff08;Scoping&#xff09;&#xff1a;我们程序中变量的组织和访问方式。"变量存在在哪里&#xff1f;“或者"我们可以在哪里访问某个变量&#xff0c;以及在哪里不能访问&#xff1f;” ● 词法作用域&#xff08;Lexical scoping&#xff…...

电脑文件批量重命名攻略:高效操作技巧助您轻松完成任务

在日常使用电脑时&#xff0c;我们经常需要对文件进行重命名。当文件数量众多时&#xff0c;手动重命名既耗时又容易出错。此时&#xff0c;借助一些实用技巧&#xff0c;我们可以轻松地完成电脑文件的批量重命名。本文将提供一份全面的电脑文件批量重命名攻略&#xff0c;帮助…...

四、三种基本程序结构

1、程序结构 (1)在C语言程序中&#xff0c;一共有三种程序结构&#xff1a;顺序结构、选择结构(分支结构)、循环结构。 顺序结构&#xff1a;按照事务本身特性&#xff0c;必须一个接着一个来完成。选择结构&#xff1a;到某个节点后&#xff0c;会根据一次判断结果来决定之后…...

深入理解元素的高度、行高、行盒和vertical-align

1.块级元素的高度 当没有设置高度时&#xff0c;高度由内容撑开&#xff0c;实际上是由行高撑开&#xff0c;当有多行时&#xff0c;高度为每行的行高高度之和。 行高为什么存在&#xff1f; 因为每行都由一个行盒包裹&#xff0c;行高实际上是行盒的高度。 2.什么是行盒&am…...

什么叫储能能量管理单元EMU?储能能量管理单元EMU功能?储能EMU是什么?储能能量管理系统如何实现一次调频AGC-AVC功能?

一&#xff1a;储能EMU是什么意思?什么叫储能能量管理单元EMU&#xff1f; EMU是能量管理单元的英文缩写 (Energy Management Unit, EMU) EmuPower3300能量管理单元EMU是由广州智昊电气研发配套EsccPower3300储能协调管理器组成对光伏电站的管理&#xff0c;控制&#xff0c;…...

机器学习之决策树

决策树&#xff1a; 是一种有监督学习方法&#xff0c;从一系列有特征和标签的数据中总结出决策规则&#xff0c;并采用树状图的结构来呈现规则&#xff0c;用来解决分类和回归问题。 节点&#xff1a;根节点&#xff1a;没有进边&#xff0c;有出边。包含最初的&#xff0c;针…...

聊聊logback的UNDEFINED_PROPERTY

序 本文主要研究一下logback的UNDEFINED_PROPERTY substVars ch/qos/logback/core/util/OptionHelper.java public static String substVars(String input, PropertyContainer pc0, PropertyContainer pc1) {try {return NodeToStringTransformer.substituteVariable(input,…...

记一次pdjs时安装glob出现,npm ERR! code ETARGET和npm ERR! code ELIFECYCLE

如往常一样&#xff0c;我使用pdjs来编译proto文件&#xff0c;但出现了以下报错&#xff1a; 大致就是pdjs的util在尝试执行npm install glob^7.2.1 escodegen^1.13.0时出错了 尝试手动执行安装&#xff0c;escodegen被正确安装&#xff0c;但glob^7.2.1出错 npm ERR! code E…...

Zabbix如何监控腾讯云NAT网关

1、NAT网关介绍 NAT 网关&#xff08;NAT Gateway&#xff09;是一种支持 IP 地址转换服务&#xff0c;提供网络地址转换能力&#xff0c;主要包括SNAT&#xff08;Source Network Address Translation&#xff0c;源网络地址转换&#xff09;和DNAT&#xff08;Destination N…...

SpringBoot案例(数据层、业务层、表现层)

1.创建项目 2.选择坐标 3.添加坐标 说明&#xff1a;为了便于开发&#xff0c;引入了lombak坐标。 <!--添加mybatis-plus坐标--><dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><ver…...

交叉编译程序:以 freetype 为例

1 程序运行的一些基础知识 1.1 编译程序时去哪找头文件&#xff1f; 系统目录&#xff1a;就是交叉编译工具链里的某个 include 目录&#xff1b;也可以自己指定&#xff1a;编译时用 “ -I dir ” 选项指定。 1.2 链接时去哪找库文件&#xff1f; 系统目录&#…...

spring-cloud-starter-dubbo不设置心跳间隔导致生产者重启no Provider问题记录

版本 spring-cloud-starter-dubbo-2.2.4.RELEASE 问题描述 生产者重启后&#xff0c;正常注册到注册中心&#xff0c;但是消费者调用接口是no provider&#xff0c;偶现&#xff0c;频繁出现 解决办法 先说原因和解决办法&#xff0c;有兴趣可以看下问题的排查过程。 原因…...

【数据结构】败者树的建树与比较过程

文章目录 前置知识归并段 建树过程比较过程疑问为什么比较次数减少了&#xff1f;如果某个归并段的元素一直获胜&#xff0c;没有元素了怎么办&#xff1f;处理方法 1处理方法 2 前置知识 归并段 外部排序算法通常用于处理大规模数据&#xff0c;其中数据量远超过计算机内存的…...

机器学习结合基因无关通路映射:从临床数据挖掘新药靶点

1. 项目概述&#xff1a;当机器学习遇见代谢通路&#xff0c;如何从数据中“挖”出新药靶点&#xff1f;在生物医学研究的前沿&#xff0c;我们正面临一个核心矛盾&#xff1a;一方面&#xff0c;我们拥有海量的临床数据&#xff0c;比如血糖、血压、BMI等指标&#xff1b;另一…...

51单片机驱动ST7735S彩屏避坑指南:从5秒刷屏到流畅贪吃蛇的优化实战

51单片机驱动ST7735S彩屏性能优化实战&#xff1a;从卡顿到流畅游戏的蜕变之路当一块128x160分辨率的ST7735S彩屏遇上传统的51单片机&#xff0c;这种组合看似矛盾却又充满挑战。许多开发者初次尝试时会发现&#xff0c;原本在STM32等平台上运行流畅的显示驱动&#xff0c;移植…...

基于Arduino与应变片传感器的高精度厨房电子秤DIY全攻略

1. 项目概述&#xff1a;用Arduino打造一台高精度厨房电子秤作为一个喜欢在厨房里折腾的硬件爱好者&#xff0c;我经常遇到需要精确称量食材的场合。市面上的电子秤要么精度不够&#xff0c;要么价格不菲&#xff0c;要么功能单一。于是&#xff0c;我萌生了自己动手做一台的想…...

OpenClaw 连接阿里云百炼图文教程

OpenClaw 连接阿里云百炼图文教程 前置准备 已安装并可以正常打开 OpenClaw Windows。 OpenClaw 顶部 Gateway 状态保持在线。 已准备好可正常登录的阿里云账号。 可以正常访问阿里云百炼登录地址&#xff1a;https://bailian.console.aliyun.com/cn-beijing#/home 建议提…...

森优时铁锌维发根养黑用三个月真实效果实测:内服营养养黑的客观测评

"森优时铁锌维发根养黑用三个月真实效果实测显示&#xff0c;针对压力、熬夜引发的早白问题&#xff0c;通过内服补充毛囊所需营养的方式&#xff0c;多数使用者能感受到发根韧性提升、新生发色素沉淀改善&#xff0c;整体改善效果因人而异&#xff0c;合规的营养补充是目…...

基于ATmega2560与ISD1700的智能语音时钟:硬件选型、软件架构与避坑指南

1. 项目概述与核心价值去年折腾那个用ATMega328驱动三块显示屏的时钟时&#xff0c;我主要精力都花在了如何在320x240的TFT屏幕上把时间、日期和图标画得又准又好看上。项目在《Elektor》杂志上发表后&#xff0c;一位热心的读者给我提了个新想法&#xff1a;能不能做个会“说话…...

《我看见的世界:李飞飞自传》第1-6章阅读笔记:从移民少女到AI教母的“看见“之旅

前言 当我们谈论人工智能时&#xff0c;我们谈论的是算法、数据、算力&#xff0c;是那些冰冷的代码和复杂的模型。但在《我看见的世界&#xff1a;李飞飞自传》中&#xff0c;李飞飞用她独特的视角告诉我们&#xff1a;AI的本质&#xff0c;是人类对"看见"世界的渴望…...

Burp Suite深度解析:从流量抓包到业务逻辑漏洞挖掘

1. 这不是“学个插件”——Burp Suite 是渗透测试的呼吸系统 很多人第一次听说 Burp Suite&#xff0c;是在某篇“三步拿下登录框”的速成教程里&#xff1a;装好Java、拖进浏览器代理、点几下Repeater就弹出密码明文。结果真去测一个中型SaaS后台&#xff0c;不到十分钟就卡在…...

基于Arduino的智能蓝调节拍器:DIY音乐练习伴侣

1. 项目概述&#xff1a;一个能“演奏”蓝调的低成本节拍器玩乐器的人&#xff0c;对节拍器这东西又爱又恨。它像一位严厉的监工&#xff0c;用单调的“嘀嗒”声强迫你跟上节奏。但你想过没有&#xff0c;这个监工其实可以很有趣&#xff1f;几年前&#xff0c;我在练习蓝调吉他…...

上线前最后一道防线,DeepSeek代码审查如何帮你拦截87%的CVE类缺陷?

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;上线前最后一道防线&#xff0c;DeepSeek代码审查如何帮你拦截87%的CVE类缺陷&#xff1f; 在软件交付生命周期末期&#xff0c;传统人工代码审计与通用SAST工具常因误报率高、上下文理解弱而漏检高危漏…...