图的深度遍历 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

图的遍历 --- 深度优先遍历

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

1.4K2 0

hashmap遍历方式_图的深度遍历

大家好，又见面了，我是你们的朋友全栈君。...HashMap的遍历可以用entrySet()；keySet()可以获得key,根据key可以用get(key)获取value ；values()可以获取map里所有的值，返回的是一个Collection...如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。

9893 0

您找到你想要的搜索结果了吗？

是的

没有找到

图的深度遍历和广度遍历

理论部分图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点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.1K3 0

浅谈图的深度优先遍历

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

7719 0

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

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

1.4K0 0

深度优先搜索遍历图

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

5382 0

图的二种遍历-广度优先遍历和深度优先遍历

图的广度优先遍历 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

9103 0

算法练习(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之间，各有一条指向对方的边，用代码表示的话，类似下面这样：

6961 0

图的存储及遍历深度遍历和广度遍历 C++代码实现

大家好，又见面了，我是全栈君 /*图的存储及遍历*/ #include using namespace std; //--------------------------...--------- //邻接矩阵的存储及深度和广度遍历 //----------------------------------- /*邻接矩阵的类型定义*/ #define MAX...*******************无向图的深度优先遍历************************/ int visited[MAX_VERTEX_NUM]; void DF_AM...visited[i]) DF_AM(G,i); } } /*********************无向图的广度优先遍历*...firstedge; G.vexs[i].firstedge=p;//采用头插法 } } /*********************有向图的深度优先遍历

3952 0

图的遍历之深度优先搜索（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.9K10 0

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

当图中所有顶点都已经访问过时，遍历结束。...(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,

5932 0

邻接图的深度广度优先遍历

邻接图的优点就是，现用现申请，空间存储很灵活，并且需要的空间也很小。我们在做复杂网络时，通常也是用这种方法。缺点是不适合并行化，因为cuda只支持连续地址空间的拷贝。...firstNode; }vertexNode,List[NUM]; typedef struct Graph{ List list; int numver,numedges; }Graph; 深度优先遍历...visited[i]) DFS(g,i); } 广度优先遍历 void BFSTraverse(Graph *g){ int i; edgeNode *p;...} p = p->next; } } } } } 示例图...list[i].firstNode = NULL; 79 } 80 g->numver = NUM; 81 g->numedges = 0; 82 //添加顶点0的边

6689 0

算法：图的深度优先遍历（Depth First Search)

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

2.5K6 0

图, 图的遍历

.图图对于我们日常的生活来说其实更加普遍,我们日常的生活大多就是不规则的,不会像树一样那样结构紧密,我们日常生活更多接触就是图.图的表示图的表示一般有两种方式,一种是二维数组,例如在 (x, y) 的点表示...因此有了第二种表示方式邻接表.邻接表是数组和链表的组合, 有点类似 hashmap, 具体见下图我们可以吧所有点都当做数组的一项.链表内容表示这个节点有连接的其他节点,节点中可以存放相关的权重值.图的遍历图的遍历可以分为两种...,一种是深度遍历,一种是广度遍历,也就是常说的深搜和广搜.我们首先用邻接表实现图,另外为了简单我们使用无向图表示.class Graph { private: int v; //表示顶点的数目...int src, int dest){ graph[src].push_back(dest); graph[dest].push_back(src); }};接下来就是图的遍历...,分别是深度遍历和广度遍历.广搜广搜的跟树的层序遍历基本一致,就是需要使用另外一个数据用来标记是否访问过.void bfs(int start){ vector visited(v,

310 0

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

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

9592 0

图的遍历

这篇文章中总结一下关于图的遍历算法，在此之前，我们来看一下什么是图：首先，图可以分为有向图和无向图（这里只讨论无权图），像下面这个图就是无向图，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

8264 0

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

题目描述给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点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，具体看代码就懂了，代码这么短。

1621 0

图的遍历 --- 广度优先遍历

广度优先遍历思路：还是以之前深度优先遍历的图为例，如下： A B C D E F G H A[0, 1, 0, 0, 0, 1, 0, 1] B[1, 0, 1, 0, 0, 0,...0, 1, 0] F[1, 0, 0, 0, 0, 0, 1, 0] G[0, 1, 0, 0, 1, 1, 0, 0] H[1, 0, 0, 1, 0, 0, 0, 0] 所谓广度优先，就类似二叉树的层序遍历...，最终的遍历结果是： A -- B -- F -- H -- C -- G -- D -- E 2....; // 存放顶点 private int[][] edges; // 邻接矩阵，存放图的边 private boolean[] isVisited; // 顶点是否被访问 /...vertexCount][vertexCount]; this.isVisited = new boolean[vertexCount]; } /** * 构建无向图

1.4K1 0

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

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

9723 1

PTA 邻接矩阵存储图的深度优先遍历

6-1 邻接矩阵存储图的深度优先遍历（20 分）试实现邻接矩阵存储图的深度优先遍历。...函数接口定义： void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ); 其中MGraph是邻接矩阵存储的图，定义如下： typedef struct...*/ WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */ }; typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型...*/ 函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，遍历时用裁判定义的函数Visit访问每个顶点。...*/ WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */ }; typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型

1.6K6 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