问题标签 [connected-components]

在 MATLAB 中使用该函数regionprops时，可以选择提取每个连通分量的二进制图像。二值图像的大小减小到连通分量的大小。我不希望二进制图像的大小减小。我希望二进制图像的大小保持其原始大小，同时仅在原始图像大小的相应位置显示选定的连接组件。如何提取原始图像大小的连通分量？

我正在寻求改进我的解决方案，以使用快速查找算法在有向图中查找所有弱连接组件。

问题陈述

给定一个 列表DirectedGraphNode，找到所有岛（即弱连接组件）。

因此，给定以下有向图：

输出应该如下（顺序无关紧要）：

我使用快速查找算法解决了这个问题。下面的代码：

然而，这个算法在最坏的情况下运行在O(N^3)中，因为它每次都需要对联合进行线性搜索。我很好奇是否有任何方法可以改善这一点。

谢谢您的建议！

提供了一个包含 0 和 1 的矩阵，所有 0 都是水，1 是土地。一组连接的 1 形成一个岛。如果一次更改可以将一个 0 转换为 1，那么找出我们需要进行的最小更改次数，以便矩阵中只有一个岛。

例如：

矩阵->

转换为单个岛的最小更改数为 1。将 (2,2) 转换为 1。

我在一次采访中被问到这个问题。我使用 dfs 来找出岛屿的数量。但无法获得进一步解决的方法。

Graph Centroid is a vertex at equal distance or at distance less than or equal (N/2) where N is the size of the connected components connected through this vertex?! [Needs Correction?!]

Here's a problem at CodeForces that asks to find whether each vertex is a centroid, but after removing and replacing exactly one edge at a time.

Problem Statement

I need help to refine this PseudoCode / Algorithm.

The problem is that this algorithm will run in at least O(N*M^2)). It's not acceptable.

I looked up the answers, but I couldn't come up with the high level abstraction of the algorithm used by others. Could you please help me understand how these solutions work?

Solutions' Link

(*1) DFS Loop

我有一个图像 ımage 有曲线，但这些曲线已经切割；不是 contunie 我怎样才能通过连接的组件更清楚这条曲线

我想知道是否有适当的算法来对以下问题的节点进行分组：

输入：关系断开图，具有以下数据结构：

输出：聚类所有具有有向/无向关系的人，作为力布局图（D3.js）中的公司属性的参考。上面示例的输出将是绘制一个圆形/气泡力布局图，其中包含 2 个气泡，其中包含以下人员：

组 1 = {1、2、3、4}

组 2 = {5, 6}

我想遍历包含~10 ⁷个顶点的无向图的每个连通分量。即我想在每个向量 V ₁ ...V _{k上调用一些函数 f(V i} )，其中 V _i是一个向量，其中包含附加到图的第 i 个连通分量中每个节点的数据。

最快的算法是什么？

我的第一个想法是：

1. 将所有未访问的顶点存储在一个堆中，然后反复从堆中取出一个顶点，使用 DFS 找到它的连通分量_Vi，调用 f(V _i ) 并从堆中删除该分量中的所有顶点。
2. 找到联合查找不相交集合的变体，它不仅支持有效的集合联合，而且还可以有效地迭代集合并找到它们的成员。（这可能吗？）

我试图使用connectedComponents()pyspark 中的 graphframes 来计算一个相当大的图的连通分量，该图大约有 1800K 顶点和 500k 边。

6小时后任务还没有结束。我在一台带有 Windows 的机器上运行 pyspark

一个。在给定的设置中进行这样的计算是否可行？

湾。我收到如下警告消息

这是什么意思？

C。我们如何指定图在图框中是无向的？我们需要在两个方向上添加边吗？

由于 OpenCV 3.0 有一个非常有用的函数connectedComponentsWithStats，我很感兴趣是否有办法加快这个函数的速度？

我正在做一个项目，我必须计算异常的属性。这个属性很好用 connectedComponentsWithStats 函数计算，但我需要更快的速度......

我们计算异常的图像是使用 OpenCV阈值函数从灰度图像计算的 8 位二进制图像。我在下面展示了这个二进制异常图像：

我们可以看到黑色区域——这是我们感兴趣的区域（ROI）。在 ROI 上，我们可以看到白色异常（点、线、划痕……）。对于这些异常，我必须计算函数 connectedComponentsWithStats 的质心、面积和类似属性，但它对我的应用程序来说还不够快。我的属性计算代码在这里：

计算大约需要 55 毫秒，我想优化它至少快 10 倍。

已经感谢您的所有建议！

由n 个节点组成的图，其中有一条边从1到2、2到3、3到4、 ........、n-1到n。

现在，有一个由1到n的排列组成的数组，并且有基于数组段给出的查询数量。确定给定段的节点（由数组元素指示）形成的连通分量的数量。例如，

数组：4 5 3 2 1 查询是：[1, 5] , [1, 4] , [2, 4]

对于[1, 5]，数组元素是1 2 3 4 5并且所有元素都是连接的并形成单个连接组件。

对于[1, 4]，数组元素是2 3 4 5，它们也形成了单个连通分量。

对于[2, 4]，数组元素是2 3 5，因此2和3形成单个组件，而5形成单个组件，因此[2, 4]中共有2 个连接的组件。