当前位置: 首页 > 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…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...