return python 文件中的节点数，路径长度

Question

我在项目的最后一个问题 python 中遇到了一道难题。

假设您得到了这样一个文件：

1 2
2 3
3 4

如果节点 1 通过边链接到节点 2，则 2 可通过长度为 1 的路径从 1 访问：1-2
如果 1 链接到 2 本身到 3 本身链接到 4 那么 4 可以通过长度为 4 的路径从 1 访问：1-2-3-4
我想return默认情况下从给定节点通过长度为 3 的路径可访问的节点数

感谢您的建议和帮助!!!!

编辑：

def bfs(graph, start_node, distance):
    if distance == 0:
        return [start_node]
    visited = []
    queue = []
    nodes_at_dist = []

    level = 0
    visited.append(start_node)
    queue.append((start_node, level))

Answer 1

首先，我们重建数据结构以简化查找，即哪些节点是可达的。我假设我们的图是无向的。

graph = [(1, 2), (2, 3), (3, 4), (1, 4), (2, 6), (6, 7)]

# we restructure our input to simplify the lookup
graph_dict = {}
for n1, n2 in graph:
    if n1 not in graph_dict:
        graph_dict[n1] = set()
    if n2 not in graph_dict:
          graph_dict[n2] = set()
    graph_dict[n1].add(n2)
    graph_dict[n2].add(n1)

因此，我们有一个dict，其中键是所有现有节点，对应的值是直接连接的所有节点的集合：

{1: {2, 4}, 2: {1, 3, 6}, 3: {2, 4}, 4: {1, 3}, 6: {2, 7}, 7: {6}}

下一部分本质上是我们的方法，它找到关于固定距离的可达节点：

def bfs(graph_dict, start_node, distance):
    # We reached the end and return the current node
    if distance == 0:
        return {start_node}
        
    # We look-up all nodes which are reachable with one step
    reachable = graph_dict[start_node]
        
    # Now we iterate through this set and call our method again (recursively)
    result=set()
    for node in reachable:
        tmp=bfs(graph_dict, node, distance-1)
        result=result.union(tmp)
    return result

示例输出 1：距离=2，start_node=1

{1, 3, 6}

请注意，“1”在我们的结果集中，因为我们可以走 1-2-1（两步）。

示例输出 2：距离=3，start_node=1

{2, 4, 7}

请注意，“2”在我们的结果集中，因为我们可以走 1-2-1-2（三步）。

return python 文件中的节点数，路径长度

return the number of nodes in a python file by a path of length

python

graph

edges