图结构是数据元素呈多对多关系，就是任意两个元素存在这样的关系。如果用一个公式来表示就是由顶点集合和顶点之间的关系集合组成的一种数据结构。
在 《Tarjan 算法的思路》中我们已经给出了 Tarjan 算法中的比较重要的几个元素，我们在这里重新复习一下：
定义union-find算法API： public class UF{ UF(int N) 初始化N个触点 void union(int p,int q) 在p和q之间建立连接 int find(int p) p所在的分量的标识符 boolean connected(int p,int q) p和q同在一个分量中则为
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向图有n(n-1)/2条边。
图是一种在计算机科学中广泛应用的数据结构，它能够模拟各种实际问题，并提供了丰富的算法和技术来解决这些问题。本篇博客将深入探讨图数据结构，从基础概念到高级应用，为读者提供全面的图算法知识。
图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
在开始文章之前先跟大家同步一个坏消息，大概是由于整理了PDF分享的原因，遭到leetcode上海官方投诉侵权（虽然我一直用的都是海外版）。我个人觉得这种行为非常霸道，决定以后不再更新leetcode相关的文章，并且之前的文章也进行了删除。对于想要看这部分文章的朋友，先说声非常抱歉。周末我会寻找其他平台的算法问题作为替代，带来不便，再次抱歉。
说到以Tarjan命名的算法，我们经常提到的有3个，其中就包括本文所介绍的求强连通分量的Tarjan算法。而提出此算法的普林斯顿大学的Robert E Tarjan教授也是1986年的图灵奖
No.17期 最小生成树（一） Mr. 王：我们再来讲一个时间亚线性算法——最小生成树问题。这里先简单介绍一下树的概念。 小可：那什么是树呢？ Mr. 王：树的简单定义，就是一个没有回路的连通无向图。
严格来讲并查集并不是一个数据结构，而是一个算法，毕竟其英文名直译是联合查找，但作为一个系列，还是当做数据结构讲了。
生成树：给定无向图G=(V,E)，连接G中所有点，且边集是E的n-1条边构成的无向连通子图称为G的生成树(Spanning Tree)，而边权值总和最小的生成树称为最小生成树（Minimal Spanning Tree,MST）。
A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.
在之前的 《客户端基本不用的算法系列：从 floodfill 到图的连通性》一文中，我们已经了解了在无向图中的割点和桥的定义。
图论中知名度比较高的算法应该就是 Dijkstra 最短路径算法，环检测和拓扑排序，二分图判定算法 以及今天要讲的最小生成树（Minimum Spanning Tree）算法了。
随着学习的深入，我们的知识也在不断的扩展丰富。树结构有没有让大家蒙圈呢？相信我，学完图以后你就会觉得二叉树简直是简单得没法说了。其实我们说所的树，也是图的一种特殊形式。
有向图强连通分量：在有向图 G 中，如果两个顶点 V_i, V_j 间（vi>vj）有一条从 V_i 到 V_j 的有向路径，同时还有一条从 V_j 到 V_i 的有向路径，则称两个顶点强连通 (strongly connected)。如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图。有向图的极大强连通子图，称为强连通分量 (strongly connected components)。
图（Graph）是一种表示对象之间关系的抽象数据结构。图由节点（Vertex）和边（Edge）组成，节点表示对象，边表示对象之间的关系。图可以用于建模各种实际问题，如社交网络、交通网络、电力网络等。
回到正题，首先介绍下什么是图的边连通度和点连通度。一般来说，点连通度是指对应一个图G，对于所有点集U属于V（G），也就是V（G）的子集中，使得G-U要么是一个非连通图，要么就是一个平凡图（即仅包含一个独立点的图），其中最小的集合U的大小就是图G的点连通度，有时候也直接称为图的连通度。通俗点说，就是一个图G最少要去掉多少个点会变成非连通图或者平凡图。当然对于一个完全图来说Kn来说，它的连通度就是n-1。 同理，边连通度就是对于一个非平凡图G，至少去掉多少条边才能使得该图变成非连通图。我们的问题就是，对于任意一个图，如何求该图的连通度以及边连通度？这跟最大流问题有什么联系？ 简单起见，我们先说如何求一个图的边连通度lamda(G)。（基于无向图考虑） 对于图G，设u，v是图G上的两个顶点，定义r（u，v）为删除最少的边，使得u到v之间没有通路。将图G转换成一个流网络H，u为源点，v是汇点，边容量均为1，那么显然r（u，v）就是流网络的最小割，根据（二）里的介绍，其等于流网络的最大流。 但是，目前为止我们还没解决完问题，因为显然我们要求的边连通度lamda（G）是所有的点对<u,v>对应的r（u，v）中最小的那个值。这样的话我们就必须遍历所有的点对，遍历的的复杂度为O（n*n）。这显然代价太高，而事实上，我们也不必遍历所有点对。
One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A "Gang" is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.
连通，字面而言，类似于自来水管道中的水流，如果水能从某一个地点畅通流到另一个地点，说明两点之间是连通的。也说明水管具有连通性，图中即如此。
图Graph是由顶点（图中的节点被称为图的顶点）的非空有限集合V与边的集合E（顶点之间的关系）构成的。 若图G中的每一条边都没有方向，则称G为无向图。 若图G中的每一条边都有方向，则称G为有向图。
记得我之前在讲 图论算法基础 时说图论相关的算法不会经常考，但最近被打脸了，因为一些读者和我反馈近期求职面试涉及很多图论相关的算法，可能是因为环境不好所以算法这块更卷了吧。
满足欧拉回路的一个大前提是判断当前图是一个连通图。问题又随之而来，什么是连通图？如何才能判断一个图到底是不是连通图？带着这个问题来看后面的内容。
在理解有向图和强连通分量前必须理解与其对应的两个概念，连通图（无向图）和连通分量。
No.18期 最小生成树（二） Mr. 王：接下来我们讨论一般的情况。在一般的情况中，我们先定义一些量以方便讨论。 Gi ：G 中包含所有权重小于i 的边的子图。 Ci ：Gi 中的连通分量数。 令β
某国有n个城市，为了使得城市间的交通更便利，该国国王打算在城市之间修一些高速公路，由于经费限制，国王打算第一阶段先在部分城市之间修一些单向的高速公路。 现在，大臣们帮国王拟了一个修高速公路的计划。看了计划后，国王发现，有些城市之间可以通过高速公路直接（不经过其他城市）或间接（经过一个或多个其他城市）到达，而有的却不能。如果城市A可以通过高速公路到达城市B，而且城市B也可以通过高速公路到达城市A，则这两个城市被称为便利城市对。 国王想知道，在大臣们给他的计划中，有多少个便利城市对。
一、背景介绍 强连通分量是有向图中的一个子图，在该子图中，所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象，因为它满足 自反性：顶点V和它本身是强连通的 对称性：如果顶点V和顶点W是强连通的，那么顶点W和顶点V也是强连通的 传递性：如果V和W是强连通的，W和X是强连通的，那么V和X也是强连通的 强连通性可以用来描述一系列属性，如自然界中物种之间的捕食关系，互相捕食的物种可以看作等价的，在自然界能量传递中处于同一位置。 下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,
人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的ID，
线性表中任一数据元素都可以 随机存取 ，所以 线性表的顺序存储结构是一种随机存取的存储结构。
相关视频——https://www.bilibili.com/video/BV1jW411K7yg?p=55 相关书籍——《大话数据结构》 图按照有无方向分为无向图和有向图。 无向图由定点和边构
今天分享到的是一种相对冷门的数据结构 —— 并查集。虽然冷门，但是它背后体现的算法思想却非常精妙，在处理特定问题上能做到出奇制胜。那么，并查集是用来解决什么问题的呢？
No.14期 图论基础回顾 Mr. 王：我们再讲一个时间亚线性算法——平面图直径的求解。平面图是图论中的一个概念，在大数据算法的很多地方都会涉及图的相关内容，所以这里我们还是要回顾一下图论的知识。 首
不少搞IT的朋友听到“算法”时总是觉得它太难，太高大上了。今天，跟大伙儿分享一个比较俗气，但是却非常高效实用的算法，如标题所示Union-Find，是研究关于动态连通性的问题。不保证我能清晰的表述并解释这个算法，也不保证你可以领会这个算法的绝妙之处。但是，只要跟着思路一步一步来，相信你一定可以理解它，并像我一样享受它。
有N个城市（编号1到N）和M条双向道路（编号1到M）。道路 i 连接城市 A 和城市 B 。
人和座位由一个整数数组 row 表示，其中 rowi 是坐在第 i 个座位上的人的ID，
今天是算法数据结构专题的第35篇文章，我们来聊聊图论当中的强连通分量分解的Tarjan算法。
在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。
No.35期 缩图法（二） Mr. 王：现在我们一步一步来分析。首先，每加入一条边，都会构成一个新的连通分量，或者在已有的连通分量上增加一个点，这意味着每一个强连通分量的大小至少为 2。 由此可知，每
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E) 其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。 在线性表中，元素个数可以为零，称为空表； 在树中，结点个数可以为零，称为空树； 在图中，顶点个数不能为零，但可以没有边。
程序由红色的节点开始运行，然后进入循环（红色节点下由三个节点组成），离开循环后有条件分支，最后运行蓝色节点后结束；
微信大概是我们每天必须接触的一个APP之一，公交上、地铁上、工作休息时，刷刷朋友圈，看看好友当天经历了什么。相较于QQ，微信的一个特点之一就是：除非好友的好友也是你的好友，否则你在朋友圈里看不到好友的好友对好友朋友圈的点赞和评论。
来源：力扣（LeetCode） https://leetcode-cn.com/problems/coloring-a-border/
连通图：无向图G中，若从顶点i到顶点j有路径相连，则称i,j是连通的；如果G是有向图，那么连接i和j的路径中所有的边都必须同向；如果图中任意两点之间都是连通的，那么图被称作连通图。
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
并查集是简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.
输入一个图，该图由一个有着 N 个节点 (节点值不重复 1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在 1 到 N 中间，这条附加的边不属于树中已存在的边。
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给你一个大小为 m x n 的整数矩阵 grid，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
