图(graph)的遍历----深度优先(DFS)遍历

目录

前言

深度优先遍历(DFS)

1.基本概念

 2.算法思想

3.二叉树的深度优先遍历(例子) 

图的深度优先遍历

1.图(graph)邻接矩阵的深度优先遍历

思路分析

代码实现

2.图(graph)邻接表的深度优先遍历

思路分析

代码实现

递归代码

非递归代码


前言

        在前面学习过二叉树的时候我们就已经接触到深度优先搜索和广度优先搜索,二叉树的前序遍历和后序遍历都属于深度优先遍历的一种,但是对于二叉树这种有规律的数据结很容易理解,但是如果是对于图这种没有规律的数据结构又该如何去实现深度优先和广度优先遍历呢?下面就一起来看看吧!

深度优先遍历(DFS)

1.基本概念

        深度优先搜索是用来遍历或搜索树和图数据结构的算法,它是可以从任意跟节点开始,选择一条路径走到底,并通过回溯来访问所有节点的算法。简单来说就是通过选择一条道路走到无路可走的时候回退到上一个岔路口,并标记这条路已走过,选择另外一条道路继续走,直到走遍每一条路。(一句话概括:一路走到黑,黑了就回头)

 2.算法思想

Dfs思修基于递归思想,通过递归的形式来缩小问题规模,把一件事分割成若干个相同的小事,逐步完成。

深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义,深度优先,则是以深度为准则,先一条路走到底,直到达到目标。这里称之为递归下去。

否则既没有达到目标又无路可走了,那么则退回到上一步的状态,走其他路。这便是回溯上来。

3.二叉树的深度优先遍历(例子) 

为了大家更好的了解深度优先遍历的算法,我下面举一个二叉树深度优先遍历的例子,如下图所示的一个二叉树,对其进行前序遍历(深度优先遍历) 

结果为: A B D H I E J C F K G  

前序遍历就是从根结点出发,一直向左子节点走,直到左子节点不存在然后返回到上一个节点走这个节点的右子节点,然后一直往右子节点走,同样的也是走不通为止就返回。很显然这种一路走到黑,黑了就回头的方式,就是深度优先遍历的过程。

图的深度优先遍历

        对于二叉树的深度优先遍历大家都很好理解,但是如果对于图的话,那怎么去进行深度优先遍历呢?

如图所示,拿到这么一个图我们从V1开始对其进行深度优先遍历,那么每一次遇到分叉点走不同的路径遍历到的结果是不一样的,所以对于一个图的深度优先变量结果可以为多种。

深度优先遍历算法步骤

  1. 访问初始结点v,并标记结点v为已访问。
  2. 查找结点v的第一个邻接结点w。
  3. 若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个结点继续。
  4. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)
  5. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

在此之前我们学习了图的两种储存方式,分别是邻接矩阵和邻接表,那么这两种存储方式进行深度优先遍历结果会有什么不同呢?我们接着看。 

1.图(graph)邻接矩阵的深度优先遍历

思路分析

如上图所示,从2位置开始进行深度优先遍历,由于图可能是具有环形结构的,为了避免进入到环内的死循环,这里我们需要用到一个辅助数组visited来标记某一个顶点是否遍历过,如果遍历过的话,那么就不走这个方向,如果全部的方向都被标记遍历过,那就返回到上一个位置,换一个方向去遍历。(递归算法)

        对于visited数组,初始化为0,表示未访问过,如果访问了的话那么就设置为1 

最后整个图遍历完成之后,visited数组里面的数组全都为1 ,也就是说这个图已经变量完成了

