python - 距起始顶点一定距离内的顶点数

Question

我正在研究一个关于法官的问题，该问题询问如何找到距离它一定距离内的顶点数。必须对图上的所有顶点执行此操作。完整问题规范可见 here.我有一些 Python 代码来解决这个程序，但是它太慢了。

import sys, collections
raw_input = sys.stdin.readline
n, m, k = map(int, raw_input().split())
dict1 = collections.defaultdict(set)
ans = {i:[set([i])for j in xrange(k)]for i in xrange(1, n+1)}

for i in xrange(m):
    x, y = map(int, raw_input().split())
    dict1[x].add(y)
    dict1[y].add(x)

for point in dict1:
    ans[point][0].update(dict1[point])

for i in xrange(1, k):
    for point in dict1:
        for neighbour in dict1[point]:
            ans[point][i].update(ans[neighbour][i-1])

for i in xrange(1, n+1):
    print len(ans[i][-1])

我的代码所做的是它最初创建一组点，这些点是每个顶点的直接邻居(距离为 0 到 1)。之后，它从所有先前找到的邻居的邻居(距离为 2)为每个顶点创建一组新的邻居。然后它继续这样做，创建一组新的邻居并增加距离直到达到最终距离。有没有更好的方法来解决这个问题？

Answer 1

有很多又好又快的解决方案。

其中之一(不是最快，但足够快)是使用 BFS 算法达到距离 K。只需运行 bfs，当距离超过 K 时，它不会将所有顶点的邻居添加到队列中。 K 是运动规范中的参数。