使用 Networkx (Python) 进行图遍历

我正在使用 Networkx 来管理依赖关系图。 假设我有这个图，每个字母代表一个服务器

>>> G = nx.Graph()
>>> G.add_edge("A","B")
>>> G.add_edge("A","H")
>>> G.add_edge("H","C")
>>> G.add_edge("B","C")
>>> G.add_edge("B","D")

           A
         /   \
       H       B
     /        /  \
   C         C     D 

所以在这里我们可以看到，在启动 A 之前，我们需要启动 H 和 B，要启动 H，我们需要启动 C，然后启动 B，我们需要启动 C 和 D

通过摆弄 Networkx，我发现我可以通过 dfs 遍历来实现

print nx.dfs_successors(G,"A")
{A:[H,B], H:[C], B:[D] }

但我对这种方法有疑问。正如你所看到的，当树中有两个相同的字母时，Networkx 只选择将其中一个放入最终结构中（这是正确的）但我需要完整的结构 如何强制 Networkx 添加结构 B:[D,C] ？

我想通过这样做来精确说明

>>> nx.dfs_successors(G,"B")
{'B': ['C', 'D']}

所以一切都是“内部”正确的，只是 dfs_successors 没有按照我希望的方式显示它。

谢谢

使用您的代码，您的图表不会按您的预期显示。如果你这样做：

import pylab as p
import networkx as nx

G = nx.Graph()
G.add_edge("A","B")
G.add_edge("A","H")
G.add_edge("H","C")
G.add_edge("B","C")
G.add_edge("B","D")

nx.draw(G)
p.show()

you will see your graph as:

这是由于以下逻辑G.add_edge("A", "B"):

1. If G没有id为“A”的节点，添加它。
2. If G没有id为“B”的节点，添加它。
3. 用新边将“A”连接到“B”。

因此，您只创建五个节点，而不是如图所示的六个。

EditNetworkx 可以将任何哈希值作为节点的值，并且在图中它使用 str(node) 来标记每个圆。因此，我们可以简单地定义我们自己的 Node 类（您可能想将其称为 Server？）并赋予它所需的行为。

import pylab as p
import networkx as nx


class Node(object):
    nodes = []

    def __init__(self, label):
        self._label = label

    def __str__(self):
        return self._label

nodes = [Node(l) for l in ["A","B","C","C","D","H"]]
edges = [(0,1),(0,5),(5,2),(1,3),(1,4)]

G = nx.Graph()
for i,j in edges:
    G.add_edge(nodes[i], nodes[j])

nx.draw(G)
p.show()

gives us and so what you wanted.