为networkX图遍历实现DFS

Question

我已经实现了 DFS 以在 networkX 图表中为 this 数据打印出从一个地铁站到另一个地铁站的路径：

def dfs(nxobject, initial, goal, compute_exploration_cost=False, reverse=False):

    frontier = [{'label':initial, 'parent':None}]  
    explored = {initial}
    number_of_explored_nodes = 1 

    while frontier:
        node = frontier.pop() 
        number_of_explored_nodes += 1
        if node['label']==goal:
            if compute_exploration_cost:
                print('number of explorations = {}'.format(number_of_explored_nodes))
            return node

        neighbours = reversed(list(nxobject.neighbors(node['label']))) if reverse else nxobject.neighbors(node['label'])
        for child_label in neighbours:

            child = {'label':child_label, 'parent':node}
            if child_label not in explored:
                frontier.append(child) # added to the right of the list, so it is a LIFO
                explored.add(child_label)      
    return None

import networkx as nx
import pandas as pd

data = pd.read_csv('tubedata.csv',header=None)

edgelist = data.apply(lambda x: (x[0],x[1],x[3]),axis=1).to_list()

G = nx.DiGraph()
G.add_weighted_edges_from(edgelist)

然而，当我调用 dfs 方法时，我不断得到 None:

solution = dfs(G, 'Euston', '"Victoria"')

输出应为：

['Euston', 'WarrenStreet', 'OxfordCircus', 'GreenPark', 'Victoria']

有什么建议吗？谢谢。

Answer 1

删除 '"Victoria"':

上的双引号

>>> dfs(G, 'Euston', 'Victoria')
{'label': 'Victoria',
 'parent': {'label': 'Green Park',
  'parent': {'label': 'Piccadilly Circus',
   'parent': {'label': 'Leicester Square',
    'parent': {'label': 'Covent Garden',
     'parent': {'label': 'Holborn',
      'parent': {'label': 'Russell Square',
       'parent': {'label': "King's Cross St. Pancras",
        'parent': {'label': 'Euston', 'parent': None}}}}}}}}}

但是你可以使用nx.shortest_path:

>>> nx.shortest_path(G, 'Euston', 'Victoria')
['Euston', 'Warren Street', 'Oxford Circus', 'Green Park', 'Victoria']

为networkX图遍历实现DFS

Implementing DFS for networkX graph traversal

python

networkx