图的遍历之DFS邻接矩阵法
本题要求实现一个函数,对给定的用邻接矩阵存储的无向无权图,以及一个顶点的编号v,打印以v为起点的一个深度优先搜索序列。
当搜索路径不唯一时,总是选取编号较小的邻接点。
本题保证输入的数据(顶点数量、起点的编号等)均合法。
函数接口定义:
void DFS(struct Graph *g, int v)
其中 g 是图结构体指针,v 是起点编号。图结构体定义如下:
#define MaxVertexNum 20 // 最大顶点数
struct Graph{int v; // 顶点数量int adj[MaxVertexNum][MaxVertexNum]; //邻接矩阵
}
裁判测试程序样例:
#include <stdio.h>
#include <stdlib.h>
/** 实际的测试程序中,** MaxVertexNum可能不是20,** 但一定是合法的、不会引发内存错误 **/
#define MaxVertexNum 20
struct Graph{int v; // 顶点数量int adj[MaxVertexNum][MaxVertexNum]; //邻接矩阵
};
int visited[MaxVertexNum]; //顶点的访问标记
void DFS(struct Graph *g, int v); //本题要求实现的函数原型
struct Graph* CreateGraph(){ // 创建图int v;scanf("%d",&v);struct Graph* g;g = malloc(sizeof(struct Graph));if(!g) return NULL;g->v = v;for(int i=0; i<v; i++){visited[i] = 0; //访问标记清零for(int j=0; j<v; j++)scanf("%d",&(g->adj[i][j]));}return g;
}
int main(){struct Graph* g;g = CreateGraph();int v;scanf("%d", &v);DFS(g, v);return 0;
}
/** 你提交的代码将被嵌在这里 **/
输入样例:

