java 连通图遍历 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

Kasaraju算法--强连通图遍历

显然这也是一个图，只不过是由三个子图组成而已，但这并非一个连通图。这三个子图叫做这个图的连通分量，连通分量的内部归根还是一个连通图。...如果有向图的各个强连通分量中的元素个数相仿，那么，它们内部分别进行遍历的时间量级别是相等的，但实际情况是，这种情况很少发生。一般从一个强连通分量到另一个强连通分量。...所不同的是，这次遍历的起始点从子图1开始。多强连通分量的有向图 ? 再来看一下这个多子图的强连通图，如果像上图所示，从子图1开始，就会像上文提到的那样，遍历到节点2，会出现多个去向的问题。...此时，遍历的起点还是从子图1开始，由于子图1没有出路，就不会出现上面所说的问题。再遍历完子图1后，继续遍历子图2、子图3。而子图2、子图3的遍历都是在强连通分量内部实现的。...for u in G[s]: if u in S:continue rec_dfs(G,u,S) return S 在强连通图内遍历 #遍历有向图的强连通分量 def

2.6K2 0

5.3.3 图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。...对于无向图来说，如果无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中所有顶点；如果无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点无法通过这次遍历访问...故而在BFSTraverse()和DFSTraverse()中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图中所有顶点。...对于无向图，上述两个函数调用BFS(G,i)或DFS(G,i)的次数等于图中的连通分量树；而对于有向图，则不是这样没因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量...，非强连通分量一次调用BFS(G,i)或DFS(G,i)无法访问到该连通分量的所有顶点。

7422 0

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

是的

没有找到

图的遍历(Java语言)

图有两种遍历方式：深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。...若G是连通图，则一次就能搜索完所有节点；否则在图G中另选一个尚未访问的顶点作为新出发点继续上述的遍历过程，直至G中所有顶点均已被访问为止。...list.addLast(w); //把该顶点的邻接点加入链表的链尾 } } } } 创建一个图并使用两种遍历方式遍历...： Graph类： package com.graph; import java.util.*; public class Graph { ArrayList vertexList...; //存储顶点的集合 int[][] edges; //存储图对应的邻接矩阵 int numEdges; //表示边的条数 boolean[] marked; //标记是否被遍历过

6862 0

连通图【并查集】

描述给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。输入描述：每组数据的第一行是两个整数 n 和 m（0图的顶点数目，m 表示图中边的数目。...输出描述：对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。...3 2 1 2 2 3 0 0 输出： NO YES 并查集 Initial() //初始化 Union() //合并，路径压缩 Find() //查询，找爹用途:判断连通图...、求连通分量 #include using namespace std; int n,m; int father[1010]; int height[1010]; void Initial...int compenent =0; for(int i=1;i<=n;i++){ if(Find(i) == i)compenent++;//连通分量个数

3614 0

图的连通分量个数

上面有向图的连通分量个数为2 二、分析：我们给图的每个结点设置一个访问标志，用visited[]数组来表示，0代表未访问，1代表已经访问然后我们求从每个节点开始的深度优先遍历序列，每访问到一个结点，...若当前结点已经被访问过(也就是visited[]数组中对应位置为1)，那这个结点就不用再深度优先遍历，只有visited[]对应位置为0时才在当前结点进行深度优先遍历，深度优先遍历的次数就是该图的连通分量个数...//这里假设图的顶点信息为字母类型 //连通图的深度优先遍历函数 void DepthFSearch(AdjMGraph G, int v, int visited[], void Visit(DataType...（返回值为连通分量的个数） int DepthFirstSearch(AdjMGraph G, void Visit(DataType item)) //非连通图G的访问操作为Visit()的深度优先遍历...（返回值为连通分量的个数） int DepthFirstSearch(AdjMGraph G, void Visit(DataType item)) //非连通图G的访问操作为Visit()的深度优先遍历

7193 0

图的连通性计算

