图的遍历之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࿰…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...
2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案
一、延迟敏感行业面临的DDoS攻击新挑战 2025年,金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征: AI驱动的自适应攻击:攻击流量模拟真实用户行为,差异率低至0.5%,传统规则引…...
Linux-进程间的通信
1、IPC: Inter Process Communication(进程间通信): 由于每个进程在操作系统中有独立的地址空间,它们不能像线程那样直接访问彼此的内存,所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...
32位寻址与64位寻址
32位寻址与64位寻址 32位寻址是什么? 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元(地址),其核心含义与能力如下: 1. 核心定义 地址位宽:CPU或内存控制器用32位…...
13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析
LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...