对于图片中的图以及样例测试程序的输入方式(8个顶点的邻接矩阵,从1号顶点出发):
8
0 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1
输出样例:
注意,总是选取编号小的邻接点
1
0
2
4
7
实现代码(邻接矩阵)
void DFS(struct Graph *g, int v)
{int w;printf("%d\n",v);visited[v]=1;for(int i=0;i<g->v;i++){if((g->adj[v][i]!=0)&&(!visited[i])){DFS(g,i);}}
}
相关文章:
图的遍历之DFS邻接矩阵法
本题要求实现一个函数,对给定的用邻接矩阵存储的无向无权图,以及一个顶点的编号v,打印以v为起点的一个深度优先搜索序列。 当搜索路径不唯一时,总是选取编号较小的邻接点。 本题保证输入的数据(顶点数量、起点的编号等…...
Java --- JVM编译运行过程
目录 一.Java编译与执行流程: 二.编译过程: 1.编译器(javac): 2.字节码文件(.class): 三.执行过程: 1.启动JVM(Java虚拟机): 2…...
HTML5 拖拽 API 深度解析
一、HTML5 拖拽 API 深度解析 1.1 背景与发展 HTML5 的拖拽 API 是为了解决传统拖拽操作复杂而设计的。传统方法依赖鼠标事件和复杂的逻辑计算,而 HTML5 提供了标准化的拖拽事件和数据传递机制,使得开发者能够快速实现从一个元素拖拽到另一个元素的交互…...
GO--基于令牌桶和漏桶的限流策略
至于为什么要限流,字面意思已经很清楚了,就是为了减轻服务器的压力 下面我们将介绍两个限流策略----漏桶和令牌桶。 漏桶 原理介绍 漏桶,顾名思义就是一个漏斗,漏斗嘴的大小是固定的,所以不管漏斗现容量多大&#…...
MongoDB性能监控工具
mongostat mongostat是MongoDB自带的监控工具,其可以提供数据库节点或者整个集群当前的状态视图。该功能的设计非常类似于Linux系统中的vmstat命令,可以呈现出实时的状态变化。不同的是,mongostat所监视的对象是数据库进程。mongostat常用于…...
Axure设计之模拟地图人员移动轨迹
在产品原型设计时,为了更好的表达和呈现预期的效果,让客户或开发看一眼就能理解要实现的功能,往往需要在产品设计时尽量去接近现实,这就需要我们在使用Axure制作原型时应具有高度细节和逼真度的原型设计。原型设计不仅包含了产品的…...
Android环境搭建
Android环境搭建 第一步:安装 Homebrew 执行以下命令来安装 Homebrew: /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"检测是否安装成功: brew --version第二步:安装 No…...
前端工程化面试题(一)
如何使用 Docker 部署前端项目? 使用 Docker 部署前端项目通常涉及以下几个步骤: 创建项目:首先,需要在本地创建并配置好前端项目。 准备 Docker 文件: .dockerignore:这个文件用于排除不需要上传到 Dock…...
模型案例:| 手机识别模型!
导读 2023年以ChatGPT为代表的大语言模型横空出世,它的出现标志着自然语言处理领域取得了重大突破。它在文本生成、对话系统和语言理解等方面展现出了强大的能力,为人工智能技术的发展开辟了新的可能性。同时,人工智能技术正在进入各种应用领…...
期权懂|个股期权交割操作流程是什么样的?
期权小懂每日分享期权知识,帮助期权新手及时有效地掌握即市趋势与新资讯! 个股期权交割操作流程是什么样的? 一、行权申报: 期权买方在行权日通过其经纪商提交行权指令,表明其决定行使期权权利。 二、行权匹配…...
【openGauss】openGauss execute执行update语句,获取更新的行数
【openGauss】openGauss execute执行update语句,获取更新的行数 在openGauss中,可以使用execute语句执行update语句,并通过GET DIAGNOSTICS语句获取更新的行数。下面是一个示例: DO $$ DECLAREupdated_rows INTEGER; BEGINEXECUT…...
P8780 [蓝桥杯 2022 省 B] 刷题统计
题目描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 𝑎道题目,周六和周日每天做 𝑏 道题目。请你帮小明计算,按照计划他将在第几天实现做题数大于等于 𝑛 题? 输入格式 输入一行包含三…...
切比雪夫不等式:方差约束下的概率估计
切比雪夫不等式:方差约束下的概率估计 背景 在概率分析中,切比雪夫不等式是一个常用的工具,它通过引入随机变量的 方差信息,给出了偏离均值的概率界限。这一不等式是对 马尔科夫不等式 的自然扩展,结合了更丰富的分布…...
使用CancellationTokenSource来控制长时间sql查询中断
前端 <!-- 透明的覆盖层,显示在页面上方,包含进度条 --><Grid Visibility"{Binding IsLoading}" Background"Transparent" HorizontalAlignment"Stretch" VerticalAlignment"Stretch" ZIndex"1&…...
小红薯最新x-s 算法补环境教程12-06更新(下)
在上一篇文章中已经讲了如何去定位x-s生成的位置,本篇文章就直接开始撸代码吧 如果没看过的话可以看:小红薯最新x-s算法分析12-06(x-s 56)(上)-CSDN博客 1、获取加密块代码 首先来到参数生成的位置&…...
wazuh-modules-sca
wazuh中安全配置评估模块主线程执行wm_sca_main最后在wm_sca_start中循环执行,不会返回 // Module main function. It wont return #ifdef WIN32 DWORD WINAPI wm_sca_main(void *arg) {wm_sca_t *data (wm_sca_t *)arg; #else void * wm_sca_main(wm_sca_t * dat…...
Uniapp的App环境下使用Map获取缩放比例
概述 目前我试过的就是你用vue后缀是拿不到比例的你可以用nvue当然uniapp的uvue应该是更加可以的我使用的是高德所以你得在高德的后台声请原生的Android的key才可以如果是vue3的开发模式的话不用使用this来获取当前对象使用scale对象来接受和改变缩放比例会比较友好然后直接走…...
微信小程序配置less并使用
1.在VScode中下载Less插件 2.在微信小程序中依次点击如下按钮 选择 从已解压的扩展文件夹安装… 3.选中刚在vscode中下载安装的插件文件 如果没有修改过插件的安装目录,一般是在c盘下C:\用户\用户名.vscode\extensions\mrcrowl.easy-less-2.0.2 我的路径是…...
“全面支持公路数字化转型升级四大任务”视频孪生解决方案
数字经济的加速布局,对交通领域数字化转型、智能化升级提出明确要求。2024年上半年,为深入贯彻落实中共中央、国务院关于加快建设交通强国、数字中国等决策部署,推进公路水路交通基础设施数字转型、智能升级、融合创新,加快发展新…...
顶顶通电话机器人开发接口对接大语言模型之实时流TTS对接介绍
大语言模型一般都是流式返回文字,如果等全部文字返回了一次性去TTS,那么延迟会非常严重,常用的方法就是通过标点符号断句,返回了一句话就提交给TTS。随着流TTS的出现,就可以直接把大模型返回的文字灌给流TTS࿰…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
