如何在有向树图中找到度数 > 2 的顶点之间的路径？

Question

我没有接受过图论方面的培训，所以我的术语很差。我有一个具有“冗余节点”的有向树图。我将“冗余节点”定义为树图中度数 = 2 的节点。我想找到一种有效的方法来 return 所有非冗余节点之间的所有路径，最好使用 NetworkX (Python) 工具。这个非常简单的图形演示了我正在努力实现的目标：

鉴于此图，我想 return 三个路径（p1、p2 和 p3）代表 1->4、5->4 和 4->7 之间的连接.

我可以编写一个算法来“手动”执行此操作，从某种意义上说，我从度数 = 1 的节点开始，沿着图“走”，直到我碰到另一个非度数 = 2 的节点。但是，我怀疑已经有一种形式化的方法可以进行这种分析，但我似乎无法弄清楚。

为了了解更多上下文，我的图表更大更复杂，因为它们代表了河流网络，如下所示：

但它们总是树，没有环。

Answer 1

不，恐怕你已经找到了最有效的方法来做你的迷你路径。您可以通过从汇合节点向后工作来稍微加快处理速度，但这就是您可以改进的全部内容。与简单地查找源节点（您仍然必须这样做）相比，这样做可以让您更有效地删除中间节点。然而，该算法并不那么简单。现在，我建议您坚持使用现有的简单设计。

将所有节点放入集合to_visit。
而 to_visit 不为空：
- 节点=to_visit.pop()
- if node has degree 1: # 源节点：找到汇合路径
  - 跟踪路径，直到遇到度 > 2 的节点。
  - 从to_visit中删除所有中间节点。
  - 发出路径。

Answer 2

LOOP over all nodes
    calculate degree
    IF degree == 2
       add to vector deg2
LOOP over all nodes in deg2 to get src
    LOOP over all nodes in deg2 starting at src+1 to get dst
        find path from src to dst ( dijsktra algorithm )

如何在有向树图中找到度数 > 2 的顶点之间的路径？

How to find the paths between vertices with degree > 2 in a directed tree graph?

python

tree

graph

vertices

networkx