将字典中的键添加到列表中

Question

我需要一些有关代码的帮助。遍历numpy数组后，我得到了一个字典，您可以在其中查看哪个元素与谁连接。 BFS方法将其整理出来并放入访问列表中。我需要弄清楚如何将密钥放入队列。有一个开始元素。但并非所有键，只是彼此连接的键。如您所见，数组中有两个图形区域。

import numpy as np

def graph():
    a = np.array([
        [0,  0,  0,  0,  0,  0,  0,  0,  0],
        [0,  0, 16, 12, 21,  0,  0,  0,  0],
        [0, 16,  0,  0, 17, 20,  0,  0,  0],
        [0, 12,  0,  0, 28,  0, 31,  0,  0],
        [0, 21, 17, 28,  0, 18, 19, 23,  0],
        [0,  0, 20,  0, 18,  0,  0, 11,  0],
        [0,  0,  0, 31, 19,  0,  0, 27,  0],
        [0,  0,  0,  0, 23, 11, 27,  0,  0],
        [0,  0,  0,  0,  0,  0,  0,  0,  0]],
        )

    graph = {}

    for r in range(len(a)):

        for c in range(len(a)

            if a[r, c] > 0:
                d = [r-1, c+1, r+1, c-1]

                if a[d[0], c] > 0 or a[r, d[1]] or a[d[2], c] or a[r, d[3]]:
                    graph[a[r, c]] = []
                    if a[d[0], c] > 0:
                        graph[a[r, c]].append(a[d[0], c])
                    if a[r, d[1]] > 0:
                        graph[a[r, c]].append(a[r, d[1]])
                    if a[d[2], c] > 0:
                        graph[a[r, c]].append(a[d[2], c])
                    if a[r, d[3]] > 0:
                        graph[a[r, c]].append(a[r, d[3]])
return(graph)

def bfs（图形，开始）：

queue = [start]
visited = [start]

while queue:

    for neighbour in graph.keys():

        if neighbour in queue:
            visited.append(graph[neighbour])
            queue.pop(0)

result = 0
print(queue)
print(visited)

bfs(graph(), 16)

Answer 1

我修改了bfs方法，请参见下文。基本上，更新后的代码使用双端队列逐层遍历图，该双端队列为FIFO提供了更高的效率。

from collections import deque
def bfs(graph, start):
    deq = deque([start])
    visited = [start]
    while deq:
        for _ in range(len(deq)):
            node = deq.popleft()
            for neighbour in graph[node]:
                if neighbour not in visited:
                    visited.append(neighbour)
                    deq.append(neighbour)
    print(visited)

输出：[16、12、21、17、28、20]