algorithm - 对于图中的每个顶点，找到距离 d 内的所有顶点

Question

在我的特殊情况下，该图表示为邻接表并且是无向和稀疏的，n 可以是数百万，d 是 3。计算 A^d(其中 A 是邻接矩阵)并挑选出非零条目有效，但我想要一些不涉及矩阵乘法的东西。对每个顶点进行广度优先搜索也是一种选择，但速度较慢。

Answer 1

def find_d(graph, start, st, d=0):

    if d == 0:
        st.add(start)
    else:
        st.add(start)
        for edge in graph[start]:
            find_d(graph, edge, st, d-1)

    return st

graph = { 1 : [2, 3],
      2 : [1, 4, 5, 6],
      3 : [1, 4],
      4 : [2, 3, 5],
      5 : [2, 4, 6],
      6 : [2, 5]
    }

print find_d(graph, 1, set(), 2)