我有一组指令,它们的工作原理如下:
- 项目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->