果然有现成的库。clique这个关键词没有掌握，搜了好一会全连通图，啥也没搜到。呵呵。
On 7月14日, 下午1时28分, 朱岩 <[email protected]> wrote: > 图论解法： > > 找最大完全连通子图，可以用Graph::Clique，当然应该还有更好的算法； > 这里只举了个10x10的小例子 > 用非零数的平方根作为最大子图顶点数的上限 > > use strict; > use Graph::Clique; > > my @edges; > my %h; > my $nnz; # num of non-zeros > > # build up undirected graph > > while(<DATA>){ > my $i = $.+1; > my @a = split(/ /,$_); > for my $j (0..$#a){ > if ($a[$j]){ > $nnz++; > my $e = $i <= $j ? $i.",".$j : $j.",".$i; > $h{$e}++; > } > } > > } > > foreach my $key (sort keys %h){ > my @a = split(/\,/, $key); > push @edges, [@a]; > > } > > # find maximal clique > > my @cliques; > > for (my $k=int(sqrt($nnz)); $k>3; $k--){ > @cliques = getcliques($k,\@edges); > if ($#cliques >=0){ > last; > } > > } > > print join("\n", @cliques),"\n"; > > __DATA__ > 0 0 1 0 1 0 0 0 0 0 > 0 1 1 0 0 0 0 0 0 0 > 1 1 1 0 1 0 0 1 0 0 > 1 1 1 0 0 0 0 0 0 0 > 1 1 1 0 1 0 0 1 0 1 > 0 0 0 0 0 0 0 0 0 0 > 0 0 0 0 0 0 0 0 0 0 > 0 0 1 0 1 0 0 1 0 1 > 0 0 0 0 0 0 0 0 0 0 > 0 0 0 0 1 0 0 1 0 0 -- 您收到此邮件是因为您订阅了 Google 网上论坛的“PerlChina Mongers 讨论组”论坛。 要向此网上论坛发帖，请发送电子邮件至 [email protected]。 要取消订阅此网上论坛，请发送电子邮件至 [email protected]。 若有更多问题，请通过 http://groups.google.com/group/perlchina?hl=zh-CN 访问此网上论坛。
