我可能想多了,遗漏了一些明显的东西,但我想知道我可以使用哪种 NetworkX 算法来实现以下目标:
给定一个有向图,例如:
以及节点列表,例如:Q1、Q2
找到所有连接到 Q1 和 Q2 的节点(或者换句话说,它们的子节点),结果如下:
哪种算法可以做到这一点?
我可能想多了,遗漏了一些明显的东西,但我想知道我可以使用哪种 NetworkX 算法来实现以下目标:
给定一个有向图,例如:
以及节点列表,例如:Q1、Q2
找到所有连接到 Q1 和 Q2 的节点(或者换句话说,它们的子节点),结果如下:
哪种算法可以做到这一点?
第一种方法是使用列表,从您的节点开始访问每个节点的前任并将其放入列表中,以这种方式与您找到的节点一起构建一棵树。
另一种方法是在反转边缘的图上使用访问(DFS 或 BFS)。
考虑以下示例,其中我从节点“Q1”开始构建bfs 树。
import networkx as nx
g = nx.DiGraph()
g.add_edges_from([("M1","Q1"),("I1","M1"),("I2","M1"),("I3","M1"),("I3","M2"),("M2","Q2")])
#creating a graph with the edges reversed
g2 = nx.DiGraph()
g2.add_edges_from([(v,u) for (u,v) in g.edges()])
t = nx.bfs_tree(g2, "Q1")
for (u,v) in t.edges():
t.remove_edge(u,v)
t.add_edge(v,u)
print(t.nodes(),t.edges())
# ['Q1', 'M1', 'I1', 'I2', 'I3'] [('M1', 'Q1'), ('I1', 'M1'), ('I2', 'M1'), ('I3', 'M1')]