图片判断无向图的连通性可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。深度优先搜索（DFS）：算法步骤：选择一个顶点作为起始顶点，标记为已访问。...判断是否有未被访问过的顶点，若有则表示图不是连通的，否则表示图是连通的。...结果： 1------2------7 | | / | | / 5------3---6 | | 4所有顶点都被访问过，因此该无向图是连通的...在有向图中找到所有的强连通分量：强连通分量（Strongly Connected Component，SCC）指的是有向图中的一个最大子图，该子图内的任意两个顶点均可达。...要找到所有的强连通分量，可以使用Tarjan算法。Tarjan算法步骤：对有向图进行深度优先搜索（DFS）。在搜索的过程中，记录每个顶点的访问次序（dfs序）和能够到达的最小次序（low值）。

3809 0

【数据结构】图—图的连通分量

题目描述输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。...输入测试次数t 每组测试数据格式如下：第一行：顶点数顶点信息第二行：边数第三行开始，每行一条边信息输出每组测试数据输出，顶点信息和邻接矩阵信息输出图的连通分量个数，具体输出格式见样例。...0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 3 思路分析建立邻接矩阵，用DFS的方式遍历图...，如果只需要从一个节点出发就能遍历所有节点，那么只有一个联通分量，如果需要从多个节点出发才能遍历完所有节点，那么有多个联通分量。...因此，解决方式就是，从所有节点出发DFS，每遍历一个节点就标记下来，即不会遍历已遍历的节点，那么联通分量的数目就是需要DFS节点的数目。

2713 0

图, 图的遍历

,我们日常的生活大多就是不规则的,不会像树一样那样结构紧密,我们日常生活更多接触就是图.图的表示图的表示一般有两种方式,一种是二维数组,例如在 (x, y) 的点表示 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

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

在讲深度优先遍历之前，先来回顾一下图这种数据结构。 1. 是什么？图，也是一种数据结构，其节点可以具有零个或者多个相邻元素，两个节点之间的连接称为边，节点也称为顶点，图表示的是多对多的关系。 ?...图的表示方式：邻接矩阵：也就是用二维数组表示。假如总共有n个顶点，那么就需要一个 n*n 的二维数组。两个顶点之间如果是连通的就用1表示，反之用0表示。...比如顶点0可以和顶点2，3，6连通，那么数组第一个位置存放的就是2 ---> 3 ---> 6这条链表。 4. 无向图的创建(邻接矩阵)：开篇所示的无向图，怎么用邻接矩阵代码实现呢？...* @param vertex1 顶点1 * @param vertex2 顶点2 * @param isConnected 顶点1和顶点2是否连通，0:未连通 1:已连通...无向图的遍历： (1). 遍历分类：图的遍历分为两种：深度优先：depth first search，简称DFS。

1.4K2 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,...UnDirectionGraph { private List vertexList; // 存放顶点 private int[][] edges; // 邻接矩阵，存放图的边...vertexCount][vertexCount]; this.isVisited = new boolean[vertexCount]; } /** * 构建无向图...顶点1 * @param vertex2 * 顶点2 * @param isConnected * 顶点1和顶点2是否连通...，0:未连通 1:已连通 */ public void buildGraph(String vertex1, String vertex2, int isConnected) {

1.4K1 0

图的遍历

这篇文章中总结一下关于图的遍历算法，在此之前，我们来看一下什么是图：首先，图可以分为有向图和无向图（这里只讨论无权图），像下面这个图就是无向图，V1 ~ V5 是图的顶点，而连接图的两个顶点的线就叫边或者专业一点的说法叫做...好了，对图有了基本的认识之后，我们来看一下图的遍历，所谓图的遍历，就是根据某种算法来将图中的顶点通过连接的边全部访问一遍。...在遍历的算法方面，我们可以有两种选择：深度优先遍历和广度优先遍历，先来看看深度优先遍历：深度优先遍历是利用了栈的原理来对图的顶点进行访问，类似我们之前总结过的深度优先搜索，我们总是通过当前顶点的第一条出边...下面给出广度优先遍历的伪代码： // 宽度优先遍历，n 为图的顶点个数 void bfs(int n) { que.push(0); // 将 V1 顶点入队 int s; while...图的遍历算法是图的基础算法，也是在很多其他图的算法中经常用得到的算法思想，比如图中两个顶点的最短路，图的最小生成树算法等等。好了。如果博客中有什么不正确的地方，还请多多指点。

8264 0

06-图1 列出连通集

题目很简单，我没用教材上给的图结构，不然太麻烦了，这是个无加全的无向图。。。...bfs(i); cout << " }" << endl;; } } } 废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权转载请注明原文链接：06-图1...列出连通集

