对多个单向链表进行分组的算法

Question

我有一个数据集，它包含以下形式的对象:

    A -> Some parent    (E.g. A -> null)
    B -> Some parent    (E.g. B -> D)
    C -> Some parent    (E.g. C -> A)
    D -> Some parent    (E.g. D -> null)
    E -> Some parent    (E.g. E -> A)
    F -> Some parent    (E.g. F -> G)
    G -> Some parent    (E.g. G -> D)
    H -> Some parent    (E.g. H -> C)
    I -> Some parent    (E.g. I -> G)
    J -> Some parent    (E.g. J -> null)

我想要所有分组链表，如下所示:

    A <- C <- H
    ^-E

    J

    D <- B
    ^- G <- F
       ^- I

是否有一种通用算法可以解决单向链表的分组问题，并且性能优于纯暴力破解？

我这里的用例是，给定G，我怎样才能得到:

    D <- B
    ^- G <- F
       ^- I

以高效的方式。

Answer 1

1. 构造一个双元素结构数组，其中第一个元素是目标，第二个元素是源:

   (null, A),
   (   D, B),
   (   A, C),
   (null, D),
   (   A, E),
   (   G, F),
   (   D, G),
   (   C, H),
   (   G, I),
   (null, J)
   

2. 按第一个元素对这个数组进行排序:

   (null, A),
   (null, D),
   (null, J),
   (   A, C),
   (   A, E),
   (   C, H),
   (   D, B),
   (   D, G),
   (   G, F),
   (   G, I)
   

3. 然后使用初始数据和刚创建的数组递归地显示整个图:

   a.
         ^- G
   
   b.
         ^- G <- F
            ^- I
   
   c.    D
         ^- G <- F
            ^- I
   
   d.    D <- B
         ^- G <- F
            ^- I