根据层次列表中对象的相互依赖性对它们进行排序

Question

我有一些相互依赖的对象。

• A
• B（取决于A）
• C（取决于B）
• D
• E（取决于B和F）
• F（取决于C）
• G
• H（取决于B）

我想创建这些对象的分层列表，其中一个对象被放置在列表中，这些对象位于包含其相关性的列表之后。

上一个对象列表将如下放置：

1. A、 D、G（这些对象没有依赖关系）
2. B（B取决于A）
3. C、 H（C和H取决于B）
4. F（F取决于C）
5. E（E取决于B和F）

Wich算法能解决这个问题吗？

Answer 1

如果您还没有任何帮助结构，那么您应该使用暴力。

我会使用一个列表，它将在模式中垂直扩展，垂直列表的每个节点都有一个列表。

因此，在您的示例中，我将在垂直列表中有5个节点，对于第一个节点，我将有一个包含3个节点的列表（第一个节点将托管a，第二个D和第三个G）。垂直列表的第二个节点，将有一个带有一个节点的列表，其中将包含B，依此类推

所以算法应该是这样的：

1.For every item
2.  if item.dependency in list
3.    append item in the correct node
4.  else // item not in list
5.    create node in list with the dependency of the item
6.    append item in the created node

所以，在上面的伪代码中，当我说列表时，我指的是垂直的。

在步骤1中，我们检查您拥有的所有项目。

在步骤2，您检查当前正在处理的项目是否存在于列表中（通过搜索整个列表并返回找到的位置或更智能的东西）。

在步骤3中，您转到步骤2中找到的位置，并在位于该位置的节点处的列表末尾插入项目的值（您不需要再次存储依赖项）。请注意，如果位置中的节点在其列表中没有条目，那么您还需要创建它的列表。

在步骤4中，我们的项目在列表中找不到。

在步骤5中，我们在列表中创建一个新节点，该节点将具有项的依赖项作为值。

在步骤6中，我们将项目插入在步骤5中创建的节点中。

希望这能有所帮助！