代码实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Maxint 32767
#define Maxnum 100//最大顶点数//数据类型
typedef struct d { char id[10];//……
}
ElemType;//图的邻接数组
typedef struct graph {ElemType vexs[Maxnum];//图数据int matrix[Maxnum][Maxnum];//二维数组矩阵int vexnum;//点数int arcnum;//边数
}Graph;//节点id查找下标
int Locate_vex(Graph G, char* id) {for (int i = 0; i < G.vexnum; i++)if (strcmp(G.vexs[i].id,id)==0)return i;return -1;
}
//构造邻接矩阵(无向图,对称矩阵)(有向图)赋权图
void Create_graph(Graph* G) {printf("请输入顶点个数和边的个数:\n");scanf("%d %d", &G->vexnum, &G->arcnum);//输入点数边数printf("请输入顶点数据:\n");for (int i = 0; i < G->vexnum; i++) {scanf("%s", G->vexs[i].id);}for (int x = 0; x < G->vexnum; x++) {for (int y = 0; y < G->vexnum; y++) {if (x == y)G->matrix[x][y] = 0;//对角线初始化为0elseG->matrix[x][y] = Maxint;//其他初始化为Maxint}}printf("请输入边相关数据:\n");for (int k = 0; k < G->arcnum; k++) {char a[10], b[10];int w;scanf("%s %s %d", a, b, &w);//a->bint i = Locate_vex(*G, a);int j = Locate_vex(*G, b);//矩阵赋值G->matrix[i][j] = w;G->matrix[j][i] = w;//删掉这个,表示有向图}
}//输出矩阵
void print_matrix(Graph G) {printf("矩阵为:\n");for (int i = 0; i < G.arcnum; i++) {for (int j = 0; j < G.arcnum; j++)printf("%-5d ", G.matrix[i][j]);printf("\n");}printf("图的顶点个数和边数:%d,%d\n", G.vexnum, G.arcnum);
}//访问输出
void visit(Graph G,int loca) {printf("%s ", G.vexs[loca].id);
}
//深度优先遍历DFS
void DFS(Graph G, char* begin,int* visited) {int loca = Locate_vex(G, begin);visit(G, loca);visited[loca] = 1;//访问完后,visited对应的下标标记为1for (int i = 0; i < G.vexnum; i++) {//当前顶点对其他顶点进行遍历,如果有通路就执行访问操作if (G.matrix[loca][i] != 0&& G.matrix[loca][i]!=Maxint )if(!visited[i])//如果visited为0的话(下一个顶点未访问过),那么就进入到下一个顶点继续访问DFS(G, G.vexs[i].id , visited);}return;
}int main() {Graph G;Create_graph(&G);print_matrix(G);int* visited = (int*)malloc(sizeof(int) * G.vexnum);memset(visited, 0, sizeof(int)*G.vexnum);//初始化为0printf("DFS:\n");DFS(G, "B" , visited);
}

输出结果:

2.图(graph)邻接表的深度优先遍历

思路分析

前面我们学习过了邻接表是由两种节点组成的,分别是头结点和边节点,头结点是用来储存数据的,而变节点是用来储存于当前节点有通路的节点的引索。如图所示

对于邻接表的话,那怎么去书写代码呢?同样的我们还是需要一个visited数组来标记已经访问过的节点,然后对下一个节点进行判断是否访问过,如果没有访问过那么就进入到下一个节点的递归,如果访问过那就换一个方向继续访问,如果都访问过,那就返回到上一个节点的位置重复以上的操作。下面我提供两种代码的书写方式,分别是递归和非递归来去实现深度优先遍历。

代码实现

创建图代码(邻接表):

