计算图中每个节点到距离n的未访问节点数

Question

针对大图中的每个节点，我正在尝试创建一个列表，其中包含距离起始节点n的未访问节点数。例如，输出结果为：[1,3,6]，这意味着在距离0处有起始节点本身，在距离1处有3个新的（未探索的）节点等等。

如果只有一个起点，这很容易：您只需在广度优先搜索之上增加一个外壳计数器即可。当我不得不为我的图中的每个节点执行此操作时，问题就开始了。因为我的图很大（> 100000个节点），所以为每个点执行上述例程变得相当缓慢。

我优化的第一步是检查是否可以从所有邻居的列表构建节点a的列表，但到目前为止我没有成功，部分原因是由于图中的循环。我希望你们中的一些人可能有一些好主意，也许涉及一些我可以缓存的附加信息。

我的问题是：如果您知道必须为< strong>每个节点执行此搜索，是否有一种优化搜索的方法？

- Ben Ruijl

---

“全源最短路径问题”基本上是通过距离分组和计数来寻求解决方案，你可能无法比O（|V|^3）更好地解决它。” - Nuclearman

我的广度优先搜索是O（|E|），在我的情况下等于O（|V|）。我必须对每个节点执行此操作，因此当前的复杂度为O（|V|²）。我现在正在使用并行计算来加速该过程，但欢迎提出其他建议！ - Ben Ruijl

它仍然应该是O（| V | * | E |），在最坏的情况下是O（| V | ^ 3）。但是，如果您说| V | 接近| E |，那么考虑到需要列出最短路径的可能组合有O（| V | ^ 2），则可能没有更多的选择。尽管如此，如果大多数顶点的度数小于或等于2，则只需列出最长路径（或足够长的路径），并从中提取最短路径可能是实际的。 - Nuclearman

为什么称它们为未访问节点？如果我理解正确，您想知道给定一个节点，有多少个节点与其距离为D，对吗？ - mrk

你需要获取近似值还是精确值？ - templatetypedef

这个图是简单图吗？假设从节点A到节点B有两条距离分别为1和3的路径，我们应该怎么办？ - shole

Answer 1

看起来不太可能有一个小于O(n*|V|^2)的解决方案，所以这里提供了一种用Python实现的方法，看起来还不错。

# some basic topologies
def lineE(N): 
  return(set((i,i+1) for i in range(N-1)))

def ringE(N):
  return(lineE(N).union([(0,N-1)]))

def fullE(N):
  return(set([(i,j) for i in range(N) for j in range(i)]))

# propagate visitors from x to y
def propagate(V, curr, x, y, d):
  nexty = set()
  for cx in curr[x]:
    if not cx in V[y]["seen"]:
      V[y]["seen"].add(cx)
      V[y]["foaf"][d] = V[y]["foaf"].get(d,0) + 1
      nexty.add(cx)
  return(nexty)

# run for D iterations
def mingle(N, E, D):
  V = dict((i, {"seen":set([i]), "foaf":{0:1}}) for i in range(N))
  curr = dict((i, set([i])) for i in range(N))
  for d in range(1, min(D+1, N)):
    next = dict((i, set()) for i in range(N))
    for (h, t) in E:
      next[t] = next[t].union(propagate(V, curr, h, t, d))
      next[h] = next[h].union(propagate(V, curr, t, h, d))
    curr = next
  return(V)

使用 10 个节点和距离为 3 进行尝试，

N=10
D=3
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N)), ("full", fullE(N))]:
  V = mingle(N, E, D)
  print "\n", topology
  for v in V:
    print v, V[v]["foaf"]

我们得到

line
0 {0: 1, 1: 1, 2: 1, 3: 1}
1 {0: 1, 1: 2, 2: 1, 3: 1}
2 {0: 1, 1: 2, 2: 2, 3: 1}
3 {0: 1, 1: 2, 2: 2, 3: 2}
4 {0: 1, 1: 2, 2: 2, 3: 2}
5 {0: 1, 1: 2, 2: 2, 3: 2}
6 {0: 1, 1: 2, 2: 2, 3: 2}
7 {0: 1, 1: 2, 2: 2, 3: 1}
8 {0: 1, 1: 2, 2: 1, 3: 1}
9 {0: 1, 1: 1, 2: 1, 3: 1}

ring
0 {0: 1, 1: 2, 2: 2, 3: 2}
1 {0: 1, 1: 2, 2: 2, 3: 2}
2 {0: 1, 1: 2, 2: 2, 3: 2}
3 {0: 1, 1: 2, 2: 2, 3: 2}
4 {0: 1, 1: 2, 2: 2, 3: 2}
5 {0: 1, 1: 2, 2: 2, 3: 2}
6 {0: 1, 1: 2, 2: 2, 3: 2}
7 {0: 1, 1: 2, 2: 2, 3: 2}
8 {0: 1, 1: 2, 2: 2, 3: 2}
9 {0: 1, 1: 2, 2: 2, 3: 2}

full
0 {0: 1, 1: 9}
1 {0: 1, 1: 9}
2 {0: 1, 1: 9}
3 {0: 1, 1: 9}
4 {0: 1, 1: 9}
5 {0: 1, 1: 9}
6 {0: 1, 1: 9}
7 {0: 1, 1: 9}
8 {0: 1, 1: 9}
9 {0: 1, 1: 9}

看起来是正确的。此外，在我的笔记本电脑上运行距离100的简单拓扑结构，有100000个节点大约需要一分钟的时间。当然，如果你有一个密集的图形（如fullE），这将会爆炸。

N=100000
D=100
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N))]:
  V = mingle(N, E, D)

- mitchus