c# - 哪种图遍历算法适合这种情况

Question

我在遍历以下类型的图时遇到问题。

• 在每个节点可以有多个输入和输出。
• 每个输出可以指向多个输入(例如，A 的第三个输出转到 C 和 D)
• 在每个节点，一些计算是根据输入中提供的值进行的。输出结果提供给其他节点的输入。
• 要从一个节点遍历到下一个节点，我必须知道所有输入的值。

我想到了这个遍历:

• 在A点，用唯一的输入计算出所有的输出
• 使用 A 的第一个输出从 A 移动到 C。
• 在 C 处，我们不知道其他输入，因此回溯到 A。
• 在 A 处，使用第二个输出到达 B。
• 在 B，我们没有所有的输入，所以回溯到 A。
• 在 A 处，获取第三个输出并到达 B。
• 在 B，现在我们拥有计算输出的所有输入。
• 在 B，通过第一个输出到达 C。
• 在 C 处，我们拥有所有输入，因此进行计算并达到 E。
• 等等

那么您认为哪种遍历算法在这种情况下最有效。 BFS 可能不起作用，因为在我的例子中，当我到达一个节点时我不知道所有的输入并且回溯是不可能的。

我必须在 C# 中实现它。

Answer 1

想法:

使用广度优先搜索，但也有每个节点的计数(或者类似地，输入列表)。

当你访问一个节点时:

• 增加它的数量
• 如果计数小于传入边的数量，则不做任何事情
• 否则，照常处理节点

你的例子:

候选人:A
我们处理 A。

候选人:C、B、D
我们访问 C，但不处理它，因为它的计数 = 1 < 2 = 传入边。

候选人:B、D
我们访问 B 并对其进行处理。

候选人:D、C、E、D
我们访问 D，但不处理它，因为它的计数 = 1 < 2 = 传入边(第二个边尚未处理)。

候选人:C、E、D
我们访问 C 并对其进行处理。

候选人:E、D、E
我们访问 E，但不处理它，因为它的计数 = 1 < 3 = 传入边(第二个和第三个边尚未处理)。

候选人:D、E
我们访问 D 并对其进行处理。

候选人:D、E、E
我们访问 D 并对其进行处理。

候选人:E，E
我们访问 E，但不处理它，因为它的计数 = 2 < 3 = 传入边(第三条边尚未处理)。

候选人:E
我们访问 E 并对其进行处理。