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

图的遍历之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;
}
/** 你提交的代码将被嵌在这里 **/

输入样例:

1.jpg

对于图片中的图以及样例测试程序的输入方式(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邻接矩阵法

本题要求实现一个函数&#xff0c;对给定的用邻接矩阵存储的无向无权图&#xff0c;以及一个顶点的编号v&#xff0c;打印以v为起点的一个深度优先搜索序列。 当搜索路径不唯一时&#xff0c;总是选取编号较小的邻接点。 本题保证输入的数据&#xff08;顶点数量、起点的编号等…...

Java --- JVM编译运行过程

目录 一.Java编译与执行流程&#xff1a; 二.编译过程&#xff1a; 1.编译器&#xff08;javac&#xff09;&#xff1a; 2.字节码文件&#xff08;.class&#xff09;&#xff1a; 三.执行过程&#xff1a; 1.启动JVM&#xff08;Java虚拟机&#xff09;&#xff1a; 2…...

HTML5 拖拽 API 深度解析

一、HTML5 拖拽 API 深度解析 1.1 背景与发展 HTML5 的拖拽 API 是为了解决传统拖拽操作复杂而设计的。传统方法依赖鼠标事件和复杂的逻辑计算&#xff0c;而 HTML5 提供了标准化的拖拽事件和数据传递机制&#xff0c;使得开发者能够快速实现从一个元素拖拽到另一个元素的交互…...

GO--基于令牌桶和漏桶的限流策略

至于为什么要限流&#xff0c;字面意思已经很清楚了&#xff0c;就是为了减轻服务器的压力 下面我们将介绍两个限流策略----漏桶和令牌桶。 漏桶 原理介绍 漏桶&#xff0c;顾名思义就是一个漏斗&#xff0c;漏斗嘴的大小是固定的&#xff0c;所以不管漏斗现容量多大&#…...

MongoDB性能监控工具

mongostat mongostat是MongoDB自带的监控工具&#xff0c;其可以提供数据库节点或者整个集群当前的状态视图。该功能的设计非常类似于Linux系统中的vmstat命令&#xff0c;可以呈现出实时的状态变化。不同的是&#xff0c;mongostat所监视的对象是数据库进程。mongostat常用于…...

Axure设计之模拟地图人员移动轨迹

在产品原型设计时&#xff0c;为了更好的表达和呈现预期的效果&#xff0c;让客户或开发看一眼就能理解要实现的功能&#xff0c;往往需要在产品设计时尽量去接近现实&#xff0c;这就需要我们在使用Axure制作原型时应具有高度细节和逼真度的原型设计。原型设计不仅包含了产品的…...

Android环境搭建

Android环境搭建 第一步&#xff1a;安装 Homebrew 执行以下命令来安装 Homebrew&#xff1a; /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"检测是否安装成功&#xff1a; brew --version第二步&#xff1a;安装 No…...

前端工程化面试题(一)

如何使用 Docker 部署前端项目&#xff1f; 使用 Docker 部署前端项目通常涉及以下几个步骤&#xff1a; 创建项目&#xff1a;首先&#xff0c;需要在本地创建并配置好前端项目。 准备 Docker 文件&#xff1a; .dockerignore&#xff1a;这个文件用于排除不需要上传到 Dock…...

模型案例:| 手机识别模型!

导读 2023年以ChatGPT为代表的大语言模型横空出世&#xff0c;它的出现标志着自然语言处理领域取得了重大突破。它在文本生成、对话系统和语言理解等方面展现出了强大的能力&#xff0c;为人工智能技术的发展开辟了新的可能性。同时&#xff0c;人工智能技术正在进入各种应用领…...

期权懂|个股期权交割操作流程是什么样的?

期权小懂每日分享期权知识&#xff0c;帮助期权新手及时有效地掌握即市趋势与新资讯&#xff01; 个股期权交割操作流程是什么样的&#xff1f; 一、行权申报&#xff1a; 期权买方在行权日通过其经纪商提交行权指令&#xff0c;表明其决定行使期权权利。 二、行权匹配&#xf…...

【openGauss】openGauss execute执行update语句,获取更新的行数

【openGauss】openGauss execute执行update语句&#xff0c;获取更新的行数 在openGauss中&#xff0c;可以使用execute语句执行update语句&#xff0c;并通过GET DIAGNOSTICS语句获取更新的行数。下面是一个示例&#xff1a; DO $$ DECLAREupdated_rows INTEGER; BEGINEXECUT…...

P8780 [蓝桥杯 2022 省 B] 刷题统计

题目描述 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 &#x1d44e;道题目&#xff0c;周六和周日每天做 &#x1d44f; 道题目。请你帮小明计算&#xff0c;按照计划他将在第几天实现做题数大于等于 &#x1d45b; 题? 输入格式 输入一行包含三…...

切比雪夫不等式:方差约束下的概率估计

切比雪夫不等式&#xff1a;方差约束下的概率估计 背景 在概率分析中&#xff0c;切比雪夫不等式是一个常用的工具&#xff0c;它通过引入随机变量的 方差信息&#xff0c;给出了偏离均值的概率界限。这一不等式是对 马尔科夫不等式 的自然扩展&#xff0c;结合了更丰富的分布…...

使用CancellationTokenSource来控制长时间sql查询中断

前端 <!-- 透明的覆盖层&#xff0c;显示在页面上方&#xff0c;包含进度条 --><Grid Visibility"{Binding IsLoading}" Background"Transparent" HorizontalAlignment"Stretch" VerticalAlignment"Stretch" ZIndex"1&…...

小红薯最新x-s 算法补环境教程12-06更新(下)

在上一篇文章中已经讲了如何去定位x-s生成的位置&#xff0c;本篇文章就直接开始撸代码吧 如果没看过的话可以看&#xff1a;小红薯最新x-s算法分析12-06&#xff08;x-s 56&#xff09;&#xff08;上&#xff09;-CSDN博客 1、获取加密块代码 首先来到参数生成的位置&…...

wazuh-modules-sca

wazuh中安全配置评估模块主线程执行wm_sca_main最后在wm_sca_start中循环执行&#xff0c;不会返回 // 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中下载安装的插件文件 如果没有修改过插件的安装目录&#xff0c;一般是在c盘下C:\用户\用户名.vscode\extensions\mrcrowl.easy-less-2.0.2 我的路径是&#xf…...

“全面支持公路数字化转型升级四大任务”视频孪生解决方案

数字经济的加速布局&#xff0c;对交通领域数字化转型、智能化升级提出明确要求。2024年上半年&#xff0c;为深入贯彻落实中共中央、国务院关于加快建设交通强国、数字中国等决策部署&#xff0c;推进公路水路交通基础设施数字转型、智能升级、融合创新&#xff0c;加快发展新…...

顶顶通电话机器人开发接口对接大语言模型之实时流TTS对接介绍

大语言模型一般都是流式返回文字&#xff0c;如果等全部文字返回了一次性去TTS&#xff0c;那么延迟会非常严重&#xff0c;常用的方法就是通过标点符号断句&#xff0c;返回了一句话就提交给TTS。随着流TTS的出现&#xff0c;就可以直接把大模型返回的文字灌给流TTS&#xff0…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

02-性能方案设计

需求分析与测试设计 根据具体的性能测试需求&#xff0c;确定测试类型&#xff0c;以及压测的模块(web/mysql/redis/系统整体)前期要与相关人员充分沟通&#xff0c;初步确定压测方案及具体的性能指标QA完成性能测试设计后&#xff0c;需产出测试方案文档发送邮件到项目组&…...