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

数据结构--图的遍历 DFS

数据结构–图的遍历 DFS

树的深度优先遍历

//树的先根遍历
void PreOrder(TreeNode *R)
{if(R != NULL){visit(R);   //访问根节点while(R还有下一个子树T)PreOrder(T);//先根遍历下一棵子树}
}

图的深度优先遍历

bool visited [MAX_VERTEX_NUM];   //访问标记数组
void DFS(Graph G, int v) //从顶点v出发,深度优先遍历图
{visit(v);//访问顶点visited[v] = TRUE; //设已访问标记{for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w))if(!visited[w]) //w为u的尚未访问的邻接顶点DFS(G, w);}
}

如果是⾮连通图,则⽆法遍历完所有结点

bool visited[MAX_VERTEX_NUM];   //访问标记数组void DFSTraverse(Graph G)//对图G进行深度优先遍历
{for(v = 0; v < G.vexnum; ++v)visited[v] = FALSE;//初始化已访问标记数据for(v = 0; v < G.vexnum; ++v)if(!visited[v])DFS(G, v);//本代码中是从v=0开始遍历
}void DFS(Graph G, int v) //从顶点v出发,深度优先遍历图G
{visit(v);//访问顶点vvisited[v] = TRUE; //设已访问标记for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w))if(!visited[w]) //w为u的尚未访问的邻接顶点DFS(G,w);
}

复杂度分析

空间复杂度:来⾃函数调⽤栈,最坏情况,递归深度为 O ( ∣ V ∣ ) \color{red}空间复杂度:来⾃函数调⽤栈,最坏情况,递归深度为O(|V|) 空间复杂度:来函数调栈,最坏情况,递归深度为O(V)

空间复杂度:最好情况, O ( 1 ) \color{purple}空间复杂度:最好情况,O(1) 空间复杂度:最好情况,O(1)

时间复杂度=访问各结点所需时间+探索各条边所需时间

邻接矩阵 \color{red}邻接矩阵 邻接矩阵存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|)的时间,⽽总共有|V|个顶点
时间复杂度= O ( ∣ V ∣ 2 ) \color{red}O(|V|^2) O(V2)

邻接表 \color{red}邻接表 邻接表存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(|E|)的时间,
时间复杂度= O ( ∣ V ∣ + ∣ E ∣ ) \color{red}O(|V|+|E|) O(V+E)

注:
同⼀个图的 邻接矩阵 \color{red}邻接矩阵 邻接矩阵表示⽅式 唯⼀ \color{red}唯⼀ ,因此 深度优先遍历序列唯⼀ \color{red}深度优先遍历序列唯⼀ 深度优先遍历序列唯
同⼀个图 邻接表 \color{red}邻接表 邻接表表示⽅式 不唯⼀ \color{red}不唯⼀ 不唯,因此 深度优先遍历序列不唯⼀ \color{red}深度优先遍历序列不唯⼀ 深度优先遍历序列不唯

深度优先⽣成树

同⼀个图的邻接矩阵表示⽅式唯⼀,因此深度优先遍历序列唯⼀,深度优先⽣成树也唯⼀
同⼀个图邻接表表示⽅式不唯⼀,因此深度优先遍历序列不唯⼀,深度优先⽣成树也不唯⼀

深度优先⽣成森林

图的遍历与图的连通性

⽆向图 \color{red}⽆向图 向图进⾏BFS/DFS遍历
调⽤BFS/DFS函数的次数=连通分量数

对于 连通图 \color{red}连通图 连通图,只需调⽤1次 BFS/DFS

有向图 \color{red}有向图 有向图进⾏BFS/DFS遍历
调⽤BFS/DFS函数的次数要具体问题具体分析

若起始顶点到其他各顶点都有路径,则只需调⽤1次
BFS/DFS 函数

对于 强连通图 \color{red}强连通图 强连通图,从任⼀结点出发都只需调⽤1次 BFS/DFS

知识回顾与重要考点

