1

我有一个有向图如下：

在此处输入图像描述

我用networkx创建它并用ipycytoscape绘制它。该图是有向图。所有的边都有一个且只有一个方向。

问题是如何从特定节点找到该节点和节点一之间的所有路径。由于该图是有向的，因此只有所有边的方向都相同的路径才有效。在图中，6 和 1 之间有两条路径。乍一看，关于蓝色路径的事情是可能的，但在这种情况下，边缘 4-6 的方向与其他方向不同。

nodes = [1,2,3,4,5,6,7,8]
children = [[2],[3,4],[5,6],[6,7],[8],[],[8],[]]
G2 = nx.Graph()
G2.add_nodes_from(nodes)
for i,child in enumerate(children):
    for c in child:
        G2.add_edge(i+1, c)
cyto = CytoscapeWidget()
cyto.graph.add_graph_from_networkx(G2, directed=True)
cyto.set_layout(name='dagre', nodeSpacing=10, edgeLengthVal=10)
display(cyto)

我正在寻找的是网络方法，它给了我两个节点之间的路径列表。伪代码：

for node1 in G.nodes:
for node2 in G.nodes:
list_of_paths = networks_method???(node1,node2)

注意：图表是这样的，箭头（方向性）总是从较小的数字到较高的数字。2 可以是 3 的父级，但不能反过来。

4

1 回答 1

2

通常，寻找“所有路径”的问题可能是一个指数任务并产生无限路径。但是，您从有向图的一个特殊子类中描述了一个图：有向无环图 (DAG)。DAG 是一个G没有循环的有向图，即，对于不存在路径 u->v_1....v_n->u 的节点u。G由于您说所有边都从较小的数字变为较大的数字，因此您的图是 DAG。

在这种情况下，修改后的 DFS 搜索将为您提供所有可能的路径。“DAG 中的所有路径”主题已在以下问题中讨论过

于 2021-07-05T07:22:40.683 回答