修改深度首先用字典搜索

在那里有很多非常好的DFS python实现，例如this one，但它们都不包含成本。我希望能够记录DFS路径的总成本，但此实现将图形表示为集合的字典。修改深度首先用字典搜索

graph = {'A': set(['B', 'C']), 
     'B': set(['A', 'D', 'E']), 
     'C': set(['A', 'F']), 
     'D': set(['B']), 
     'E': set(['B', 'F']), 
     'F': set(['C', 'E'])} 

def dfs(graph, start): 
    visited, stack = set(), [start] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.add(vertex) 
      stack.extend(graph[vertex] - visited) 
    return visited 

dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}

我不认为套可以充分记录成本。所以我觉得将图形表示为词典词典是实现成本的好方法。即：

graph = {'A' : {'C' : 10, 
       'D' : 7} 
       etc.....

我的问题是，如何修改这个算法来使用这种新型的图形？我仍然很不熟悉python语法，所以看到这样的例子确实有帮助。

或者，如果有代表成本更简单的方法，我很开放的建议

编辑：好的，这里是思考它的另一种方式。我怎样才能修改上面的代码，以便它将嵌套字典与集合相似对待？编辑2：我相信我自己解决了它，现在我明白字典的keys（）函数返回一个列表。

来源

2016-09-24 Bob

你最好把这个问题移到[代码评论]（http://codereview.stackexchange.com/） –

我认为你提出的嵌套字典将是一个好主意 - 看看json格式，也许你需要什么。另外，DFS并不是真的与成本有关，所以你应该看看其他的算法实现，比如dijkstra等，它使用成本作为算法的重要部分。 – coder

我知道DFS不使用成本，但它仍然可以记录它。 – Bob

看起来像NetworkX是你在找什么。 DFS包含在软件包中，它的图形实现是你想要的。希望能帮助到你。

来源

2016-09-24 18:05:34 mengg

这很有趣，但由于我仍然在学习python，我认为它会更有用，看看它如何使用默认的python库完成。 – Bob

这是创建图形的非常直观的结构。强烈推荐。 – mengg

修改深度首先用字典搜索

回答

相关问题