Метка глубины первого поиска (Python)

Question

Мне нужно пометить узлы дерева порядком, в котором узлы посещаются во время первого поиска глубины. Я должен реализовать его в Python. Я пытаюсь использовать networkx lib, но до сих пор не знаю, как это сделать. Вы, ребята, знаете, как его использовать? Или я должен попытаться реализовать его сам?

Cheers, GP

Answer 1

Постарайся не реализуют хорошо знать алгоритмы, если они существуют в библиотеке. Там у вас есть ссылка на документ основных алгоритмов обхода.

http://networkx.github.io/documentation/latest/reference/algorithms.traversal.html

Удачи :)

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 
>>>