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

对于大图中的每个点，我试图创建一个列表，其中包含距离起始节点n的未访问节点的数量。一个例子的输出是： [1,3,6] 这意味着在距离0有起始节点本身，在距离1有3个新（未知）节点等计算图中每个节点的距离为n的未访问节点

如果只有一个起点，这是相当简单：您只需在广度优先搜索的基础上增加一个外壳计数器。当我必须为我的图中的每个节点执行此操作时，问题就开始了。由于我的图形很大（> 100000个节点），因此对于每个点执行上述例程变得相当缓慢。

我优化这个第一次尝试以检查列表节点a可以从a所有邻居的列表构造，但到目前为止，我已经没有运气，部分原因是由于在图中的循环。我希望你们中的一些人可能有一些不错的想法，可能涉及一些我可以缓存的附加信息。

我的问题：有没有一种方法来优化这样的搜索，如果你知道你将不得不这样做每节点？

2013-04-09 Ben Ruijl

[所有最短路径问题（http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm）基本上是你的距离和计数分组后寻求的东西，你也许可以真的比O（| V |^3）好得多。 – Nuclearman 2013-04-09 19:41:40

我的广度优先搜索是O（| E |），在我的情况下它等于O（| V |）。我必须为每个节点都做，所以我目前的复杂度是O（| V |²）。我现在正在使用并行计算来加速这个过程，但其他建议是最受欢迎的！ – 2013-04-11 12:03:19

它应该仍然是O（| V | * | E |），在最坏的情况下它是O（| V |^3）。但是，如果你在说| V |接近| E |，那么考虑到有可能需要列出最短路径的顶点的可能组合O（| V |^2），那么可能没有太多的工作要做。尽管如果大多数顶点的度数为2或更小，那么简单地列出最长路径（或足够长的路径）并从中提取最短路径可能是实用的。 – Nuclearman 2013-04-11 23:49:05

似乎不太可能有一个小于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}

这似乎是正确的。另外，在我的笔记本电脑上运行带有100000个节点的距离为100的简单拓扑大约需要一分钟。当然，如果你有一个密集的图表（如fullE），这将炸毁。

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

来源

2015-05-05 22:45:39 mitchus

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

回答

相关问题