perl - 从 2 列文件中查找集群

Question

我有以下问题，我有一个文件排序如下：

1 2
1 3
2 4
2 5
6 7
6 8
9 1

每个数字代表网络的一个“节点”。左节点与右节点相连，如果它们相连，它们属于同一个“集群”。

我想找到由这些数字和集群组成组成的“集群”的数量，在这种情况下应该给出输出：

cluster[1]=(1,2,3,4,5,9)
cluster[2]=(6,7,8)

我认为给每个数字一个标签可能很有用，每次我找到这个数字的邻居或邻居的邻居时，它都会使用相同的标签（这将是集群中的“第 n 个”数字向量cluster[n]），如果有一个数字不属于任何过去的集群，那么它需要一个新的标签等......，但我不知道如何在代码中重现这个想法......有什么帮助吗？

Answer 1

如上所述，您应该使用Graph。您正在寻找无向图的连通分量。

#!/usr/bin/env perl

use strict;
use warnings;

use Graph::Undirected;
my $g = Graph::Undirected->new(unionfind => 1);

while (my $line = <DATA>) {
    last unless $line =~ /\A ([0-9]+) \s+ ([0-9]+) \s+ \z/x;
    $g->add_edge($1, $2);
}

my @cc = sort { @$b <=> @$a }
         map { [ sort @$_ ] } $g->connected_components;

printf "[%s]\n", join(', ', @$_) for @cc;

__DATA__
1 2
1 3
2 4
2 5
6 7
6 8
9 1

[1、2、3、4、5、9]
[6、7、8]

Answer 2

my @node_links = (
    {a => 1, b => 2},
    {a => 1, b => 3},
);

my %clusters;

for my $node_link (@node_links) {
    $clusters{ $node_link->{a} } ||= {};
    $clusters{ $node_link->{a} }->{ $node_link->{$b} } = 1;
    $clusters{ $node_link->{b} } ||= {};
    $clusters{ $node_link->{b} }->{ $node_link->{$a} } = 1;
}

my @clusters;

while (my($node, $node_links) = each %clusters) {
    my %cluster;
    $cluster{$node} = 1;
    delete $clusters{$node};
    build_cluster(\%clusters, \%cluster, $node_links);
    push(@clusters, \%cluster);
}

sub build_cluster {
    my($clusters, $cluster, $node_links) = @_;

    for my $node (keys %$node_links) {
        $cluster->{$node} = 1;
        if ($clusters->{$node}) {
            my $next_node_links = delete $clusters->{$node};
            build_cluster($clusters, $cluster, $next_node_links);
        }
    }
}

Answer 3

除了此处介绍的解决方案，您还可以使用Graph::UnionFind解决此问题。我认为向您指出我最近提出的一个问题可能会有所帮助，因为它为同一问题提供了很好的解决方案。