c# – 图形问题的算法

发布时间：2020-12-16 01:31:27 所属栏目：百科来源：网络整理

导读：我需要检查列表中定向节点的连通性. 基本上是问题,每个问题有2到7个答案.选择的答案决定了下一个问题. 由于这些对将被手动捕获,我需要检查每个可能的路径以循环(不允许)和死角(所有路由必须在END节点处停止) 有什么指针吗？ start -- n1 --- n2 --- n3 --- n

我需要检查列表中定向节点的连通性.
基本上是问题,每个问题有2到7个答案.选择的答案决定了下一个问题.
由于这些对将被手动捕获,我需要检查每个可能的路径以循环(不允许)和死角(所有路由必须在END节点处停止)
有什么指针吗？

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

              /            /       /

             n5           n6------ n7

                         /       /

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

          DIRECTION -->

解决方法

这可能是您正在寻找的：

Testing whether a graph is acyclic

您的END节点是叶节点在该页面的术语中的含义.

>如果图形没有节点,则它是非循环的.
>如果图形没有叶子,则它是循环的.
>选择任何叶子,移除叶子和所有过渡到它,转到步骤1.

要检查没有死角：在使用上述算法之前,只需确保只有一个叶节点.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!