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

数据结构深度优先搜索遍历连通图+非连通图(C语言代码+遍历+终端输入内容)

首先数据结构(C语言版第二版)的关于深度优先搜索遍历连通图的图G4如下:

 使用邻接表去创建上面这个无向图,然后再使用书本DFS函数以及DFSTraverse函数实现深度优先搜索遍历

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
//下面三个结构体就是邻接表的结构体,完全一样的方式
typedef struct EdgeNode
{int adjvex;struct EdgeNode* next;
}EdgeNode;
typedef struct VertexNode
{char data;EdgeNode* firstedge;
}VertexNode;
typedef struct
{VertexNode adjlist[MAXVEX];int numVertexs;int numEdges;
}GraphAdjlist;
int visited[10];//一个标记数组,记录遍历过的不会重复遍历
//创建邻接表
void CreateALGraph(GraphAdjlist* G)
{int i, j, k;EdgeNode* p;printf("请输入顶点数+边数\n");scanf("%d%d", &G->numVertexs, &G->numEdges);getchar();//接收scanf残留的换行符\nprintf("请输入顶点的信息\n");for (i = 0; i < G->numVertexs; i++){scanf("%c", &G->adjlist[i].data);G->adjlist[i].firstedge = NULL;//初始化指向边表的指针为null}for (k = 0; k < G->numEdges; k++){printf("请输入(vi,vj)的头,尾,一共有%d条\n", G->numEdges);scanf("%d%d", &i, &j);//我们这里是实现深度遍历连通图的无向图p = (EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex = j;p->next = G->adjlist[i].firstedge;G->adjlist[i].firstedge = p;p = (EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex = i;p->next = G->adjlist[j].firstedge;G->adjlist[j].firstedge = p;}printf("邻接表创建成功\n");
}
void DFS(GraphAdjlist* G,int i)
{EdgeNode* p;visited[i] = 1;printf("%c ", G->adjlist[i].data);//先把这个顶点值输出,有点类似树的先序遍历(根左右)p = G->adjlist[i].firstedge;while (p!=NULL){if (visited[p->adjvex] == 0){DFS(G, p->adjvex);}p = p->next;}
}
void DFSTraverse(GraphAdjlist* G)
{int i;for (i = 0; i < G->numVertexs; i++){visited[i] = 0;//全部初始为0,然后遍历过的(vi,vj)就置为1 由未访问 -> 已访问}for (i = 0; i < G->numVertexs; i++){if (visited[i] == 0){DFS(G, i);}}
}
int main()
{GraphAdjlist G;CreateALGraph(&G);printf("深度遍历如下\n");DFSTraverse(&G);return 0;
}

关于深度遍历,很相似树的前序遍历(根左右),如果出现(根右左),其实这个问题也就是邻接表边表插入结点的时候,我们使用的是头插法,所以才有时候出现深度优先遍历会出现根右左,这个没关系的,不重复遍历就好 

下面是终端输入内容:

请输入顶点数+边数
8 9
请输入顶点的信息
01234567
请输入(vi,vj)的头,尾,一共有9条
0 1
请输入(vi,vj)的头,尾,一共有9条
0 2
请输入(vi,vj)的头,尾,一共有9条
1 3
请输入(vi,vj)的头,尾,一共有9条
1 4
请输入(vi,vj)的头,尾,一共有9条
3 7
请输入(vi,vj)的头,尾,一共有9条
4 7
请输入(vi,vj)的头,尾,一共有9条
2 5
请输入(vi,vj)的头,尾,一共有9条
2 6
请输入(vi,vj)的头,尾,一共有9条
5 6
邻接表创建成功
深度遍历如下
0 2 6 5 1 4 7 3

下标全部+1就可以查看12345678的遍历情况 

关于非连通图,代码通用的;

数据结构书本关于深度优先搜索遍历的非连通图如下:

终端输入内容如下: 

请输入顶点数+边数
8 8
请输入顶点的信息
01234567
请输入(vi,vj)的头,尾,一共有8条
0 1
请输入(vi,vj)的头,尾,一共有8条
1 3
请输入(vi,vj)的头,尾,一共有8条
1 4
请输入(vi,vj)的头,尾,一共有8条
3 7
请输入(vi,vj)的头,尾,一共有8条
4 7
请输入(vi,vj)的头,尾,一共有8条
2 5
请输入(vi,vj)的头,尾,一共有8条
2 6
请输入(vi,vj)的头,尾,一共有8条
5 6
邻接表创建成功
深度遍历如下
0 1 4 7 3 2 6 5

非连续图中的边数由9 -> 8 

相关文章:

数据结构深度优先搜索遍历连通图+非连通图(C语言代码+遍历+终端输入内容)

首先数据结构(C语言版第二版)的关于深度优先搜索遍历连通图的图G4如下: 使用邻接表去创建上面这个无向图&#xff0c;然后再使用书本DFS函数以及DFSTraverse函数实现深度优先搜索遍历 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #…...

信息安全工程师(55)网络安全漏洞概述

一、定义 网络安全漏洞&#xff0c;又称为脆弱性&#xff0c;是网络安全信息系统中与安全策略相冲突的缺陷&#xff0c;这种缺陷也称为安全隐患。漏洞可能导致机密性受损、完整性破坏、可用性降低、抗抵赖性缺失、可控性下降、真实性不保等问题。 二、分类 网络安全漏洞可以根据…...

member access within null pointer of type ‘ListNode‘

文章目录 前言一、空指针解引用二、访问已释放的内存三、 结构体定义问题四、错误的链表操作五、代码上下文六、示例代码七、调试建议 前言 p -> next p1; p1 p1 -> next; p p->next;runtime error: member access within null pointer of type ListNode如果出现…...

UE5蓝图中整理节点的方法

UE5蓝图中整理节点的方法 第一种&#xff1a;子图 右键选中的节点&#xff0c;出现一个面板&#xff0c;点击 Collapse Nodes 既可折叠选中的所有节点 注意&#xff1a;子图不可以被复制使用。 双击子图可以查看节点&#xff0c;若不想折叠选中的节点为子图&#xff0c;右键点…...

01,http 协议

1 &#xff0c;http 协议 &#xff1a;介绍 1 &#xff0c;http &#xff1a;是什么 Hyper Text Transfer Protocol &#xff1a;超文本传输协议 2 &#xff0c;传输内容 &#xff1a;文本 1 &#xff0c;内容 &#xff1a;      纯文本    2 &#xff0c;特殊 &#xf…...

在 typescript 中,如何封装一个 class 类来接收接口的响应数据

在 TypeScript 中&#xff0c;封装一个类来接收接口的响应数据是一个常见的需求&#xff0c;特别是在处理后端 API 响应时。这通常涉及到定义与后端 API 响应结构相匹配的接口&#xff08;或类型&#xff09;&#xff0c;并在类中创建方法来处理这些数据。以下是一个简单的示例…...

力扣周赛第420场 中等 3325.字符至少出现k次的子字符串 I

文章目录 题目介绍题解 题目介绍 题解 滑动窗口思想&#xff1a;参考 3.无重复字符的最长子串 链接 代码如下&#xff1a; class Solution {public int numberOfSubstrings(String s, int k) {int n s.length(), res 0;for(int left 0; left < n; left){// 记录窗口内…...

【Spring框架】Spring核心思想IoC以及依赖注入DI详解

目录 Spring框架前言 服务端三层开发表现层业务层持久层 Spring框架的概述Spring框架的优点Spring核心——IoC什么是IoC&#xff1f;O.o什么是耦合度&#xff1f; 创建第一个IoC程序导入必要依赖编写接口和实现类编写Spring核心配置文件测试类进行测试 Spring配置文件Bean对象的…...

Java项目-基于springboot框架的智慧外贸系统项目实战(附源码+文档)

作者&#xff1a;计算机学长阿伟 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、ElementUI等&#xff0c;“文末源码”。 开发运行环境 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBoot、Vue、Mybaits Plus、ELementUI工具&#xff1a;IDEA/…...

Python程序控制结构 if语句详解

前面我们已经详细介绍了Python编程基础入门&#xff1a;从风格到数据类型再到表达式 在编程中&#xff0c;控制结构决定了代码的执行顺序。Python提供了丰富的控制结构&#xff0c;可以帮助程序根据不同条件做出不同的决策和操作。本文将深入介绍Python中常见的控制结构——包…...

【ppq install】

简介 PPQ 是 Sensetime OpenPPL 团队开源的量化部署工具&#xff0c;经过量化的神经网络往往能够在端侧加速600%~800%&#xff0c;而在目前已经支持OpenPPL, TensorRT, SNPE, NXP, Metax等多个不同平台的量化模拟与网络部署。PPQ 不仅限于提供强大而先进的量化优化算法&#x…...

3DGS相关方法conda环境配置

环境&#xff1a;ubuntu22.04&#xff0c;cuda_11.7 conda create -n 3dgs python3.8 -y conda activate 3dgs python -m pip install --upgrade pip pip uninstall torch torchvision functorch tinycudann pip install torch2.1.2cu118 torchvision0.16.2cu118 torchaudio2…...

python画图|曲线动态输出

【1】引言 前序教程中的曲线动态输出&#xff0c;其实是把曲线按照左右移动的形式输出&#xff08;波的传递形式&#xff09;。 python画图|曲线动态输出基础教程_python 动态曲线-CSDN博客 但有些时候我们更期待的是曲线不移动&#xff0c;随着自变量的增加而输出因变量&am…...

电子商务类型

常见电子商务类型及其代表性的例子&#xff1a; B2B&#xff08;Business to Business&#xff09; 定义&#xff1a;B2B 模式是指企业与企业之间的商业交易。在这种模式下&#xff0c;企业通过电子商务平台相互提供产品或服务。 特点&#xff1a; 大宗交易&#xff1a;通常…...

vue elementui el-table实现增加行,行内编辑修改

需求&#xff1a; 前端进行新增表单时&#xff0c;同时增加表单的明细数据。明细数据部分&#xff0c;可进行行编辑。 效果图&#xff1a; <el-card><div slot"header"><span style"font-weight: bold">外来人员名单2</span><…...

1. Redis简介与安装

1.1 什么是Redis Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、基于内存的数据结构存储系统&#xff0c;支持多种数据结构&#xff0c;如字符串、列表、集合、有序集合和哈希。它不仅能作为一个高效的缓存工具&#xff0c;还能作为消息队列、分布式锁和…...

Redis的持久化存储和集群管理操作

Redis 的持久化存储和集群 一、引言 Redis 是一个开源的内存数据结构存储系统&#xff0c;被广泛应用于缓存、消息队列、排行榜等场景。然而&#xff0c;由于数据存储在内存中&#xff0c;一旦服务器重启或出现故障&#xff0c;数据就会丢失。为了解决这个问题&#xff0c;Re…...

Auto-encoder(自编码器)

Auto-encoder&#xff08;自编码器&#xff09; 1 基本概念 自编码就和之前的cycle GAN的概念很像&#xff0c;假設你有非常大量的圖片&#xff0c;在 Auto-Encoder 裡面你有兩個 Network&#xff0c;一個叫做 Encoder&#xff0c;一個叫做 Decoder&#xff0c;他們就是兩個 N…...

Vue+sortable+el-table表格排序使用指南

前言 这两天遇到一个需求&#xff1a;在点击【设置优先级】的按钮后弹出关于玩法类型的table&#xff0c;点击【排序】按钮可以后可以进行排序。由于组内使用的组件库是 element-ui&#xff0c;那我首先就想到了使用 el-table组件&#xff0c;但奈何其版本原因不能相应的拖拽排…...

表数据删一半,为什么表文件大小不变?

参数innodb_file_per_table 这个参数设置为ON&#xff0c;表示每个表数据单独存在一个文件中&#xff0c;这时如果执行drop命令&#xff0c;系统会直接删除表文件。 这个参数设置为off时&#xff0c;所有表的数据和索引都存在共享的.ibdata文件&#xff0c;即使表删掉了&…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...