#include<stdio.h>
#include<string.h>//数据结构体
typedef struct datatype {char id[10];//字符串编号//………………
}ElemType;
//边节点存储结构
typedef struct arcnode {int index;//指向顶点的位置int weight;//权struct arcnode* nextarc;//指向下一个边节点
}Anode;
//顶点结点存储结构
typedef struct vexnode {ElemType data;Anode* firstarc;
}Vhead;
//图结构
typedef struct {Vhead* vertices;int vexnum;int arcnum;
}Graph;//顶点id查找下标
int Locate_vex(Graph G, char* id) {for (int i = 0; i < G.vexnum; i++)if (strcmp(G.vertices[i].data.id,id)==0)return i;return -1;
}
//创建头节点
void Create_vexhead(Graph *G,int n) {G->vertices = (Vhead*)malloc(sizeof(Vhead) *n);if (!G->vertices) {printf("ERROR\n");exit(-1);}else {for (int i = 0; i < n ; i++) {scanf("%s", G->vertices[i].data.id);G->vertices[i].firstarc = NULL;}}
}
//创建一个边节点
Anode* Create_arcnode(int loca, int w) {Anode* arc = (Anode*)malloc(sizeof(Anode));if (!arc){printf("ERROR\n");exit(-1);}arc->index = loca;arc->nextarc = NULL;arc->weight = w;return arc;
}
//创建邻接表(无向图)(有向图)
void Create_graph(Graph* G) {printf("输入顶点数和边数:\n");scanf("%d %d", &G->vexnum, &G->arcnum);printf("输入顶点数据:\n");Create_vexhead(G, G->vexnum);printf("输入边数据:\n");for (int k = 0; k <G->arcnum; k++) {ElemType a, b;int w;scanf("%s%s%d", a.id, b.id, &w);int i = Locate_vex(*G, a.id);int j = Locate_vex(*G, b.id);//头插法//a->bAnode* p = Create_arcnode(j, w);p->nextarc = G->vertices[i].firstarc;G->vertices[i].firstarc = p;//如果创建有向图的话,直接把下面的代码删掉即可//b->aAnode* q = Create_arcnode(i, w);q->nextarc = G->vertices[j].firstarc;G->vertices[j].firstarc = q;}
}//访问
void visit(Graph G, int index) {printf("%s ", G.vertices[index].data.id);
}//输出图
void print(Graph G) {printf("以下是图的顶点连接关系:\n");for (int i = 0; i < G.vexnum; i++) {printf("%s:", G.vertices[i].data.id);Anode* cur= G.vertices[i].firstarc;while (cur) {visit(G, cur->index);cur = cur->nextarc;}printf("\n");}printf("顶点和边数分别是:%d %d\n", G.vexnum, G.arcnum);
}
递归代码
//深度优先遍历DFS0(递归实现)
void DFS0(Graph G, char* begin_id,int* visited) {int index = Locate_vex(G, begin_id);visit(G, index);visited[index] = 1;//标记这个顶点已经访问过了Anode* p = G.vertices[index].firstarc;//找到这个顶点的下一个位置pwhile (p) {if (visited[p->index] == 0) {//如果没有访问过的话,就进入到下一个递归DFS0(G, G.vertices[p->index].data.id, visited);}p = p->nextarc;//退出之后换一个方向访问}return;
}
非递归代码
//深度优先遍历DFS(非递归实现)
void DFS(Graph G,char* begin_id) {//判断是否变量过int* visited = (int*)malloc(sizeof(int) * G.vexnum);memset(visited, 0, sizeof(int) * G.vexnum);//全部初始化为0//记录路径int* path = (int*)malloc(sizeof(int) * G.vexnum);memset(path, -1, sizeof(int) * G.vexnum);int i = -1;//初始化int index = Locate_vex(G, begin_id);int count = 0;//表示已经访问了多少个顶点Anode* p= G.vertices[index].firstarc;//初始化下一个位置指针pwhile (count<G.vexnum) {if (p) {if (visited[index] == 0) {visit(G, index);visited[index] = 1;i++;path[i] = index;//记录当前路径p = G.vertices[index].firstarc;index = p->index;//指向下一个位置count++;}else {p = p->nextarc;index = p->index;}}//回溯过程else {index = path[i - 1];//返回到上一个位置p = G.vertices[index].firstarc->nextarc;//p指针向后移动一位index = p->index;i--;}}
}

测试结果:

int main() {Graph G;Create_graph(&G);print(G);printf("\n递归DFS0深度优先遍历:\n");int* visited = (int*)malloc(sizeof(int) * G.vexnum);memset(visited, 0, sizeof(int) * G.vexnum);DFS0(G, "B", visited);printf("\n非递归DFS深度优先遍历:\n");DFS(G, "B");
}

 以上就是本期的全部内容了,我们下次接着学习图的广度优先遍历,下次见咯!

分享一张壁纸: 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/168502.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Web】| CSS Float (浮动)的使用方法

Float&#xff08;浮动&#xff09;概念 CSS的Float&#xff08;浮动&#xff09;&#xff0c;会使得元素向左或者向右移动&#xff0c;其它周围元素也会重新排列。 Float浮动&#xff0c;往往是用于图像&#xff0c;但它的布局一样非常有效。 元素如何浮动 元素的水平方向…

【MySQL架构篇】MySQL字符集、大小写规范及默认数据库

文章目录 1. 字符集与字符集比较规则2. 大小写规范3. 默认数据库4. 与文件系统相关 1. 字符集与字符集比较规则 MySQL有4个级别的字符集和比较规则&#xff0c;分别是 服务器级别数据库级别表级别列级别 当创建对应表或列未指定字符集时&#xff0c;默认会取其上一级别的字符…

MySQL中的表操作,配置文件,储存引擎,数据类型

MySQL中的表操作 1 查库&#xff08;已密码登陆mysql&#xff09; show databases; 2 添加库 create database t1; 3 表操作 1选定操作库 use t1 2在库里添加表格式 create table t1(id int, name varchar(32), gender varchar(32),age int); 3往表里添加具体元素 insert…

OpenCV 笔记(2):图像的属性以及像素相关的操作

Part11. 图像的属性 11.1 Mat 的主要属性 在前文中&#xff0c;我们大致了解了 Mat 的基本结构以及它的创建与赋值。接下来我们通过一个例子&#xff0c;来看看 Mat 所包含的常用属性。 先创建一个 3*4 的四通道的矩阵&#xff0c;并打印出其相关的属性&#xff0c;稍后会详细…

django建站过程(2)创建第一个应用程序页面

创建第一个应用程序页面 设置第一个页面【settings.py,urls.py,views.py】settings.pyurls.pyviews.py django是由一系列应用程序组成&#xff0c;协同工作&#xff0c;让项目成为一个整体。前面已创建了一个应用程序baseapp,使用的命令 python manage.py startapp baseapps这…

2023全新小程序广告流量主奖励发放系统源码 流量变现系统

2023全新小程序广告流量主奖励发放系统源码 流量变现系统 分享软件&#xff0c;吃瓜视频&#xff0c;或其他资源内容&#xff0c;通过用户付费买会员来变现&#xff0c;用户需要付费&#xff0c;有些人喜欢白嫖&#xff0c;所以会流失一部分用户&#xff0c;所以就写了这个系统…

RustCC分享会|非凸科技与开发者共同探讨Rust安全进化

10月15日&#xff0c;非凸科技受邀参加RustCC联合多家开发者社区组织的Global Tour of Rust技术分享活动&#xff0c;旨在为Rust开发者提供交流互动的平台&#xff0c;分享Rust语言的知识、经验和最佳实践。 活动上&#xff0c;非凸科技成都分公司研发总监赵海峰以“Rust安全进…

系统架构师备考倒计时13天(每日知识点)

1. 数据仓库四大特点 面向主题的。操作型数据库的数据组织面向事务处理任务&#xff0c;各个业务系统之间各自分离&#xff0c;而数据仓库中的数据是按照一定的主题域进行组织的。集成的。数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整…

TechSmith Camtasia 2023 for Mac 屏幕录像视频录制编辑软件

​ TechSmith Camtasia for Mac 2023中文破解版 是一款专业的屏幕录像视频录制编辑软件&#xff0c;非常容易就可以获得精彩的截屏视频。创建引人注目的培训&#xff0c;演示和演示视频。Camtasia 屏幕录制软件简化&#xff0c;直观&#xff0c;让您看起来像专业人士。利用Camt…

安卓使用android studio跨进程通信之AIDL

我写这篇文章不想从最基础的介绍开始,我直接上步骤吧. 1.创建服务端 1.1:创建服务端项目:我的as版本比较高,页面就是这样的 1.2:创建AIDL文件,右键项目,选中aidl aidl名字可以自定义也可以默认 basicTypes是自带的,可以删掉,也可以不删,然后把你自己所需的接口写上去 1.3:创建…

让uniGUI支持https

今天在专家的帮助下&#xff0c;成功的让uniGUI支持https了。 首先&#xff0c;去申请个**的证书。我同事去阿里申请的&#xff0c;申请回是一个zip文件&#xff0c;里面有两个文件&#xff0c;一个扩展是per&#xff0c;一个key 然后&#xff0c;把这两个证书文件放到uniGUI…

06、Python 序列 与 列表 与 元组 的关系和创建 和 简单使用

目录 序列元组与列表关系总结 创建元组与列表方式一创建元组注意点 创建元组与列表方式二简单使用通过索引访问元素子序列序列加法序列乘法in运算 了解Python序列 创建列表和元组 通过索引访问元素 子序列 序列运算 序列 所谓序列&#xff0c;指的是一种包含多项数据的数据结…

【蓝桥每日一题]-动态规划 (保姆级教程 篇11)#方格取数2.0 #传纸条

