c# – 检测图重新收敛的算法(类似于公共子树？)

概述我整天都在研究这个问题,我正在重写我们的一个遗留产品,而且我很难确定如何在流程图中找到特定节点.这个问题让我想起了大学,但对于我的生活,我无法想出一个算法来解决这个问题. 我附上3个屏幕截图来帮助解释这一点,但基本问题是,给出是/否？决策节点,找到终止分支的最近的子节点. 我在C#.NET和JSON工作.在JSON中,我有一个对象,它为每个节点提供唯一的标识符,并且还标识从一个节点到下一个节点的每 我整天都在研究这个问题,我正在重写我们的一个遗留产品,而且我很难确定如何在流程图中找到特定节点.这个问题让我想起了大学,但对于我的生活,我无法想出一个算法来解决这个问题.

我附上3个屏幕截图来帮助解释这一点,但基本问题是,给出是/否？决策节点,找到终止分支的最近的子节点.

我在C#.NET和JSON工作.在JSON中,我有一个对象,它为每个节点提供唯一的标识符,并且还标识从一个节点到下一个节点的每个“链接”.我希望编写一个函数(或几个)来确定给定C#中的分支节点的第一个“结束节点”.目前我已经在C#中将JsON构建为XML.

鼓励所有和所有想法,不是真正寻找代码而是寻找方法/算法.

附件是图中JsON的输出：

{ "class": "go.GraphlinksModel","linkFromPortIDProperty": "fromPort","linktoportIDProperty": "toport","nodeDataArray": [ {"key":-1,"category":"Start","loc":"169 288","text":"Start"},{"key":-2,"category":"End","loc":"855 394","text":"End"},{"category":"Branch","text":"Yes or No","key":-4,"loc":"284.8837209302326 285.7848837209302"},{"category":"DelayNode","text":"Delay","key":-3,"loc":"365.8837209302326 215.52345997177622"},"key":-5,"loc":"478.8837209302326 214.52345997177622"},"key":-6,"loc":"568.8837209302326 151.52345997177622"},"key":-7,"loc":"573.8837209302326 268.5234599717762"},"key":-8,"loc":"653.8837209302326 215.52345997177622"},"key":-9,"loc":"392.8837209302326 392.5234599717762"},"key":-10,"loc":"454.8837209302326 317.5234599717762"},"key":-11,"loc":"550.8837209302326 473.5234599717762"},"key":-12,"loc":"549.8837209302326 317.5234599717762"},"key":-13,"loc":"711.8837209302326 343.5234599717762"},"key":-14,"loc":"434.8837209302326 487.5234599717762"} ],"linkDataArray": [ {"from":-4,"to":-3,"fromPort":"T","toport":"L","visible":true},{"from":-1,"to":-4,"fromPort":"R","toport":"L"},{"from":-3,"to":-5,{"from":-5,"to":-6,"to":-7,"fromPort":"B","visible":true,"text":"NO"},{"from":-6,"to":-8,{"from":-7,{"from":-4,"to":-9,{"from":-9,"to":-10,{"from":-10,"to":-12,{"from":-11,"to":-13,{"from":-12,{"from":-8,{"from":-13,"to":-2,"to":-14,{"from":-14,"to":-11,"text":"NO"} ]}

解决方法 更新：我提出了另一种解决方案,这次是使用最常见祖先问题的标准解决方案.看到我的其他答案.

正如对奥伦回答的评论中所指出的那样,奥伦实际上已经回答了这个问题：“两个分支机构最接近的节点是什么？”但实际上要回答的问题是“两个分支必须达到的最接近的节点是什么？”

这是一个相当难以解决的问题,我不知道一个有效的解决方案.但是,这是一个可行的算法草图.

假设给定的决策节点被称为A,而WolOG它有两个子节点B和C.那么问题是什么是节点,称之为G,它具有以下两个属性：

>从B到END的每条可能路径,以及从C到END的每条可能路径都经过G.
> G是距离B和C最近的具有第一个属性的节点.

(注意G可能是END.我们可能有A – > B,A – > C,B – > END,C – > END.)

我们可以从容易制作一组可能的G的候选人开始.选择从B到END的任何路径 – 如果您愿意,可以随意选择它 – 并将其节点放在哈希集中.然后选择从C到END的任何路径,并将其节点放在哈希集中.这两组的交集包含G.调用交集α.

所以现在让我们从Alpha中删除绝对不是G的所有节点.对于集合Alpha中的每个节点N：

>构造一个与原始图形相同的新图形,但缺少N.
>新图表中的B或C是否仍可以到达END？如果是,则N绝对不是G.如果不是,则添加N以设置Beta.

如果我们完成Beta测试为空,则G为END.

否则,Beta中有节点.这些节点中的每一个都具有如果删除它,则没有其他方法可以从B或C到END.恰好其中一个节点必须最接近B – 如果两个节点同样接近,那么其中一个节点就没有必要了！ – 来自B的广度优先遍历也是如此,并且当您第一次遇到Beta中的节点时,那就是您的G.

如果图形很大,这个草图似乎不会很快,但我很确定它会起作用.我很想知道是否有更好的解决方案.

总结

以上是内存溢出为你收集整理的c# – 检测图重新收敛的算法(类似于公共子树？)全部内容，希望文章能够帮你解决c# – 检测图重新收敛的算法(类似于公共子树？)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。