python 2 中的密钥是如何存储和访问的？

Question

我正在尝试在 python 中实现 DFS 和 BFS。我有深度优先搜索的代码，它可以工作，我几乎可以理解它。

我不明白的是密钥是如何被访问的。该程序可以选择 G.keys() 中的任何键，但它最终总是选择图中的下一个相邻键。由于我已将图形存储为字典，程序如何知道接下来要选择哪个键。它是随机发生还是有特定原因？请帮助我了解内部工作。

Graph={'A':['B','G','D'],
 'B':['E','F'],
 'C':['F','H'],
 'D':['A','F'],
 'E':['B','G'],
 'F':['B','D','C'],
 'G':['E','A'],
 'H':['C']}


def traverse(G,node,visited):
 visited[node]=True
 print 'node:'+node+
 for other_nodes in G[node]:
  if other_nodes not in visited:
   traverse(G,other_nodes,visited)

def start_traversal(G):
 visited={}
 for node in G.keys():
  if node not in visited:
   traverse(G,node,visited)

start_traversal(Graph)

Answer 1

字典的存储往往是按照其键的哈希值的顺序，尽管这不能保证。您可以看到，在您的特定示例中，哈希值都与字符有关。

>>> for x in 'ABCDEFGH':
    print hash(x)

-269909568
-141909181
-13908798
114091589
242091972
370092359
498092742
626093129

如果需要指定字典的确切顺序，可以使用 OrderedDict。

Answer 2

start_traversal不是选择相邻键的地方。那是 traverse 中的部分，特别是 for other_nodes in G[node]:。由于 G[node] 仅包含相邻节点，因此将迭代所有节点。

for node in G.keys(): 所做的是 select 一个随机节点开始（和后续节点以防万一 G 中有许多断开连接的子图）。

在这种情况下，选择相邻节点与哈希顺序没有任何关系（你永远不应该依赖它）。

Answer 3

首先他们是程序中的一个错误：13 col:19它必须是打印'node:'+节点

如果你想在同一行输出你可以在 node

之后添加一个逗号第二件事字典按键的 ascii 值的排序顺序存储元素

但是在你的程序中发生的事情是在第 20 行节点是 'A' 并且当你尝试遍历它然后在第 14 行中 other_nodes 成为列表中的值之一存储为键 'A' 即 'B' 因为 'B' 也是一个键，那么在另一个步骤中 other_nodes 将是 'E' 然后 "E" 作为 "B" 的键但是它已经在访问中所以它变成 "G" 并且这个过程继续并且直到这个递归结束时所有键都存在于访问列表中所以你的结果是无序的。

python 2 中的密钥是如何存储和访问的？

How are keys stored and accessed in python 2?

python

dictionary

depth-first-search

python-2.7