0

次の問題があります。次のようにソートされたファイルがあります。

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番目の」番号になります） vector cluster[n]) 過去のクラスターに属さない番号がある場合は、新しいラベルなどが必要ですが、このアイデアをコードで再現する方法がわかりません...何か助けはありますか?

4

3 に答える 3

2

上記のように、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]
于 2013-03-10T20:42:11.757 に答える
1 
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);
        }
    }
}
于 2013-03-10T20:37:03.307 に答える
0

ここに示した解決策に加えて、Graph::UnionFindを使用してこの問題を解決することもできます。同じ問題に対する適切な解決策を提供しているため、最近私が尋ねた質問を指摘するのに役立つと思います.

于 2013-03-12T18:38:36.857 に答える