algorithm - How do a topological sort in Groovy, or an FP language 如何对列表进行排序，以便经理始终领先于下属(How do I do a topological sort in Groovy, or an FP language)

Question

我正在使用 Groovy 进行一个项目，我想采用一个员工数组，这样在数组中没有经理跟随他们的下属。原因是我需要将人员添加到数据库中，我不希望分两次完成。

所以，我基本上有:

<employees>
  <employee>
     <employeeid>12</employeeid>
     <manager>3</manager>
  </employee>   
  <employee>
     <employeeid>1</employeeid>
     <manager></manager>
  </employee>   
  <employee>
     <employeeid>3</employeeid>
     <manager>1</manager>
  </employee>   
</employees>

所以，它应该这样排序:

employeeid = 1
employeeid = 3
employeeid = 12

对于经理，第一个人应为空。

我正在考虑二叉树表示，但我预计它会非常不平衡，而且我不确定正确使用 Groovy 执行此操作的最佳方法。

有没有一种不涉及使用嵌套循环的方法来做到这一点？

Answer 1

http://en.wikipedia.org/wiki/Topological_sorting

假设除 CEO 以外的每个员工都有一个经理，我会将所有员工记录插入一个关联结构，该结构将每个员工 ID 映射到他们的直接下属列表。现在我们对 CEO 调用以下递归过程:

def recursiveinsert(e):
    insert e into the database
    for each direct report d of e:
        recursiveinsert(d)