如何從給定的一組節點等距離地查找圖中的所有節點？

Question

如果你有一個簡單的無向圖G(V,E)和F這是V的子集。你怎麼能找到一些節點v，使得從F到v的每個節點的距離是相同的，距離是最小的？如果沒有v，請返回None。我被告知這可以在O(|V|+|E|)的複雜性。

假設所有邊緣的距離爲1.

任何人都可以解釋如何做到這一點嗎？僞代碼也有幫助。

Answer 1

的解決方案是類似於BFS，但有一點變化：

1. 開始使用S = F爲F節點標記。

2. 查找| S |在S中的每個元素設置距離爲1（所有這些集應該包含未標記的節點）。如果這些集合的交集非空，則找到候選者。

3. 以| S |在S'中設置以上並標記這些節點。如果S'爲空，則返回'無'。

4. 返回到步驟2。

假設所有該組操作採取恆定時間，則算法的複雜度是相同BFS其是O（| V | + | E |）。

現在推理設置操作的複雜性。我的推理是集合運算不會增加複雜性，因爲步驟2和3中的並集和交集操作可以合併以花費時間O（| S |），並且由於在每一步中S與以前迭代中的S不同，設置操作的整體複雜度將是O（| V |）。

Answer 2

下面是一個僞代碼算法，試圖添加註釋來解釋它是如何工作的。

declare explored // a table of all the vertices that can keep track of one number (distance, initialized to -1) and a list of vertex references (origins, initialized to null) 
to_explore = S // fifo queue of vertices to explore 

while (to_explore not empty) { 
    pop vertex v from to_explore 
    current_distance = explored[v].distance 
    current_origins = explored[v].origins 
    for (vertex n, neighbor of v) { 
     if (explored[n].origins contains v) 
      continue // we just hit a loop and we're only interested in shortest distances 
     if (explored[n].distance == -1) { // first time we come here 
      explored[n].distance = current_distance+1 
      explored[n].origins = current_origins 
      push n to to_explore 
      continue 
     } 
     if (explored[n].distance != current_distance+1) { 
      continue // we are merging path from another node of S but different distance, cannot lead to any solution 
     } 
     // only case left is explored[n].distance == current_distance+1 
     // so we've already come here from other place(s) in S with the same distance 
     add/merge (without duplicates) origins to explored[n].origins 
     if (explored[n].origins = S) // maybe compare the size is enough? 
      return n // we found a solution 
     // if not , we just continue our exploration, no need to add to the queue since we've already been through here before 
    } 
} 

的想法是，與FIFO隊列中，我們將探討一切，在距離1從集合S，如果我們不能找到任何解決方案在那裏，一切都在距離2 ...等等。所以我們我會先找到最短的距離。

我對複雜性並不完全確定，但我認爲在最糟糕的情況下，我們只探索每個頂點和每個邊緣一次，以便給出O(|E| + |V|)。但在某些情況下，我們多次訪問同一個頂點。儘管這並沒有增加探索的路徑，但我不確定是否應該有一個因素| S |某處（但如果那只是認爲像一個常數，那麼沒關係......）

希望我沒有錯過任何東西。很顯然，我沒有測試任何這.... :)

編輯（回覆評論）

請問像這樣的圖你的代碼的工作？ （a，b），（a，c），（a，d） ，（b，e），（c，e），（d，e）和我的F = {b，c，d} 。說，你用a開始你的 bfs。我懷疑，最後，源數組將只有{a} ，因此代碼將返回None。 - 大師Devanla

在這種情況下，會出現以下情況：

to_explore is initialized to {b,c,d} 
//while (to_explore not empty) 
pop one from to_explore (b). to_explore becomes {c,d} 
current_distance=0 
current_origins={b} 
//for (neighbors of b) { 
handling 'a' as neighbor of b first 
explored[a].distance=1 
explored[a].origins={b} 
to_explore becomes {c,d,a} 
//for (neighbors of b) 
handling 'e' as next neighbor of b 
explored[e].distance=1 
explored[e].origins={b} 
to_explore becomes {c,d,a,e} 
//while (to_explore not empty) 
pop one from to_explore (c). to_explore becomes {d,a,e} 
current_distance=0 
current_origins={c} 
//for (neighbors of c) 
handling 'a' as neighbor of c first 
explored[a].distance is already 1 
explored[a].origins={b,c} 
to_explore already contains a 
//for (neighbors of c) { 
handling 'e' as next neighbor of b 
explored[e].distance is already 1 
explored[e].origins={b,} 
to_explore already contains e 
//while (to_explore not empty) 
pop one from to_explore (d) 
current_distance=0 
current_origins={d} 
//for (neighbors of d) 
handling 'a' as neighbor of d first 
explored[a].distance is already 1 
explored[a].origins={b,c,d} 
that matches F, found a as a solution.