在 NetworkX DiGraph 中识别源节点之后具有两个邻居节点的第一个节点。

Question

我正在使用NetworkX实现一个DiGraph。源节点是红色节点。我需要找到从红色节点开始第一个有两个邻居（在“流动方向”上）的节点。如果我遍历所有节点，似乎是随机的。希望有人能帮忙！

- lars111

---

你不需要迭代遍历所有节点，你可以从源节点开始递归遍历其后继节点，直到找到你想要的节点。 - Corley Brigman

Answer 1

您可以使用successors方法。如果您的DiGraph实例称为G，并且红色节点的索引为0，则可以采用广度优先搜索方法，如下所示：

import networkx as nx

# Construct graph from example image, all edges pointing away from source
G = nx.DiGraph()
G.add_path([0,1,2,3,4])
G.add_path([1,5])
G.add_path([3,6])
G.add_path([2,7,8])

# Find first with 2 neighbors
neighbors = G.successors(0)
for n in neighbors:
    nneighbors = set(G.successors(n))
    if len(nneighbors) == 2:
        print "Found", n
        break
    neighbors.extend(nneighbors)

neighbors方法在networkx的DiGraph中与successors方法是可互换的。如果您想为每个节点计算其入边数量，请在计算时将G.predecessors(n)添加到nneighbors集合中，但记住在扩展neighbors时不要将其包括在该集合中。代码如下：

# Find first with 2 neighbors
neighbors = G.successors(0)
for n in neighbors:
    if len(G.predecessors(n)+G.successors(n)) == 2:
        print "Found", n
        break
    nneighbors = set(G.successors(n))
    neighbors.extend(nneighbors)

- Ulf Aslak

---

对于DiGraph，如果使用显式的“successors”和“predecessors”版本，则会减少很多混淆。 - Corley Brigman

在你的回答中使用“广度优先搜索”这个词是值得的。 - Joel