首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

遍历 --- 深度优先遍历

在讲深度优先遍历之前,先来回顾一下这种数据结构。 1. 是什么? ,也是一种数据结构,其节点可以具有零个或者多个相邻元素,两个节点之间连接称为边,节点也称为顶点,图表示是多对多关系。 ?...F ---> G; 无向:上面的就是无向,就是节点之间连线是没有方向,A可以到B,B也可以到A; 有向:节点之间连线是有方向; 带权:边具有权值叫做带权,也叫网。...无向遍历: (1). 遍历分类: 遍历分为两种: 深度优先:depth first search,简称DFS。...类似于二叉树层序遍历,具体本文不做介绍。 (2). 深度优先算法步骤: 以开篇中图为例: 访问A,并将A标记为已访问; 找到A第一个未被访问邻接顶点,怎么找?...isVisited[vertexList.indexOf(str)]){ dfs(str, isVisited); } } } 深度优先遍历方法都写了详细注释

1.4K20
您找到你想要的搜索结果了吗?
是的
没有找到

深度遍历和广度遍历

理论部分 深度遍历和广度遍历都不算很难像极了二叉树前序遍历和层序遍历,如下面的,可以用右边邻接矩阵进行表示,假设以顶点0开始对整幅进行遍历的话,两种遍历方式思想如下: 1....深度优先遍历(depthFirstSearch—DFS) 由初始顶点开始,沿着一条道一直走,当走到走不动时候,再回来走一条可以走道,然后再继续往下走,直到走不动,再回来…对应于本图来说就是从0开始往前走...之前我们是直接就默认从0开始进行往下遍历了,但是从0开始遍历没有一条路可以走到2,为了避免这种情况,我们必须得从每一个顶点开始遍历,这样才能避免漏掉这种只出不进顶点 于是深度优先遍历得到遍历结果应为...0,然后再遍历它下一层1,3,4------>然后分别遍历1,3,4下一层---->而1,3,4只有1有下一层,则遍历1下一层5,同理最后遍历2 即广度优先遍历得到遍历结果应为:0 1 3 4...5 2 和二叉树层序遍历一样,广度遍历也用到了队列,对于下图而言,先将0放入队首----->然后遍历0并将0从队列中取出,同时将0邻接点1,3,4入队,这样队首就是1----->然后将1出队,并将

1.1K30

浅谈深度优先遍历

一、深度优先概述 ,就是由一些小圆点(称为顶点)和连接这些小圆点直线(称为边)组成。...现在我们从1号顶点开始遍历这个遍历指的是把每一个顶点都访问一次)。...使用深度优先搜索来遍历这个我们将得到以下结果: 使用深度优先搜索来遍历这个具体过程是: 首先从一个未走到过顶点作为起始顶点,比如1号顶点作为起点。...深度优先遍历主要思想是: 首先以一个未被访问过顶点作为起始顶点,沿当前顶点边走到未访问过顶点; 当没有未访问过顶点时,则回到上一个顶点,继续试探别的顶点,直到所有的顶点都被访问过。...二、实现 显而易见,深度优先搜索遍历是沿着某一条分支遍历直到末端,然后回溯,再沿着另一条进行同样遍历,直到所有的顶点都被访问过为止。 那么问题来了,该如何实现这一过程呢?

74690

深度优先遍历和广度优先遍历

深度优先遍历 深度优先遍历类似于树先序遍历,首先通过一个指定节点开始遍历,然后访问第一个邻接点,然后切换到这个节点判断是否是否有邻接点,如果有,判断是否被访问过,如果没有被访问过,则访问这个节点...广度优先遍历类似于数层次遍历,首先选定一个节点,然后把这个节点邻接点全部访问,然后再判断下一个节点是否存在邻接点,同时这个邻接点没有被访问,遍历这个节点所有邻接点,依次循环直到所有节点都被遍历完毕...同时广度遍历也需要一个标志数组来判断节点是否被访问,标志数组原理和深度优先遍历相同。...上图邻接表进行广度优先遍历时候,借助了队列来实现,先访问A然后访问A同时会将BC入队,访问完了A以后会访问B,此时,也会将B邻接点入队,余下节点依次访问,如果节点访问过则不访问,结果为A-B-C-D-E...这样就实现了表广度优先遍历

1.4K00

深度优先搜索遍历

深度优先搜索 深度优先搜索(DFS)每次沿着路径到达不能再前进时,退回到最近岔道口向下继续遍历。换句话说每次路径不可达时,代表一条完整路径形成。...实现过程 连通分量:在无向图中,如果两个顶点可以相互到达(可以通过一定路径间接到达),那么称这个两个顶点连通,如果G中任意两个顶点都连通,则称G为连通, 否则称为非连通,其中极大连通子称为连通分量...可以知道如果遍历整个,就需要对所有连通块(连通分量和强连通分量)进行遍历。...基本思想就是在遍历过程中,将经过顶点设置为已遍历。...实现代码(C++) 基于上一篇构建,我们主要实现一下DFS核心代码 //DFS顶点 void DFS(int v){ //邻接表 cout<<"到达顶点"<<v<<endl;

