隔离图中的“编织部分”

假设我有一个图形表示形式的图形:

enter image description here

如您所见,这里有一个“编织部分”,可以采用许多不同的路径,但是,如果继续走下去(至少沿主轴的一个方向),您总是会到达同一点“辫子”的结尾。

该图可以沿任一方向延伸很长的距离,并具有沿途任意复杂的多个辫子。

是否有某种算法能够隔离蓝色圆圈的节点,从而指示“辫子”的起点和终点?还是走得更远,只返回包含这些节点的辫子的子图?

我在用Google阐明这个问题时遇到了麻烦,而我的图形库文档并没有说明它实现的各种算法。

我目前正在使用Python NetworkX,但是如果它没有直接实现,我不反对手动实现算法。

我还应该指定理想情况下可以定向图,以便所有边缘都指向主轴的一个方向,但是也可以使用定向图的解决方案会更好。

评论
  • Henry
    Henry 回复

    我不知道执行此操作的特定算法,但是实现一个算法很容易。您以广度优先的方式遍历节点,并跟踪正在探索的分支数量。当数字增加到1以上时,您就处于“编织”的开始。当您正在探索的并发分支数下降到1时,您刚刚发现了辫子的末端。这可能不是最佳选择,因为您的复杂度大于O(n),因为如果各个分支中的节点数不同,则无法跳过已访问的节点(如果这样做,则可能会跳过辫子的末尾) ,但是除非您要处理数百万个节点,较高的分支因子和严重的不平衡,否则我希望您会很好。

  • Dear
    Dear 回复

    您也可以尝试使用中间性中心度,因为它可以很好地衡量通过节点的最短路径的数量。启动分支或关闭分支的节点之间应具有较高的中间性。这当然是不准确的,因为辫子内部的复杂行为可能导致辫子内部的某些节点也具有较高的中间性,但是我认为这是一种快速的方法(由于已经实现,因此如果您拥有很多节点),可能会产生您期望的结果。