深度优先搜索标记（Python）

Question

我需要按照深度优先搜索访问节点的顺序为树的节点打上标签。我需要在Python中实现此功能。我正在尝试使用networkx库，但仍然不知道如何实现它。你们有任何关于如何使用它的想法吗？或者我应该自己实现它吗？

祝好，GP

- gpestana

Answer 1

尽量不要实现已经存在于库中的众所周知的算法。你可以在这里找到基本遍历算法的文档链接。 http://networkx.github.io/documentation/latest/reference/algorithms.traversal.html 玩得开心 :)

- Nasgar

Answer 2

如果你创建了一个新的图形，

>>> import networkx as nx

>>> g = nx.DiGraph()

然后你添加一些边缘，

>>> g.add_edges_from([(0,1),(1,2),(0,3),(3,4),(3,5),(5,6)]) # etc

你可以使用 dfs_edges() 来遍历并查看遍历顺序。

>>> nodes = nx.dfs_edges(random_g, node_) # This creates an edges iterator
>>> nodes.next()
(0, 1)
>>> nodes.next()
(1, 2)
>>> nodes.next()
(0, 3)
>>>

如果你想的话，可以从调用.next()中获取输出，以确定正在访问的节点。

例如，（不包括第一个节点0），

>>> for n in nodes:
...     print n[1]
... 
1
2
3
4
5
6
>>> 

- HeyWatchThis