linux - 如何在 Perl 中找到图形的连通分量？

Question

我有以下节点和边的集合。我想要做的是从中找到所有不同的图形。

my %connections=(36=>[31],10=>[3,4],31=>[30,22],30=>[20],22=>[20,8],20=>[1],8=>[5],5=>[2],2=>[1,20],  3=>[7]);

在这个例子中它将产生:

my %all_graph = {
   graph1 => {36=>[31],31=>[30,22],30=>[20],22=>[20,8],20=>[1],8=>[5],5=>[2],2=>[1,20]}.
   graph2  => {10=>[3,4],  3=>[7]} 
};

是否有任何现有算法可以做到这一点？

Answer 1

使用 Graph模块:

#!/usr/bin/perl

use strict; use warnings;

use Graph;

my %connections = (
    36 => [ 31 ],
    10 => [ 3, 4],
    31 => [ 30, 22],
    30 => [ 20 ],
    22 => [ 20, 8],
    20 => [ 1 ],
    8  => [ 5 ],
    5  => [ 2 ],
    2  => [ 1, 20 ],
    3  => [ 7 ]
);

my $g = Graph->new( undirected => 1 );

for my $src ( keys %connections ) {
    for my $tgt ( @{ $connections{$src} } ) {
        $g->add_edge($src, $tgt);
    }
}

my @subgraphs = $g->connected_components;
my @allgraphs;

for my $subgraph ( @subgraphs ) {
    push @allgraphs, {};
    for my $node ( @$subgraph ) {
        if ( exists $connections{ $node } ) {
            $allgraphs[-1]{$node} = [ @{ $connections{$node} } ];
        }
    }
}

use YAML; print Dump \@allgraphs;

输出:

[sinan@archardy SO]$ ./g---- 2:    - 1    - 20  20:    - 1  22:    - 20    - 8  30:    - 20  31:    - 30    - 22  36:    - 31  5:    - 2  8:    - 5- 10:    - 3    - 4  3:    - 7