如何在 python 中使用 BFS 获取所有节点的所有邻居

Question

我有一个图表：

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

我想获取此图中每个节点的所有不同邻居的组合。结果将是这样的：

['A','B','C','D','E']
['F','G']

我尝试了 BFS 并使用循环遍历所有节点，它有效但想象图很大并且需要很长时间。你有什么建议吗？

这是我的代码：

# define bfs
def bfs(graph, node):
# node is the starting position
# graph is the graph in dictionary format
visited = []
queue = []
visited.append(node)
queue.append(node)
while queue:
    s = queue.pop(0)
    for x in graph[s]:
        if x not in visited:
            visited.append(x)
            queue.append(x)
return visited

# define is_exist_in_list
def is_exist_in_list(target, element):
for line in target:
    if element in line:
        return True
return False

res = []
for i in G.nodes:
    if is_exist_in_list(res, i) == False:
        tt = bfs(G, i)
        tt.sort()
        if tt not in res:
            res.append(tt)

Answer 1

在我看来，您正在与 networkx 合作。如果是这样，你可以这样做：

import networkx as nx

G = nx.Graph((key, value) for key in G for value in G[key])
results = list(nx.connected_components(G))

结果：

[{'E', 'D', 'A', 'B', 'C'}, {'F', 'G'}]

如果您想根据提供的字典自己构建它，我不会使用列表，而是使用集合：

results = []
stack = set(G)
while stack:
    node = stack.pop()
    result = {node}
    check = {node}
    while check:
        node = check.pop()
        for child in G.get(node, set()) - result:
            result.add(child)
            check.add(child)
            stack.discard(child)
    results.append(result)

您的样本结果 G：

[{'B', 'E', 'A', 'C', 'D'}, {'G', 'F'}]

如何在 python 中使用 BFS 获取所有节点的所有邻居

how to get all neighbors of all nodes by using BFS in python

python

breadth-first-search