1

提前致谢。我有一个由 T-SQL 构建的 JSON 格式的图表。像下面这样：

  • “NodeId”是节点的Id
  • “N”是相关节点（id）

如何在 Python 中遍历所有相对（在任何级别）到图的请求节点？

[{"NodeId":"1","N":"2"},
{"NodeId":"1","N":"3"},
{"NodeId":"3","N":"5"},
{"NodeId":"5","N":"6"},
{"NodeId":"2","N":"4"},
{"NodeId":"9","N":"7"}]

预期结果应按级别（任何格式）列出所请求节点的所有相关节点。一个输出列表，如：

输入（节点 ID）<<“1”：

输出 >> ["2", "3", "5", "4", "6"]

4

2 回答 2

0

您可以使用“深度优先搜索”或“广度优先搜索”。

如果你想要“Level Order”，那么设置第二个参数depth=False。

from collections import deque

def get_nodes(nodes, start_node, depth=True):
    graph = {}

    for node in nodes:
        graph.setdefault(node['NodeId'], []).append(node['N'])

    seen = set()
    d = deque()

    d.extend(graph[start_node])

    while d:
        cur_node = d.pop() if depth else d.popleft()

        if cur_node in seen:
            continue

        seen.add(cur_node)
        yield cur_node
        d.extend(graph.get(cur_node, []))

nodes = [{"NodeId":"1","N":"2"}, {"NodeId":"1","N":"3"}, {"NodeId":"3","N":"5"}, {"NodeId":"5","N":"6"}, {"NodeId":"2","N":"4"}, {"NodeId":"9","N":"7"}]

输出（定向）

print(list(get_nodes(nodes, '1', True)))
['3', '5', '6', '2', '4']
print(list(get_nodes(nodes, '1', False)))
['2', '3', '4', '5', '6']

如果图是无向的，则添加

graph.setdefault(node['N'], []).append(node['NodeId'])到for循环。

像这样

for node in nodes:
    graph.setdefault(node['NodeId'], []).append(node['N'])
    graph.setdefault(node['N'], []).append(node['NodeId'])

现在输出看起来像（无向）

print(list(get_nodes(nodes, '1', True)))
['3', '5', '6', '1', '2', '4']
print(list(get_nodes(nodes, '1', False)))
['2', '3', '1', '4', '5', '6']
于 2021-04-28T10:48:44.890 回答
0

您可以使用递归生成器函数：

d = [{'NodeId': '1', 'N': '2'}, {'NodeId': '1', 'N': '3'}, {'NodeId': '3', 'N': '5'}, {'NodeId': '5', 'N': '6'}, {'NodeId': '2', 'N': '4'}, {'NodeId': '9', 'N': '7'}]
def get_nodes(n, s = []):
  yield n
  for i in d:
     if i['NodeId'] == n and i['N'] not in s:
        yield from get_nodes(i['N'], s+[n])

_, *result = get_nodes('1')

输出：

['2', '4', '3', '5', '6']
于 2021-04-28T16:10:14.563 回答