Comment trouver tous les nœuds dans un graphique équidistant d'un ensemble de nœuds donné?

Question

Si vous avez un graphique simple non orienté G(V,E) et F qui est un sous-ensemble de V. Comment pouvez-vous trouver un noeud v de sorte que la distance de chaque noeud dans F à v soit la même et les distances sont minimisées? Et il suffit de retourner None s'il n'y a pas v. On m'a dit que cela peut être fait en complexité O(|V|+|E|).

On suppose tous les bords sont de la distance 1.

Quelqu'un peut-il expliquer comment cela peut être fait? Un pseudo-code aiderait aussi.

Answer 1

La solution est similaire à BFS, mais avec un peu de changement:

1. Commencez avec S = F avec des noeuds F marqué.

2. Trouver | S | définit avec la distance 1 de chaque élément dans S (tous ces ensembles doivent contenir des nœuds non marqués). Si l'intersection de ces ensembles est non vide, le candidat est trouvé.

3. Prendre l'union du | S | définit ci-dessus en S 'et marquer ces nœuds. Si S 'est vide, renvoyez' None '.

4. Revenir à l'étape 2.

On suppose toutes les opérations de réglage prennent du temps constant, la complexité de l'algorithme est identique à BFS qui est O (| V | + | E |).

Maintenant, pour raisonner sur la complexité des opérations d'ensemble. Mon raisonnement est que les opérations d'ensemble n'augmentent pas la complexité car les opérations d'union et d'intersection aux étapes 2 et 3 peuvent être combinées pour prendre le temps O (| S |), et puisque à chaque étape S est différent de S dans les itérations précédentes , la complexité globale des opérations d'ensemble serait O (| V |).

Answer 2

Voici un algorithme, en pseudo-code, essayant d'ajouter des commentaires pour expliquer comment cela fonctionne.

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'idée est que la file d'attente FIFO, nous allons explorer tout ce qui est à une distance 1 de l'ensemble S, si nous ne pouvons y trouver toute solution, tout à la distance 2 ... etc .. donc nous ll trouvera la plus courte distance en premier. Je ne suis pas complètement sûr de la complexité, mais je crois que dans le pire des cas, nous n'explorons chaque sommet et chaque bord qu'une seule fois, ce qui donnerait O(|E| + |V|). Mais dans certains cas, nous visitons le même sommet plusieurs fois. Bien que cela n'augmente pas les chemins pour explorer beaucoup, je ne suis pas sûr qu'il devrait y avoir un facteur | S | quelque part (mais si cela est juste considéré comme une constante, alors ça va ...)

J'espère que je n'ai rien manqué. Il est évident que je n'ai pas testé tout cela .... :)

EDIT (réponse à un commentaire)

Est-ce que votre travail de code pour un graphique comme celui-ci? E = (a, b), (a, c), (a, d) , (b, e), (c, e), (d, e), et mon F = {b, c, d} . Dites, vous démarrez votre bfs avec un.Je suspecte, à la fin le tableau d'origines aura seulement {a} et donc le code retournera None. - Guru Devanla

Dans ce cas, voici ce qui se passe:

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.