python - 如何使用 Julia 查找矩阵中的连通分量

Question

假设我有以下矩阵(在此处用 Julia 语言定义):

    mat = [1 1 0 0 0 ; 1 1 0 0 0 ; 0 0 0 0 1 ; 0 0 0 1 1]

将一组值为“1”的相邻元素视为一个“分量”，如何识别该矩阵具有 2 个分量以及由哪些顶点构成每个分量？

对于上面的矩阵 mat 我想找到以下结果:

组件 1 由矩阵的以下元素(行，列)组成:

    (1,1)
    (1,2)
    (2,1)
    (2,2)

组件 2 由以下元素组成:

    (3,5)
    (4,4)
    (4,5)

我可以使用像 this 这样的图算法识别方阵中的分量。但是，此类算法不能用于非方阵，例如我在此展示的那种。

任何想法将不胜感激。

如果您的建议涉及使用 Python 库 + PyCall，我愿意接受。尽管我更愿意使用纯 Julia 解决方案。

问候

Answer 1

使用Image.jl的label_components确实是解决核心问题最简单的方法。但是，您对 1:maximum(labels) 的循环可能效率不高:它是 O(N*n)，其中 N 是数字labels 和 n 中元素的最大数量，因为您访问了 labels 中的每个元素 n 次。

您最好只访问 labels 的每个元素两次:一次确定最大值，一次将每个非零元素分配给其适当的组:

using Images

function collect_groups(labels)
    groups = [Int[] for i = 1:maximum(labels)]
    for (i,l) in enumerate(labels)
        if l != 0
            push!(groups[l], i)
        end
    end
    groups
end

mat = [1 1 0 0 0 ; 1 1 0 0 0 ; 0 0 0 0 1 ; 0 0 0 1 1]

labels = label_components(mat)
groups = collect_groups(labels)

测试矩阵的输出:

2-element Array{Array{Int64,1},1}:
 [1,2,5,6] 
 [16,19,20]

调用find 之类的库函数偶尔会有用，但它也是较慢语言的一种习惯，值得摒弃。在 julia 中，您可以编写自己的循环，它们会很快；更好的是，通常生成的算法更容易理解。 collect(zip(ind2sub(size(mat),find( x -> x == value, mat))...)) 并没有完全脱口而出。