用邻接矩阵实现图的深度优先遍历
问题描述
给定一个无向图,用邻接矩阵作为图的存储结构,输出指定顶点出发的深度优先遍历序列。在深度优先遍历的过程中,如果同时出现多个待访问的顶点,则优先选择编号最小的一个进行访问。
输入描述
第一行输入三个正整数,分别表示无向图的顶点数n(2≤n≤100,顶点从1到n编号)、边数m和指定起点编号s。
接下来的m行对应m条边,每行给出两个正整数,分别是该条边直接连通的两个顶点的编号。
输出描述
输出从 s开始的深度优先遍历序列,用一个空格隔开,最后也含有一个空格。如果从 s出发无法遍历到图中的所有顶点,则在第二行输出Non‑connected。
样例输入
5 4 1 1 2 3 1 5 2 2 3
样例输出
1 2 3 5 Non-connected
#include<stdio.h>
#define MVNUM 10 //最大顶点数
typedef int VerTexType; //顶点数据类型为整型
typedef int ArcType; //边的权值为整型
typedef struct
{VerTexType vexs[MVNUM];//顶点表ArcType arcs[MVNUM][MVNUM]; //邻接矩阵int vexnum, arcnum; //图当前的顶点数和边数int visited[MVNUM];
}AMGraph;
static int LocateVex(AMGraph G, int v) //在图中查找顶点
{for (int i = 0; i < G.vexnum; i++)if (v == G.vexs[i])return i;return -1;
}
static void CreateUDG(AMGraph &G) //创建无向网
{for (int i = 0; i < G.vexnum; i++) //创建顶点表{G.vexs[i] = i + 1;G.visited[i+1] = 0; //未搜索的顶点标记为0}for (int i = 0; i < G.vexnum; i++) //邻接矩阵元素置零for (int j = 0; j < G.vexnum; j++)G.arcs[i][j] = 0;for (int k = 0; k < G.arcnum; k++){int v1 = 0, v2 = 0;scanf("%d%d", &v1, &v2);int i = LocateVex(G, v1);int j = LocateVex(G, v2);G.arcs[i][j] = 1;G.arcs[j][i] = 1;}return;
}
int count = 0;
static void DFS(AMGraph &G, int v)
{count++;printf("%d ", v);G.visited[v] = 1; //访问过的顶点标记为1for (int j = 1; j <= G.vexnum; j++)if (G.arcs[v-1][j-1] && !G.visited[j])DFS(G, j); //递归调用
}
int main()
{int s = 0; //指定起点编号AMGraph G;scanf("%d%d%d", &G.vexnum, &G.arcnum, &s);CreateUDG(G);DFS(G, s);if (count < G.vexnum)printf("\nNon-connected");return 0;
}
相关文章:
用邻接矩阵实现图的深度优先遍历
问题描述 给定一个无向图,用邻接矩阵作为图的存储结构,输出指定顶点出发的深度优先遍历序列。在深度优先遍历的过程中,如果同时出现多个待访问的顶点,则优先选择编号最小的一个进行访问。 输入描述 第一行输入三个正整数&#…...
vue2中实现token的无感刷新
后端配置 设置Token过期时间:在后端(如服务器或网关)配置access_token和refresh_token的过期时间。通常,access_token的过期时间较短,而refresh_token的过期时间较长。提供刷新Token接口:后端需要提供一个…...
无需Photoshop即可在线裁剪和调整图像大小的工具
Bitmind是一个灵活且易于使用的批量图像本地化处理器,经过抓包看,这个工具在浏览器本地运行,不会上传图片到服务器,所以安全性完全有保证。 它可以将图像调整到任何特定尺寸,并在必要时按比例裁剪。 这是一个在线工具…...
云安全之法律和合规
0x00 前言 本文主要内容是从法律,合同,电子举证,以及合规和审计这五个部分来记录一下相关的云安全内容 0x01 法律 受法律约束的影响因素 云服务所在的地区云用户所在的区域数据主体所在的区域 GDPR:通用数据保护法案…...
倒计时功能分享
今天想要分享的是一个面试题,也是一个我们在项目中常用的功能:倒计时。 首先我们在写倒计时的时候必须要考虑到是:准确性、性能。接下来我们一步一步实现这个完美地倒计时功能。 setInterval 先来简单实现一个倒计时的函数: func…...
【论文分享】使用多源数据识别建筑功能:以中国三大城市群为例
建筑功能对城市规划至关重要,而利用多源数据进行建筑功能分类有助于支持城市规划政策。本研究通过分析建筑特征和POI密度,识别了中国三个城市群的建筑功能,并使用XGBoost模型验证了其在大规模映射中的高准确性和有效性。研究强调了建筑环境对…...
华为手机启用ADB无线调试功能
打开开发者模式,勾选USB调试,和“仅充电”模式下允许ADB调试 确认 设置添加adb路径到PATH变量 使用adb查看安卓设置 切换为无线模式: 查看手机IP...
云原生之Kubernetes集群搭建
1、Kubernetets基础概念 传统的服务器架构演进,现在基于docker容器化应用可以完成快速部署,但是对于大型的应用,有可能出现成百上千个容器化应用,一个挂了需要人工管理是相当麻烦,因此急需一个大规模容器编排系统。 Kubernetes Kubernetes 是一个可移植、可扩展的开源平…...
STM32单片机CAN总线汽车线路通断检测
目录 目录 前言 一、本设计主要实现哪些很“开门”功能? 二、电路设计原理图 1.电路图采用Altium Designer进行设计: 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 随着汽车电子技术的不断发展,车辆通信接口在汽车电子控…...
大连理工大学概率上机作业免费下载
大连理工大学概率论与数理统计上机资源 本资源库收录了大连理工大学概率论与数理统计课程的上机作业范例代码,旨在通过实际操作加深学生对概率统计概念的理解,帮助学生更好地理解和掌握知识点。 作业内容概览 第一题:随机变量关系探索 数…...
Tomcat 如何管理 Session
Tomcat 如何管理 Session 我们知道,Tomcat 中每一个 Context 容器对应一个 Web 应用,而 Web 应用之间的 Session 应该是独立的,因此 Session 的管理肯定是 Context 级的,也就是一个 Context 一定关联多个 Session。 Tomcat 中主…...
stm32启动过程解析startup启动文件
1.STM32的启动过程模式 1.1 根据boot引脚决定三种启动模式 复位后,在 SYSCLK 的第四个上升沿锁存 BOOT 引脚的值。BOOT0 为专用引脚,而 BOOT1 则与 GPIO 引脚共用。一旦完成对 BOOT1 的采样,相应 GPIO 引脚即进入空闲状态,可用于…...
SystemVerilog学习——构造函数new
一、概述 在 SystemVerilog 中,new 是一个构造函数,用于创建类的实例(即对象)。它在面向对象编程(OOP)中起着重要作用,负责实例化一个对象并进行初始化。与传统编程语言(如 C 或 Jav…...
力扣题目总结
1.游戏玩法分析IV AC: select IFNULL(round(count(distinct(Result.player_id)) / count(distinct(Activity.player_id)), 2), 0) as fraction from (select Activity.player_id as player_idfrom (select player_id, DATE_ADD(MIN(event_date), INTERVAL 1 DAY) as second_da…...
Java API 进阶指南:从核心API到高级应用的全面提升
文章目录 Java API 进阶学习指南1. 深入理解核心API1.1 集合框架(Collections Framework)1.2 输入输出流(I/O Streams)1.3 并发编程(Concurrency)1.4 反射(Reflection)1.5 泛型&…...
esp32c3开发板通过micropython的ubluetooth库连蓝牙设备
ESP32-C3开发板是一款高性能、低功耗的微控制器,搭载了Espressif自家的RISC-V处理器。通过MicroPython,一种面向微控制器的精简版Python编程语言,开发者可以轻松地为ESP32-C3编写代码。MicroPython的ubluetooth库使得ESP32-C3能够通过蓝牙与各…...
leetcode hot100【LeetCode 35.搜索插入位置】java实现
LeetCode 35.搜索插入位置 题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用 O(log n) 的时间复杂度来实现。 示例 1: 输入: nums [1,3,5,6…...
我们要用平凡来诠释非凡
#孟晚舟香港中文大学演讲# #华为价值观念# #并非站在山顶才能被看见# #传递正确的价值观# #如果信仰有颜色,那一定是中国红# #送给自己的价值理念# 在信息大爆炸的时代,很多同学都希望尽可能的抓取更多的知识,尽可能的不要遗漏任何热点…...
synchronized和volatile区别
synchronized和volatile是Java并发编程中两种重要的同步机制,它们之间存在明显的区别。以下是对这两者的详细比较: 一、基本定义与作用 synchronized 是一个用于实现线程同步的关键字。可以用来锁住方法或代码块,从而确保在同一时刻只有一个…...
125.验证回文串-力扣(LeetCode)
题目: 解题思路: 首先进行移除非字母数字字符,并将大写字符转换为小写字符的操作。这个过程中,主要利用快慢指针的方式来进行移除操作,通过加32将大写字符转换为小写字符。完成后,将前一半的数据与后一半的…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
