一些术语 深度： 从根节点到指定节点的边的个数 高度： 从指定节点到叶子节点的边的个数 树的高度： 指的是根节点的高度，也即根节点到最深叶子节点的边的个数。...树的遍历 遍历指的是访问整颗树的所有节点，由于树是一个非线性的数据结构，所以这儿没有唯一的遍历方式，大体上可分为两种遍历类型： （一） 深度优先遍历 深度优先遍历又分为三种策略： （1）前序遍历 （先根节点...对于有向图来说，一笔画不仅指遍历所有边，而且要遵循正确的方向。严谨地说，一个连通有向图 G有欧拉路径，指存在一个顶点，从它出发，沿着有向边的方向，可以不重复地遍历图中所有的边。...有向图的欧拉回路则是指可以从某一顶点开始，沿有向边的方向不重复地遍历所有边，然后回到原来出发的顶点。...定理不理解无所谓，我们看看如何将书遍历问题转化成了图遍历问题，从而可以快速写出上面的三种深度遍历的结果。 我们将上面的树遍历，转化为使用欧拉回路进行对二叉树的散步，其中每条边都是一道墙，你不能横穿。
因为图中的每一条边都是由两个节点相连而成的，因此图可以表示任何二元关系 在我们生活中，每天使用的微信等社交软件，我们的好友关系网也能被形象成一种图结构，如图，图能表示各种丰富的关系结构 在 JS 中没有图结构...，则图是连通的 有向图 图中节点之间边线是单向的 无向图 图中节点之间的边线是双向的，或者没有方向，称为无向图 三、如何表示一个图？...邻接矩阵 我们可以采用一个二维数组来确定顶点间的连接关系，如果 A 能连接到 B 那么我们就置为 1 ，如果连不到就是 0 如图 A 连接 B 节点，因此 第一行第二列为 1，表示 A 连接 B 2....深度优先遍历（DFS） 尽可能深的搜索图的分支，类似于树的前序遍历 先访问根节点 对根节点的没访问过的相邻节点挨个进行深度优先遍历 代码实现 // 记录访问过的节点 const visited = new...广度优先遍历（BFS） 先访问离根节点最近的节点，类似于树的层序遍历 遍历的方法 新建一个队列，把根节点入队并访问 把对头没有访问过的相邻节点入队 重复，直至队列为空 代码实现 // 广度优先遍历 const
，表示自己是自己的父节点（或者说每个元素都是根节点） 接下来，遍历前面准备好的HashMap，每个key对应的都是一个List，将这个list中的所有元素在并查集中合并，以key等于2为例，value...，6指向自己的父节点4 第二个key是3，value中的数字是6和15，将6和15合并的效果如下图，蓝色是改过的地方，值等于6，表示数字15的父节点改成了6，为了便于理解，逻辑图也同步改动了，15...i; } // 用递归的方式寻找，并且将整个路径上所有长辈节点的父节点都改成根节点， // 例如1的父节点是2，2的父节点是3，3的父节点是4，4就是根节点...} // 用递归的方式寻找，并且将整个路径上所有长辈节点的父节点都改成根节点， // 例如1的父节点是2，2的父节点是3，3的父节点是4，4就是根节点，在这次查找后，1...恍然大悟：我们无需对各个质因数之间做什么，只要将每个质因数对应的数字合并即可，有的数字本来就属于多个质因数，所有跨质因数的连接都是因为这个特点而存在！
在上一篇博客判断有向图是否有圈中从递归的角度简单感性的介绍了如何修改深度优先搜索来判断一个有向图是否有圈。...(上图的无向图是双连通的) 如果一个图不是双连通的，也就是说存在一些顶点，将其删除后图将不在连通，我们把那些顶点称为割点或者关节点(articulation point)。...由(3)可知我们必须先求出v的所有孩子的最小编号，故需要用后序遍历计算low(v)。 求出所有割点： 第一类割点：根节点是割点当且仅当他有两个或两个以上的孩子。...因为如果根节点有多个孩子时，删除根使得其他的节点分布在不同的子树上，而每一棵子树就对应一个连通图，所以整个图就不连通了；而但根只有一个孩子时，删除它还是只有一棵子树。...(注意：节点v一定不是叶节点因为删除叶节点还是一棵树，而根节点之所有单独拿出来是因为任何情况下若v为根节点，一定满足low(w) >= num(v)，因为num(v)是最小先序编号)。
示例场景 假设我们有一个有向图，其中结点u是图中的一个特殊结点，其所有出边指向的结点都已经在之前的DFS过程中被访问过，而所有指向u的入边（如果有的话）的源结点在当前DFS的上下文中不被进一步探索（可能是因为它们已经被访问过...节点u是起始节点，并且没有任何入边。在这种情况下，深度优先搜索将从节点u开始，并遍历所有可能的路径，直到找到目标节点或遍历完所有可达节点。 2. 节点u的所有入边都被删除或者被标记为不可达。...然后，我们从顶点2开始执行深度优先搜索。请注意，即使节点2同时具有入边和出边，它仍然可以成为深度优先树中的唯一节点，只要它的所有入边都被删除或标记为不可达。...g.DFS(1) } 在这个例子中，我们创建了一个有向图，包含5个结点，并添加了一些边。我们从结点1开始进行深度优先搜索。这将确保只有从结点1可达的结点被访问，形成以结点1为根的深度优先树。...这个代码示例展示了如何使用DFS遍历有向图，并在遍历过程中记录访问过的节点。
本章节开始的所有图和树，如果没有额外声明，都是采用邻接表存储的，点的下标为 1 \sim n ，无向边存储以两条有向边等价存储 树与图的深度优先遍历 树的深度优先遍历 深度优先遍历，就是在每个点...，我们可以统计许多关于树和图的信息 图的连通块划分 树的深度优先遍历，每从 x 开始一次遍历，就会访问 x 能够到达的所有点和边 因此通过多次深度优先遍历，可以划分出一张无向图中的各个连通分块...，我们已知 “以它为根的子树” 大小为 1 若结点 x 有 k 个子节点 y_1, \cdots, y_k ，并且以 y_1, \cdots, y_k 为根的子树大小分别是 size[...，因此对于一个结点的两棵子树，他们的子节点不可能有交集。...y 出发能够到达的点的并集，再加上 x 自身 所有在计算所有后继结点的 f 值之后，就可以计算出该点的 f 值 这启发我们用拓扑排序算法求出一个拓扑序，然后按照拓扑序的逆序进行计算（因为在拓扑序中
本文收录于 www.cswiki.top 可达性分析可以分成两个阶段 根节点枚举 从根节点开始遍历对象图 前文 可达性分析深度剖析：安全点和安全区域 提到过，在可达性分析中，第一阶段 ”根节点枚举“...是必须 STW 的，不然如果分析过程中用户进程还在运行，就可能会导致根节点集合的对象引用关系不断变化，这样可达性分析结果的准确性显然也就无法保证了；而第二阶段 ”从根节点开始遍历对象图“，如果不进行 STW...，这是理所当然的事情 也就是说，“从根节点开始遍历对象图” 阶段的停顿时间随着堆容量的增长而增加。...灰色：表示对象已经被垃圾收集器访问过，但这个对象上至少存在一个引用还没有被扫描过 所以对象图遍历的过程，其实就是由灰色从黑向白推进的过程，灰色是黑和白的分界线。...对象消失是一个很致命的问题，程序肯定会因此发生错误，所以 “对象图遍历” 这个阶段最好是进行 STW 的，但是这个阶段的时间又很长，所以我们需要想出一些办法来解决对象消失问题，使得在遍历对象图的过程中不用进行
首先我们要先对整棵树dfs一遍，求出他们的dfs序，然后对每个节点以dfs序为关键字从小到大排序 同时维护一个栈，表示从根到栈顶元素这条链 假设当前要加入的节点为\(p\)，栈顶元素为\(x = s[top...]\)，\(lca\)为他们的最近公共祖先 因为我们是按照dfs序遍历，因此\(lca\)不可能是\(p\) 那么现在会有两种情况 \(lca\)是\(x\)，直接将\(p\)入栈。...\(x,p\)分别位于\(lca\)的两棵子树中，此时\(x\)这棵子树已经遍历完毕，（如果没有，即x的子树中还有一个未加入的点y，但是dfn[y]访问y）， 我们需要对其进行构建...MatrixTree定理 给定一张无向图，求出其生成树的个数 记\(A\)为无向图的度数矩阵(A[i][i]表示\(i\)号点的度数)，\(D\)为无向图的邻接矩阵\(D[i][j]\)表示\(i\)与...\(j\)的边数 记\(G = A - D\)，那么图的所有不同的生成树等于任意一个\(n - 1\)阶主子式的行列式的绝对值 求行列式可以直接高斯消元后把主对角线上的所有元素乘起来复杂度\(O(n^3
= rootY { uf.parent[rootX] = rootY // 将一个集合的根节点指向另一个集合的根节点 } } // 判断两个顶点是否在同一连通分量中 func...首先，我们初始化一个空的结果列表和一个标记数组来记录每个节点是否被访问过。然后，我们对每个未访问过的节点执行深度优先搜索，并将找到的连通分量添加到结果列表中。...每个连通分量是一个节点列表，表示这些节点都在同一个连通分量中。 360智脑： 您提到的 CONNECTED-COMPONENTS 算法可能是指图论中的一个算法，用于查找无向图中的所有连通分量。...在处理图的连通分量时，我们初始化一个并查集，其中每个顶点都是一个独立的集合。然后，我们遍历每条边，对于每条边上的两个顶点，如果它们不在同一个集合中，我们就将这两个集合合并。...通过深度优先搜索 (DFS) 来遍历图，当访问到某个顶点时，将其标记为已访问，并递归地继续遍历与该顶点相邻的未访问顶点。最后，根据是否访问到目标顶点来判断它们是否在同一个连通分量中。
有向图是它的使用范围，我们只能使用在有向图当中。对于无向图其实也存在强连通分量这个概念，但由于无向图的连通性非常强，只需要用一个集合维护就可以知道连通的情况，所以也没有必要引入一些算法。...算法原理 Kosaraju算法的原理非常简单，简单到只有三个步骤： 我们通过后序遍历的方式遍历整个有向图，并且维护每个点的出栈顺序 我们将有向图反向，根据出栈顺序从大到小再次遍历反向图 对于点u来说，在遍历反向图时所有能够到达的...下面我们来详细阐述一下细节，首先后序遍历和维护出栈顺序是一码事。也就是在递归的过程当中当我们遍历完了u这个节点所有连通的点之后，再把u加入序列。...还有一种可能是u不能连通到v，说明图被分割成了多个部分。对于第二种情况我们先不考虑，因为这时候u和v一定不在一个连通分量里。对于第一种情况，u是v的上游，说明u可以连通到v。...这时候，我们将图反向，如果我们从u还可以访问到v，那说明了什么？很明显，说明了在正向图当中v也有一条路径连向u，不然反向之后u怎么连通到v呢？所以，u和v显然是一个强连通分量当中的一个部分。
6,7在自己的连通通道上可以互通。 如何检查图结构的连通性和计算连通分量？ 笨拙的方案是使用深度或广度搜索算法。原理较简单，一次搜索完毕后，搜索到的节点必是在一个连通分量上。...否则，可以使用轻巧、快速的并查集数据结构来检查。 有向图的连通性 无论是在有向图或无向图中，都不可能改变连通这个概念。...我们已知在无向图中计算连通分量的算法。那么在有向图中如何计算机强连通分量？ 算法界有一句名言：没有暴力算法不能解决的问题。有向图中查找强连通子量，同样可以使用深度搜索或广度搜索。...因为，2节点被访问过，现又以4号节点的子节点身份重新被访问，会想到是不是碰到了祖先，或者说遇到了同一个强连通分量上的节点？ 答案是，不能这么简单的认为？因为这种情况有可能是回边也有可能是横叉边。...难道说4号节点和1号节点在同一个强连通分量上吗？4->2是回边，而1->4是横叉边。 那么应该如何做出正确判断？继续回到我们的图结构上来讨论怎么正确得到强连通分量。
过程中改变节点颜色，并未直接展示如何构建或遍历图以及生成颜色网格。...• 白色到黑色：不可能，因为节点只有在访问所有邻接点后才会变黑。 • 灰色到白色：可能，类型为“发现边”。 • 灰色到灰色：不可能，因为在DFS中不会有指向正在访问的节点的回边。...对于有向图的DFS，我们可以分析如下： 有向图的DFS网格 • 白色 -> 白色：不可能，因为DFS开始于一个白色节点，但不会从一个未访问节点指向另一个未访问节点（除非是递归的子树，但这种情况下，子节点在被访问时会变成灰色...在无向图的DFS中，我们可以分析如下： • 白色 -> 白色：不可能，因为DFS不会从一个未访问节点指向另一个未访问节点，除非是递归的子树。...对于有向图，我们可以创建一个 3\times3 的网格，其中行和列分别代表白色、灰色和黑色的节点。在深度优先搜索（DFS）中，从一个节点到另一个节点的边取决于我们如何遍历图。
数据结构 并查集的重要思想在于：用集合中的一个元素代表集合。 如果把集合比喻成帮派，而代表元素则是帮主，接下来我们利用这个比喻，看看并查集是如何运作的。 最开始，所有大侠各自为战。...综上所述，并查集是一个树状的结构，要寻找集合的代表元素，只需要一层一层往上访问父节点（图中箭头所指的圆），直达树的**根节点（图中橙色的圆）**即可。根节点的父节点是它自己。...我们可以直接把它画成一棵树： 数据结构核心代码 Init 假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的...：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。...多余的边 树可以看成是一个连通且 无环 的 无向 图。 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。
基本概念 图是有限集V和E的有序对，即G=(V,E)。其中V的元素称为顶点（也称为节点或点），E的元素称为边（也称为弧或线）。...一个图不可能包含自连边，即(i,i)形式的边。自连边也叫做环。 在图的一些应用中，我们可能要为每条边赋予一个表示成本的值。我们称之为权。这时的图称为加权有向图和加权无向图。...所有发言人都只会说英语，而每一个与会人员所懂得的语言是L1，L2,……，Ln中的一种。翻译小组合一在有英语和其他语言之间互译。现在是任务是如何使翻译小组的人数最少。...我们需要找到能够覆盖所有语言顶点的最小翻译人员顶点集。 如下图，对这个问题进行描述： ? 特性 在一个无向图中，与一个顶点i相关联的边数称为该顶点的度。 在无向图中，顶点的度之和是边数的2倍。...对于每一个n(n>=2)，都存在一个恰有n条边的强连通有向图。 每一个具有n（n>=2）个顶点的强连通有向图，至少包含n条边
先通过一道特别经典的题目来回顾下DFS算法。 T1 无向图的遍历 对下图的各个节点遍历，且不重复 解法如下。...先来实现两个简单的题目。 T4.二叉树的层次遍历（从根节点开始） 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。...分析:要想找出所有被x包围的o很难，但是我们可以逆向思维:找到所有在四边或者与四边相连的o，是则暂时改为为A，最后将所有A恢复成O,将所有剩下的O改X。...那么问题就被简化了，因为我们可以通过深度优先搜索或者广度优先搜索来找到与四周相连接的o。...如何进行遍历搜索呢?可以利用i,j的增减实现，具体的实现过程参考下面代码。
每个Broker节点，在启动时，都会遍历NameServer列表，与每个NameServer建立长连接，注册自己的信息，之后定时上报。...分区容错(Partiton Tolerance)：对于分布式架构，网络条件不可控，出现网络分区是不可避免的，只要保证部分NameServer节点网络可达，就可以获取到数据。...以下源码截图展示了这个过程： 然而定时拉取，还不能解决所有的问题。因为客户端默认是每隔30秒会定时请求NameServer并获取最新的路由表，意味着客户端获取路由信息总是会有30秒的延时。...4 生产者重试机制 在讲解生产者重试机制之前，我们必须先对三种消息类型：普通消息、普通有序消息、严格有序消息进行介绍。因为RocketMQ客户端的生产者重试机制，只会普通消息有作用。...这里主要说明：对于普通有序消息，在异常情况下，如何经历短暂无序之后再恢复有序。
相同编号之间的节点编号为以此编号为根节点的子树上的所有节点编号。 [2,8,8,5,5,2]表示编号 2为根节点的子树中所有节点为8,5。...Tarjan算法求解割点的核心理念： 在深度优先遍历算法访问到k点时，此时图会被k点分割成已经被访问过的点和没有被访问过的点。...如果k点是割点，则没有被访问过的点中至少会有一个点在不经过k点的情况下，是无论如何再也回不到已访问过的点了。则可证明k点是割点。 下图是深度优先遍历访问到2号顶点的时候。...这个道理是很好理解的，说明子节点想重回树的根节点是无法绕开父节点。 3.2 割边 定义：即在一个无向连通图中，如果删除某条边后，图不再连通。如下图删除2-5和5-6后，图不再具有连通性。...，每次遍历完一个子节点时，返回到此节点记录，得到的 2 ∗ N − 1 长的序列； 欧拉序和DFS序的区别，前者在每一个子节点访问后都要记录自己，后者只需要访问完所有子节点后再记录一次。
是的，这两段就是 Tarjan 算法求割点的核心思路，我们通过图来继续学习一下： ? 首先我们要知道，上图中的箭头表示 DFS 访问的顺序（不是有向图）。...另外我们要考虑一个边界情况，就是 DFS 的根节点（一般情况下都是下标为 0 的节点），因为根节点没有祖先顶点。...另外，根节点是不是割点也是很好判断，如果我们从根节点出发，一次 DFS 就能访问到所有的节点，那么根节点就不是割点。...以上分析我们得到两个结论： 当该点是根节点，只要子节点数目大于 1，它就是割点； 如果不是根节点，只要节点的子节点不到达祖先顶点，它就是割点； Tarjan 中的一些概念 Tarjan 算法是基于对图的...另外，在 Tarjan 算法中，如果一次 Tarjan 遍历后，DFN[u] = LOW[u]时，以 u 为根的搜索子树上所有节点是一个强连通分量。
所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。...这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。...我们来给出它们的详细定义，然后举例看看它们的应用。 先序遍历 ：在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树。...我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树。...，最后访问根节点。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
云直播
对象存储
实时音视频
