PDA

Visualizza la versione completa : [C++] Controllo connessione grafo


AyFrank
29-12-2012, 17:29
Salve a tutti, mi affido subito ad un esempio per esporvi il mio dubbio nella maniera più chiara possibile :D

G è un grafo non orientato, supponiamo di avere due partizioni in G, una partizione A composta da 95 vertici ed una partizione B composta da 5 vertici. Ogni passo del mio algoritmo corrisponde ad una regola del taglio. Le due partizioni sono sconnesse, cosa che non so a priori altrimenti non esisterebbe il topic, però partendo da un vertice nella partizione B è ovvio che arriverò molto prima alla conclusione che le due partizione sono sconnesse, piuttosto che cominciando la visita da un vertice in A.

Sapendo che posso iniziare la visita da un vertice S qualsiasi nel grafo, la domanda è: c'è qualche criterio per sperare di iniziare la visita da un vertice in B piuttosto che da un vertice in A?

Loading