目录 题目&#xff1a;方格取数 思路&#xff1a; 题目&#xff1a;传纸条 思路&#xff1a; 题目&#xff1a;方格取数 &#xff08;跑两次&#xff09; 思路&#xff1a; 如果记录一种方案后再去跑另一个方案&#xff0c;影响因素太多了&#xff0c;所以两个方案要同时开…

FL Studio 21 for Mac中文破解版百度网盘免费下载安装激活

FL Studio 21 for Mac中文破解版是Mac系统中的一款水果音乐编辑软件&#xff0c;提供多种插件&#xff0c;包括采样器、合成器和效果器&#xff0c;可编辑不同风格的音乐作品&#xff0c;Pattern/Song双模式&#xff0c;可兼容第三方插件和音效包&#xff0c;为您的创意插上翅膀…

Unity3D 基础——鼠标悬停更改物体颜色,移走恢复

方法介绍 【unity学习笔记】OnMouseEnter、OnMouseOver、OnMouseExit_unity onmouseover_一白梦人的博客-CSDN博客https://blog.csdn.net/a1208498468/article/details/117856445 GetComponent()详解_getcomponet<> 动态名称-CSDN博客https://blog.csdn.net/kaixindrag…

uniapp 测试 app 到安卓模拟器部署方法以及常见错误解决 无废话