相关文章:

数据结构--图的遍历 DFS

数据结构–图的遍历 DFS 树的深度优先遍历 //树的先根遍历 void PreOrder(TreeNode *R) {if(R ! NULL){visit(R); //访问根节点while(R还有下一个子树T)PreOrder(T);//先根遍历下一棵子树} }图的深度优先遍历 bool visited [MAX_VERTEX_NUM]; //访问标记数组 void DFS(Grap…...

SpringBoot集成MyBatisPlus+MySQL(超详细)

前言 查看此文章前强烈建议先看这篇文章&#xff1a;Java江湖路 | 专栏目录 该文章纪录的是SpringBoot快速集成MyBatis Plus&#xff0c;每一步都有记录&#xff0c;争取每一位看该文章的小伙伴都能操作成功。达到自己想要的效果~ 文章目录 前言1、什么是MyBatisPlus2、Spring…...

一边是计算机就业哀鸿遍野,一边是高考生疯狂涌向计算机专业

在张雪峰推荐的几大专业里&#xff0c;计算机专业是其中之一。近几年&#xff0c;计算机专业报考热度不减&#xff0c;但就业前景却令人堪忧&#xff0c;互联网裁员接二连三&#xff0c;许多码农找不到工作。 一位网友感叹&#xff1a;一边是计算机就业哀鸿遍野&#xff0c;一…...

解决外部主机无法访问Docker容器的方法

使用Docker启动了一个tomcat容器&#xff0c;并做了端口映射&#xff0c;但是外部主机仍然无法访问。 编辑centos上的配置文件 vi /etc/sysctl.conf net.ipv4.ip_forward1 systemctl restart network保存以后即可生效&#xff0c;这个配置是开启linux的ip数据包转发功能&#…...

IDEA中修改类头的文档注释信息

IDEA中修改类头的文档注释信息 选择File--Settings--Editor--File and Code Templates--Includes&#xff0c;可以把文档注释写成这种的 /**author: Arbicoralcreate: ${YEAR}-${MONTH}-${DAY} ${TIME}Description: */这样回看就可以很清楚的看到自己创建脚本的时间&#xff…...

建模教程:如何利用3ds Max 和 After Effects 实现多通道渲染和后期合成

推荐&#xff1a; NSDT场景编辑器 助你快速搭建可二次开发的3D应用场景 1. 创建基本场景 步骤 1 打开 3ds Max。 打开 3ds Max。 步骤 2 我做了一个简单的场景。我放了三个 彼此之间有一定距离的物体。 制作对象 步骤 3 按 Ctrl-C 键 在透视视图中创建摄影机。 创建相机 …...

JPA之Hibernate

JPA 定义&#xff1a;是 JavaEE 中一组用于持久化数据的 API&#xff0c;它提供了一种标准的 ORM 规范&#xff0c;用于 Java 对象映射到数据库中。 JPA 的开发是为了简化企业级应用程序的开发&#xff0c;降低应用程序与数据库之间的耦合度&#xff0c;并提高应用程序的可维护…...

leetcode(力扣)剑指 Offer 16. 数值的整数次方 (快速幂)

文章目录 题目描述思路分析完整代码 题目描述 实现 pow(x, n) &#xff0c;即计算 x 的 n 次幂函数&#xff08;即&#xff0c;xn&#xff09;。不得使用库函数&#xff0c;同时不需要考虑大数问题。 示例 1&#xff1a; 输入&#xff1a;x 2.00000, n 10 输出&#xff1a;10…...

git命令分类合集

配置 git config --global user.name <name>&#xff1a;设置全局用户名 git config --global user.email <email>&#xff1a;设置全局用户邮箱 git config --global core.editor <editor>&#xff1a;设置全局文本编辑器创建与克隆仓库 git init&#xf…...

微信小程序打开地图的方法

