algorithm - 从图形中获取主线

Question

我面临的问题需要某种算法，该算法允许我从图表中获取主线。主线基本上是一个支线网络。在图表上，它将是提供子节点的主节点。下图说明。

所以上图中的主线是 1、2、3、4、5。每个节点都包含一个属性，即连接节点的列表；所以数字 3 将包含 2、4 和 10。我开始考虑首先我应该摆脱有一个连接到它们的节点，但这也会给我留下一些不需要的节点，因此如果我要删除 6 , 7, 8 ,9, 11, 13, 12 我仍然有一个不需要的节点 10。

对于那些不了解馈线网络是什么的人来说，它基本上是一堆结构，检修孔，手孔，机柜，它们承载来自根结构的信号 1通过 2、3、4 和 5 将其分发到区域，直到到达客户。 6, 7, 8, 11, 13, 12, 9.至于10，它是子井结构，根本不属于主网，因为它分布在支线内。现在我知道那些是什么，但在代码中。这些只不过是一堆包含它们所连接的对象。没有类型什么都没有。

Answer 1

根据您给出的部分答案，我认为添加另一个属性将为您提供解决方案。

到目前为止，你有 1、2、3、4、5 和 10。

问题是 10，正如我们所知，不应该是馈线网络的一部分(因为它是一个分支)。

如果你回头看，你可以看到，对于除 10 个节点之外的所有节点，只有一条从节点到源的路径和一条从节点到目的地的路径(你通过你的进程从队列中选择的最后一个节点)没有任何边缘被访问两次。

例如:

1.) 3->2->1(来源)& 3->4->5(目的地)

2.) 4->3->2->1(来源)& 4->5(目的地)

但是在 10 的情况下，一条边将被访问两次。

如，

10->3->2->1 & 10->3->4->5

在这里，如您所见，边 10-3 被访问了两次，这在其他节点的情况下不会发生。

通过这个过程，任何不属于馈线网络的节点都将被丢弃。

根据提供的信息，这将给出正确的解决方案。