这张图显示了父子关系树。它是定向的,没有循环。一个 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 / ]
)
最佳答案
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
关于algorithm - 给定节点关系数据结构,如何对父子列表进行排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10999094/