1、打开内置地图 wx.openLocation({latitude: 31.230416, // 上海的纬度longitude: 121.473701, // 上海的经度name: 上海市, // 地点名称address: 中国上海市黄浦区人民广场, // 地址的详细说明scale: 18, // 缩放比例success: function(res) {console.log(打开地图成功);},f…...

快手头部主播合体,二驴祁天道直播首秀销售额破亿

2023年刚刚过半&#xff0c;直播江湖突然生变。 快手头部娱乐主播「二驴」与快手户外主播第一人「祁天道」宣布“合体”&#xff0c;两者加总的粉丝量接近1亿&#xff0c;又一个“超级网红IP”诞生。 ▲图源&#xff1a;二驴的、祁天道快手截图 从白手起家的草根&#xff0c;…...

Golang Devops项目开发(1)

1.1 GO语言基础 1 初识Go语言 1.1.1 开发环境搭建 参考文档&#xff1a;《Windows Go语言环境搭建》 1.2.1 Go语言特性-垃圾回收 a. 内存自动回收&#xff0c;再也不需要开发人员管理内存 b. 开发人员专注业务实现&#xff0c;降低了心智负担 c. 只需要new分配内存&#xff0c;…...

Django系列之DRF简单使用

基于ModelViewSets的简单使用 models.py from django.db import modelsclass AuthorDetail(models.Model):gender models.CharField(max_length8)birthday models.DateField()telephone models.BigIntegerField()addr models.CharField(max_length64)class Author(models…...

新闻标题文本分类任务

目录 知识回顾使用debug调试 知识回顾 预处理内容 文本主要进行清洗、分词/分字 ID替换(不希望计算机看到文字&#xff0c;而是ID)&#xff0c;通过语料表来表示&#xff0c;根据频率高低来分配ID号 文本的ID映射到文本的一个特征向量&#xff0c;进行词嵌入(Embedding)&…...

自己实现MyBatis 底层机制--抽丝剥茧(上)

&#x1f600;前言 本篇博文是学习过程中的笔记和对于MyBatis底层机制的分析思路&#xff0c;希望能够给您带来帮助&#x1f60a; &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到…...

Django后端执行成功或失败状态码

后端执行成功或失败以状态码的形式告诉前端&#xff0c;处理成功返回200系列状态码&#xff0c;执行前端then里面的代码&#xff1b;处理失败返回400/500系列状态码&#xff0c;执行catch里面的代码。 200 OK &#xff1a;服务器成功返回用户请求的数据 201 CREATED &#xff…...

Prometheus中的关键设计

1、标准先行&#xff0c;注重生态 Prometheus 最重要的规范就是指标命名方式&#xff0c;数据格式简单易读。比如&#xff0c;对于应用层面的监控&#xff0c;可以要求必须具备这几个信息。 指标名称 metric Prometheus 内置建立的规范就是叫 metric&#xff08;即 __name__…...

Centos7 安装yum

1、检查主机名和网络并且配置/etc/hosts文件 查看主机名&#xff1a;hostname 查看ip :ifconfig vi /etc/hosts//添加把主机名和IP配置进去hosts文件192.18.56.111 orcale12c2、关闭防火墙 systemctl status firewalld.service//检查防火墙状态 暂时关闭防火墙&#xff0c;下…...

无涯教程-Lua - 简介

Lua是一种轻量语言&#xff0c;它的官方版本只包括一个精简的核心和最基本的库。这使得Lua体积小、启动速度快。它用ANSI C语言编写并以源代码形式开放&#xff0c;编译后仅仅一百余K&#xff0c;可以很方便的嵌入别的程序里。和许多“大而全”的语言不一样&#xff0c;网络通信…...

【第一阶段】kotlin语言引用数据类型

Java语言中有两种数据类型 第一种&#xff1a;基本数据类型 如int double等 第二种&#xff1a;引用数据类型。如String kotlin只有一种数据类型&#xff0c;看起来都是引用数据类型&#xff0c;实际上编译器会在Java字节码中&#xff0c;修改成基本类型 //Java语言中有两种数…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...