logo标签列表

一个图问题的算法

c#algorithmgraph
3

我需要检查列表中有向节点的连通性。 这基本上是包含2到7个答案的问题。选择的答案决定了下一个问题。 由于这些配对将手动捕获，因此我需要检查每条可能的路径是否存在回路（不允许）和死路（所有路径必须在“END”节点处停止）。 有什么指导意见吗？

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

            \  /   \      \   /       /

             n5     \      n6------ n7

              \      \     /       /

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

          DIRECTION -->
1
我对这张图有点困惑。n8只有一个答案吗？n9呢？ - Rob Elliott
不，n1-n11中没有一个问题只有少于2个答案。该图是不同答案可能导致的不同路径的示意图。 例如：n1有4个答案，其中3个指向n2，其余的指向n5。 一个问题的答案可以指向不同的下一个问题，但我尽量保持图形简单易懂。 - callisto
哦，等等，n6显示了3条不同的路径。 n9的所有答案都指向n10，因为n11只指向n7。 - callisto
2个回答
4

这可能是您正在寻找的内容：

测试图形是否为无环图

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

  1. 如果图形没有节点，则它是无环的。
  2. 如果图形没有叶子，则它是有环的。
  3. 选择任何一个叶子，删除该叶子及其所有转换，转到步骤1。

要检查是否存在死结：只需确保在使用上述算法之前只有一个单独的叶子节点即可。

3
使用广度优先搜索算法，记录已访问的所有节点。如果在寻找下一个要遍历的节点时，已访问的节点之一是可能性，则图形不正确。此外，如果您到达一个没有其他可遍历的节点，并且尚未到达结束节点，则该图形也未正确连接。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接