uniapp 测试 app 到安卓模拟器 1.1 安装安卓模拟器 https://www.yeshen.com/ 1.2 查看安装模拟器端口 右击夜神模拟器属性打开文件位置 在打开的文件夹找到 debugReport 双击运行查看运行出来的端口号 一般都是&#xff1a;62001 1.3 HBuilder 配置 选中项目运行运行到手机…

自然语言处理---Transformer机制详解之ELMo模型介绍

1 ELMo简介 ELMo是2018年3月由华盛顿大学提出的一种预训练模型. ELMo的全称是Embeddings from Language Models.ELMo模型的提出源于论文<< Deep Contextualized Word Representations >>.ELMo模型提出的动机源于研究人员认为一个好的预训练语言模型应该能够包含丰…

opencv dnn模块 示例(19) 目标检测 object_detection 之 yolox

文章目录 0、前言1、网络介绍1.1、输入1.2、Backbone主干网络1.3、Neck1.4、Prediction预测输出1.4.1、Decoupled Head解耦头1.4.2、Anchor-Free1.4.3、标签分配1.4.4、Loss计算 1.5、Yolox-s、l、m、x系列1.6、轻量级网络研究1.6.1、轻量级网络1.6.2、数据增强的优缺点 1.7、Y…

【JavaEE】线程安全的集合类 -- 多线程篇(9)

线程安全的集合类 多线程环境使用 ArrayList多线程环境使用队列多线程环境使用哈希表 多线程环境使用 ArrayList 自己使用同步机制 (synchronized 或者 ReentrantLock)Collections.synchronizedList(new ArrayList); synchronizedList 是标准库提供的一个基于 synchronized 进…

nginx的使用

一、nginx下载 1.打开nginx官网http://nginx.org/en/index.html 下载安装链接 nginx&#xff08;NGINX&#xff09;详细下载安装及使用教程&#xff08;非常适合入门&#xff09;_nginx下载-CSDN博客 二、安装nginx # 前往用户根目录 cd ~#下载nginx1.13.7wget http://nginx…