c# - 图问题的算法

Question

我需要检查列表中定向节点的连通性。它基本上是每个问题有 2 到 7 个答案。选择的答案决定了下一个问题。由于这些对将被手动捕获，因此我需要检查每个可能的路径以进行环回(不允许)和死胡同(所有路由必须停在 END 节点)任何指针？

start --> n1 --- n2 --- n3 --- n4 --- end

            \  /   \      \   /       /

             n5     \      n6------ n7

              \      \     /       /

               n8----n9---n10----n11

          DIRECTION -->

Answer 1

这可能是您正在寻找的:

Testing whether a graph is acyclic

您的 END 节点就是该页面术语中的叶节点。

1. 如果图没有节点，则它是无环的。
2. 如果图没有叶子，则它是循环的。
3. 选择任何叶子，移除叶子及其所有过渡，转到第 1 步。

要检查是否没有死角:在使用上述算法之前，只需确保只有一个叶节点即可。