1

Perl スクリプトが有向グラフのすべての循環ノードを検出できるという問題の解決策を探しています。 たとえば、次のグラフがあります。

A<-N<-G<-L<- A<-B<-C<-D<-E<-F<-A Be a Graph with cyclic edges. 
use strict;
use warnings;
my @graphNodes=(A,N,G,L, A,B,C,D,E,F,A );
my depEdges= dependBy(); #Let dependBy be hypothetical function that return immediate dependents.

コードの残りの部分では、循環依存関係に関係するすべてのノードを収集するための論理的な助けが必要です。たとえば、私の場合、ノード「A」には循環依存関係があります。周期的なエッジまたは依存関係を見つけるために、dependBy 関数を再帰的に実装するにはどうすればよいですか?

4

1 に答える 1

1

これは概念的なヘルプではありませんが、最速の解決策です。誰かが既に解決策を見つけているかどうかを確認してください。この場合、CPANのGraphモジュールを使用してそれを行うことができます。

use strict;
use warnings;
use feature 'say';
use Graph;

my $g = Graph->new;

my @edges = qw(A B C D E F A);
for (my $i =0; $i < $#edges; $i++) {
  $g->add_edge($edges[$i], $edges[$i+1]);
}

say $g;
say "is cyclic" if $g->is_cyclic;
say $g->find_a_cycle;

これは出力されます：

A-B,B-C,C-D,D-E,E-F,F-A
is cyclic
FABCDE
于 2015-09-28T12:38:27.603 に答える