3373 0

YbtOJ 884「线性基」连通的图

YbtOJ 884「线性基」连通的图题目链接：YbtOJ #884 小 A 有一张 n 个点，n+k-1 条边的无向连通图。...他想知道有多少种方案删去图中若干条边（包括一条边都不删），满足剩下的图依然连通。由于方案数可能很大，你只需输出答案对 998244353 取模的结果。...要实现这一过程，只需利用树上差分给每条非树边覆盖的树边打上异或标记，最后 dfs 遍历一遍做个子树异或和即可求出所有树边的权值。...发现一张图不连通，充要于 **删去的边集中存在一个子集异或和为 0**。要判断加入一个数后是否存在子集异或和为 0，只要判断能否插入线性基即可。

7403 0

06-图1 列出连通集

题目来源：http://pta.patest.cn/pta/test/18/exam/4/question/624 给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。...输入格式: 输入第1行给出2个整数N(0图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。...输出格式: 按照"{ v1 v2 ... vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

1.2K9 0

ccf 高速公路(连通子图)

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。...非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。...{5},{6}也分别是两个强连通分量。 ? 直接根据定义，用双向遍历取交集的方法求强连通分量，时间复杂度为O(N^2+M)。...从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。 ?...求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。

8443 0

无向图的连通分量

对于一个图而言，它的极大连通子图就是它的连通分量。如果包含G’的图只有G，那么G’就是G的极大连通子图。连通分量可以通过深度优先搜索或者广度优先搜索来寻找。...题目：ALDS1_11_D 方法就是以未访问的顶点为起点来进行搜索，每次开始从头进行搜索，搜索到的节点都属于同一个极大连通子图，也就是整个图的一个连通分量。

8473 0

C++图论之强连通图

连通性什么是连通性？连通，字面而言，类似于自来水管道中的水流，如果水能从某一个地点畅通流到另一个地点，说明两点之间是连通的。也说明水管具有连通性，图中即如此。无向图和有向图的连通概念稍有差异。...无向图连通性如果任意两点间存在路径，称此图具有连通性，如下的图结构具有连通性。...如上图，有一个强连通分量，也称此图为强连通性有向图。如下图所示有向图结构，有向图本身不具有强连通性，但存在子图具有强连通性，则称子图即为原图的强连通分量。当然，具有强连通性的子图可能不只一个。...getConn(int u) { ++cnt; //前序位置记录节点的时间戳和回溯值 dfn[u]=low[u]=cnt; //入栈 s.push(u); inSta[u]=true; //遍历子节点...更新 low 为祖先节点的时间戳 low[u]=min(low[u],dfn[v]); } //后序遍历位置 if(dfn[u]==low[u]) { //如果时间戳和回溯值相同，找到一条强连通分量

2141 0

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

HashMap的遍历可以用entrySet()；keySet()可以获得key,根据key可以用get(key)获取value ；values()可以获取map里所有的值，返回的是一个Collection

9893 0

图的深度遍历和广度遍历

理论部分图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点0开始对整幅图进行遍历的话,两种遍历方式的思想如下: 1....之前我们是直接就默认从0开始进行往下遍历了,但是从0开始遍历没有一条路可以走到2,为了避免这种情况,我们必须得从每一个顶点开始遍历,这样才能避免漏掉这种只出不进的顶点于是深度优先遍历得到的遍历结果应为...:0 1 5 4 3 2 2.广度优先遍历(broadFirstSearch—BFS) 广度遍历我觉得理解起来更简单,就是一层一层的进行遍历,比如说以0顶点开始,0往下指向1,3,4,遍历的时候就先遍历...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

7.3 图的遍历

01 遍历 1、和树的遍历类似，从图中某一项点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程叫做图的遍历。 2、图的遍历算法是求解图的连通性问题，拓扑排序和求关键路径等算法的基础。...3、图的遍历比树的遍历要复杂的多，因为图的任一顶点都可能和其余的顶点相邻接。 4、图中访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。...5、深度优先搜索：遍历类似于树的先根遍历，是树的先根遍历的推广。 6、广度优先搜索：遍历类似于树的按层次遍历的过程。如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

37932 29

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