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

Question

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

有一个课程'食谱'.每个食谱可以包括其他食谱,但不能包括自己或包含它的任何其他食谱.

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

如果A首先添加B,那么稍后B不能添加A,因为它会导致循环.

一个更复杂的例子是:

A,B,C

(1)配方C添加B
(2)配方B添加A
(3)配方A尝试添加C,但由于这种关系不能.C - B - A.

我自己可以这样做,我只是想知道这是否是一个标准命名算法,我可以抓住最佳解决方案.

谢谢

Answer 1

在数学/计算机科学术语中,您的结构称为有向图.你想要一个" 有向无环图 " - 这是一个没有循环的图.

要确定图形中是否存在循环,可以使用称为拓扑排序的算法.它试图重新排列图形,这样如果A指的是B,那么A总是按顺序出现在B之前.如果图表有周期,它会停止.

如果要查找图中的所有周期(这对于错误消息很有帮助),那么此stackoverflow问题和答案会提供很多帮助.

作为背景:
Graph =具有通过边链接的节点的任何东西(在您的情况下节点是配方,参考是边).
定向 =边缘有方向.在你的情况下这是真的,因为'A'指的是'B',而不是'A'和'B'.

Answer 2

拓扑排序/环路检测？（如果检测到环路，拓扑排序算法就会停止。）

这应该与您正在做的事情很接近。