Come trovare tutti i nodi in un grafico equidistante da un determinato set di nodi?

Question

Se si dispone di un semplice grafo non orientato G(V,E) e F, che è un sottoinsieme di V. Come si può trovare qualche nodo v in modo tale che la distanza da ogni nodo in F a v sia la stessa e le distanze siano ridotte al minimo? E basta restituire None se non c'è v. Mi è stato detto che questo può essere fatto nella complessità O(|V|+|E|).

assumere tutti i bordi sono di distanza 1.

qualcuno può spiegare come questo può essere fatto? Anche uno pseudo-codice sarebbe d'aiuto.

Answer 1

La soluzione è simile a BFS, ma con un piccolo cambiamento:

1. Iniziare con S = F con nodi F marcata.

2. Trova | S | imposta con distanza 1 da ciascun elemento in S (tutti questi set dovrebbero contenere nodi non marcati). Se l'intersezione di questi insiemi non è vuota, viene trovato il candidato.

3. Prendere l'unione di | S | imposta sopra in S 'e segna questi nodi. Se S 'è vuoto, restituire' Nessuno '.

4. Ritorna al passaggio 2.

Supponiamo tutte le operazioni impostati richiedono tempo costante, allora la complessità dell'algoritmo è stessa BFS che è O (| V | + | E |).

Ora ragionare sulla complessità delle operazioni di set. Il mio ragionamento è che le operazioni impostate non aumentano la complessità in quanto le operazioni di unione e intersezione nei passaggi 2 e 3 possono essere combinate per richiedere il tempo O (| S |), e poiché in ogni fase S è diverso da S nelle iterazioni precedenti , la complessità complessiva delle operazioni impostate sarebbe O (| V |).

Answer 2

Ecco un algoritmo, in pseudo-codice, che tenta di aggiungere commenti per spiegare come funziona.

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 
    } 
} 

L'idea è che con la coda FIFO, esploreremo tutto ciò che è ad una distanza 1 dal set S, se non siamo in grado di trovare alcuna soluzione c'è, tutto a distanza di 2 ... ecc .. quindi noi' Troveremo prima la distanza più breve.

Non sono completamente sicuro della complessità, ma credo che nel caso peggiore, esploriamo solo ogni vertice e ogni spigolo solo una volta in modo da dare O(|E| + |V|). Ma in alcuni casi visitiamo lo stesso vertice più volte. Anche se ciò non aumenta il percorso da esplorare molto, non sono sicuro che dovrebbe esserci un fattore | S | da qualche parte (ma se è considerato come una costante, allora va bene ...)

Spero di non aver perso nulla. Ovviamente non ho la prova di tutto questo .... :)

EDIT (Rispondi al commento)

apparirà il tuo lavoro codice per un grafico come questo? E = (a, b), (a, c), (a, d) , (b, e), (c, e), (d, e), e il mio F = {b, c, d} . Supponi di iniziare con il tuo bfs con a.Sospetto, alla fine, l'array di origini avrà solo {a} e quindi il codice restituirà None. - Guru Devanla

In questo caso, qui è che cosa accade:

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.