52320

二种遍历-广度优先遍历深度优先遍历

广度优先遍历 1.树广度优先遍历 这样一个图中,是如何实现广度优先遍历呢,首先,从1遍历完成之后,在去遍历2,3,4,最后遍历5 ,6 , 7  , 8。...;//顶点w入队列 } } 4.知识回顾与总结 ---- 深度优先遍历 1.树深度优先遍历深度优先遍历有点类似于先根遍历 首先遍历 1 2 5 6 3  4 7 8 ,它遍历更趋向于先深层遍历树...2.深度优先遍历 首先我们可以先看一下2,和2相邻是1号结点和6号结点。和2相邻第一个结点是1,所以先访问1,1号结点未被访问。...代码 bool visited [MAX_VERTEX_NUM] ;//访问标记数组 void DFS(Graph G,int v){ //从顶点v出发,深度优先遍历G visit(v )...最终代码 bool visited [MAX_VERTEX_NUM];//访问标记数组 void DFSTraverse(Graph G){ //对G进行深度优先遍历 for( v=0; v

85530

算法练习(17)-广度优先遍历深度优先遍历

一、数据结构及表示法 如上图,由一堆"点"与一堆"边"构成数据结构 ,就称为,其中边上可以有方向(称为有向),也可以无方向(称为无向)。边上还可以有所谓权重值。...,输出为:1 4 3 5 2 7 6 三、深度优先遍历 思路:与广度优先不同,深度优先要沿着某个节点,尽可能向纵深走,而非优先看自身相邻节点,这里要换成Stack,而非Queue,详见下面的代码 /*...set.add(next.to); } } } } 输出:1 4 5 3 7 2 6 带权重深度优先遍历...: /** * 带权重深度优先遍历(菩提树下杨过 yjmyzz.cnblogs.com) * @param g */ void dfs2(Graph g) {...对于无向而言,可以看成是有向特例: 如上图,节点1与节点2构成了1张最简单,从1可以走到2,从2也可以走到1,可以理解为1与2之间,各有一条指向对方边,用代码表示的话,类似下面这样:

63510

优秀题解【遍历——深度优先搜索】

当图中所有顶点都已经访问过时,遍历结束。...(2)以上过程为思想描述过程,但在实际代码描述中,许些地方不同 ①:假设存储结构为邻接表,从顶点v开始访问,其代码遍历过程为 ②:访问该顶点v,把该顶点置为已访问visit[v]=1 ③:让p指向v...第一个边表节点 ④:当p不等于NULL时,循环以下过程 1):如果该边表节点未被访问过,以该节点为顶点继续深度优先遍历 2):1)结束后 p=p->nextarc p等于p下一个边表节点 以下为邻接表结构定义模板...->adjvex); p=p->nextarc;/*下一个边表节点*/ } } 注意事项: 题目输入为邻接矩阵,因为输入一定是无向所以偷个懒把它直接当做邻接表,故可以第...=0&&visit[i]==0)/*如果顶点i是v邻接顶点,且没有被访问,则进行以i为顶点深度优先遍历*/ { DFS_(edges,visit,n,

52020

遍历深度优先搜索(DFS)

深度优先搜索(depth-first search)是对先序遍历(preorder traversal)推广。”深度优先搜索“,顾名思义就是尽可能深搜索一个。...是连通,则通过深度优先搜索可以对它所有顶点进行标记,并且在算法执行过程中,它每一条边至少被查看过一次。...然而,如果一个G不是连通,要标记所有顶点,需对DFS稍作修改:若在第一次尝试所有顶点都被标记过,则是连通,否则,从任意一个未被标记顶点开始,再次执行DFS。...: 若有N个顶点、 E条边,时间复杂度是   用邻接表存储,有O(N+E)   用邻接矩阵存储,有O(N^2) 深度优先搜索相关练习: poj-1979 Red and Black poj-...深度优先生成树及其应用 参考资料: 《数据结构与算法分析-C语言描述》 《算法引论》

1.8K100

算法:深度优先遍历(Depth First Search)

遍历和树遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做遍历(Traverse Graph)。...遍历方法一般有两种,第一种是深度优先遍历(Depth First Search),也有称为深度优先搜索,简称为DFS。...第二种是《广度优先遍历(Breadth  First Search)》,也有称为广度优先搜索,简称为BFS。我们在《堆栈与深度优先搜索》中已经较为详细地讲述了深度优先搜索策略,这里不再赘述。...下面只给出邻接矩阵和邻接表存储方式时深度优先遍历算法代码,没有给出整体可供测试运行代码,其实只需要再写一个创建函数就可以进行整体测试了,可以参考《邻接矩阵创建》和《邻接表创建》 一、如果我们使用是邻接矩阵方式...) 由结果可以看出,因为我们采用了不同存储方式,即使使用是同样深度优先搜索,遍历结果也是不同

1.8K60

【小算法】遍历深度优先(DFS)

谈到算法,操作是避免不了。 而我们一般谈到时,又必定会谈到遍历遍历通常有 2 种,深度优先(DFS) 和广度优先(BFS)。 本篇博文讲解深度优先(DFS)。...表示 有两种表示方式 ? 1. 临接矩阵 ? 其实就是一个权重矩阵,用 1 代表两个结点有连接,0 表示没有连接,这样表示方式通俗易懂,特别适合稠密,也就是大多数结点是亮亮连接情况。...上面是一张,如果要遍历图中所有的结点,又不重复。 可以先选择一个顶点作为根结点,然后沿着路径一条一条遍历下去。...F 也有 3 个临接点B,D,E,按照从最右边顺序遍历,我们选择 E,现在路径是: A--->B--->F--->E ?...A 是从 B 出发,按照算法逻辑,这个时候应该从 C 出发了,但是 C 已经被访问了,所以最终整个遍历就结束了。

91120

遍历

这篇文章中总结一下关于遍历算法,在此之前,我们来看一下什么是: 首先,可以分为有向和无向(这里只讨论无权),像下面这个就是无向,V1 ~ V5 是顶点,而连接两个顶点线就叫边或者专业一点说法叫做...好了,对有了基本认识之后,我们来看一下遍历,所谓遍历,就是根据某种算法来将图中顶点通过连接边全部访问一遍。...在遍历算法方面,我们可以有两种选择:深度优先遍历和广度优先遍历,先来看看深度优先遍历深度优先遍历是利用了栈原理来对顶点进行访问,类似我们之前总结过深度优先搜索,我们总是通过当前顶点第一条出边...好了,我们继续对 V2 进行讨论,我们发现 V3 也没被访问过,于是访问 V3 ,接下来是 V4 ,最后是 V5, 于是这个无向深度优先遍历结果就是 V1 --> V2 --> V3 --> V4...int e[N][N]; // 储存信息邻接矩阵 int book[N]; // 标记顶点是否被访问 // 对第 n 个顶点进行深度优先遍历 void dfs(int n, int sum

79840

【数据结构】遍历--深度优先搜索

题目描述 给出一个邻接矩阵,对进行深度优先搜索,从顶点0开始 以下代码框架仅供参考,同学们可在理解基础上自行设计算法,不强制要求和框架相同 注意:n个顶点编号从0到n-1 代码框架如下:...输入 第一行输入t,表示有t个测试实例 第二行输入n,表示第1个有n个结点 第三行起,每行输入邻接矩阵一行,以此类推输入n行 第i个结点与其他结点如果相连则为1,无连接则为0,数据之间用空格隔开 以此类推输入下一个示例...输出 每行输出一个深度优先搜索结果,结点编号之间用空格隔开 输入样例1 2 4 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 5 0 0 0 1 1 0 0 1...递归实现DFS,还是递归,递归关键在于两个地方,一个是什么时候结束?一个是往哪里递归? 具体到这里,那么就是,这个节点访问过了,那么我就return回去,不然我就对它每一个连接节点都DFS。...当然,为了避免它是一个非连通,我们需要遍历每一个未曾访问节点去DFS,具体看代码就懂了,代码这么短。

14210

遍历(深度优先搜索和广度优先搜索)

遍历----->深度优先搜索和广度优先搜索 一、遍历 与树遍历操作类同,遍历操作定义是,访问途中每个顶点且每个顶点之北访问一次。...遍历方法有两种:一种是深度优先遍历,另一种是广度优先遍历深度优先遍历类似于树先根遍历广度优先遍历类同于树层序遍历。...深度优先遍历算法是遍历深度优先算法,即在所有邻接顶点中,每次都在访问完当前节点后,首先访问当前顶点第一个邻接顶点。 深度优先遍历算法可以设计成递归算法。...对于连通,从初始顶点出发一定存在路径和连通图中其它顶带相连,所以对于连通来说,从初始顶点出发一定可以遍历。连通深度优先遍历递归算法如下。 (1)访问顶点v并标记顶点v已被访问。...深度优先搜索顶点访问顺序:A->B->D->C->E 三、广度优先遍历 广度优先遍历算法是一个分层搜索过程。

85630

详解第二篇:遍历(广度优先+深度优先)

遍历 所谓遍历: 即从图中任一顶点出发,对图中所有顶点访问一次且只访问一次。...举个栗子: 这就是对一个(无向广度优先遍历,红色数字就是结点遍历顺序。...深度优先遍历(一条道走到黑) 那深度优先遍历又是什么呢? 其实我们之前学二叉树前序遍历就是一个深度优先遍历,就是先往深了去走,直到走不通了,再往回回溯。...思路分析 那深度优先遍历我们来看一下: 大家看这个。...对于连通,不论是广度优先遍历还是深度优先遍历,我们上面的代码肯定都是没问题,肯定能遍历完所有的顶点; 但是如果给我们是一个非连通呢?比如: 这样

28410
领券