algorithm - 给定节点关系数据结构，如何对父子列表进行排序？

Question

这张图显示了父子关系树。它是定向的，没有循环。一个 child 可以有多个 parent 。

Perl中对应的数组数组为:

(
    [A C],
    [B C],
    [D F G],
    [C E D],
    [E J X I],
    [I J]
)

每个子数组中的第一个元素是其余元素的父元素，子数组的数量是至少有一个 child 的节点的数量。

问题

我想为每个节点分配一个数字，告诉它在图中的哪个级别。级别还应该说明两个节点是否独立，我的意思是它们不是直接父子关系。这个具体例子的答案(在许多其他答案中)应该是:

[A B C D E F G X I J]
[1 1 2 3 3 4 4 4 4 5]

我的解决方案可以用任何语言实现，但首选 Perl。

不过，建议的解决方案似乎都不适用于此阵列:

(
  [ qw( Z A   )],
  [ qw( B D E ) ],
  [ qw( A B C ) ],    
  [ qw( G A E  )],
  [ qw( L B E )]  
)

同样

(
  [ qw/ M A / ],
  [ qw/ N A X / ],
  [ qw/ A B C / ],
  [ qw/ B D E / ],
  [ qw/ C F G / ], 
  [ qw/ F G / ]
  [ qw/ X C / ]
)

Answer 1

Graph::Directed模块将使处理此类数据变得更简单。

多个源节点可能会使它变得更复杂(例如，如果有另一条边 [Y, X])，但只要所有源都在第一级，它就可行。

这里有一些代码可以生成您期望的信息。它假设顶层以下的所有节点都可以从第一个源节点访问，并从那里测量它们的路径长度，忽略第二个源。

use strict;
use warnings;

use feature 'say';

use Graph::Directed;

my @data = (
  [ qw/ A C / ],
  [ qw/ B C / ],
  [ qw/ D F G / ],
  [ qw/ C E D / ],
  [ qw/ E J X I / ],
  [ qw/ I J / ],
);

my $graph = Graph->new(directed => 1);

for my $item (@data) {
  my $parent = shift @$item;
  $graph->add_edge($parent, $_) for @$item;
}

my ($source) = $graph->source_vertices;

for my $vertex (sort $graph->vertices) {
  my $path;
  if ($graph->is_source_vertex($vertex)) {
    $path = 0;
  }
  else {
    $path = $graph->path_length($source, $vertex);
  }
  printf "%s - %d\n", $vertex, $path+1;
}

输出

A - 1
B - 1
C - 2
D - 3
E - 3
F - 4
G - 4
I - 4
J - 4
X - 4