c# - 在 vb.net 或 c# 中寻找算法，但我不知道它的名字!

Question

我会尽力解释该算法应该做什么:

有一个“食谱”类。每个 Recipe 都可以包含其他 Recipe，但不能包含它自己或包含它的任何其他 Recipe。

所以，一个简单的例子是我们只有两个食谱 A 和 B。

如果A先加B，后面B就不能加A，会造成循环

一个更复杂的例子是:

A,B,C

(1) 配方 C 添加 B
(2) B方加A方
(3) Recipe A 试图添加C，但由于关系不能。 C - B - A.

我可以自己做，我只是想知道这是不是一个标准的命名算法，我可以找到最优解。

谢谢

Answer 1

在数学/计算机科学术语中，您的结构称为 directed graph .您需要一个“Directed Acyclic Graph”——其中没有循环。

要找出图中是否存在循环，您可以使用一种名为 Topological sorting 的算法。 。它尝试重新排列图形，以便如果 A 引用 B，则 A 总是按顺序出现在 B 之前。如果图形有循环，它会停止。

如果您想在图中找到所有循环(这有助于错误消息)，那么 this stackoverflow question and answer 提供了很多帮助。

作为背景:
Graph = 节点由边连接的任何东西(在你的例子中，节点是食谱，引用是边)。
定向 = 边缘有方向。在您的情况下，这是真的，因为“A”指的是“B”，而不是“A”和“B”彼此。