根据项目的需求对项目集进行分层排序



我有一组指令,它们的工作原理如下:

  • 项目A:需要B、C
  • 项目B:需要C、D
  • 项目C:不需要任何东西
  • 项目D:需要C

排序后的指令列表应将A作为最后一个,因为它是需要最多项的指令,将C作为第一个,因为不需要任何内容。此外,在这种情况下,订单将是唯一的,因为创建B需要发生D,这意味着最终订单将是这样的:

  • C
  • D
  • B
  • A

我试着在网上寻找类似的算法,但找不到任何算法,尽管可能这个问题有一个我不知道的特定名称,这可能是我找不到解决方案的原因。

那么,有解决这类问题的算法吗?

这看起来像是一个拓扑排序问题,可以使用有向无环图(DAG(来解决。网上有很多关于拓扑排序的资源——这里有一些有用的资源:

https://www.geeksforgeeks.org/topological-sorting/

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

我不知道有任何具体的算法,但我想,一种方法是尝试计算每个项目的权重/优先级。

我们可以先给每个项一个优先级1,然后循环遍历该项的所有依赖项,并将该项的优先级添加到我们的优先级中。

例如

Item A = 1 + B + C ( 1 + 2 + 1) = (4)
Item B = 1 + C + D (1 + 1 + 1) = (3)
Item C = 1 + Nothing (1 + 0) = (1)
Item D = 1 + C (1 + 1) = (2)

这将给予它们C->D->B->

最新更新