[Algoritmi] Codice Grafo Bipartito. Errore Libro di Testo?

[Giova411]

Buongiorno a tutti,
ho un dubbio sul seguente esercizio:
Modificare una visita BFS per verificare se un grafo non orientato è bipartito oppure no.
Per chi non ricorda i grafi bipartiti: http://it.wikipedia.org/wiki/Grafo_bipartito

Metto anche un'immagine dove voglio colorare di rosso e di bianco per capire se è bipartito:


Ecco, invece, dove penso sia la parte di testo da correggere:


INCISO: ABBIAMO COSTANTI DI COLORE COME FOSSERO SENTINELLE
rosso = 0
bianco = 1
senzacolore = 2
Quindi l'espressione $1- $corrente$ = 1 - 0 = 1$ che trasforma semplicemente il rosso in bianco e viceversa

Secondo voi opera nel modo giusto?

[Giova411]

Ecco sì... Mi pare giusto a vederlo meglio ora...
Potevo cancellare il POST ma lo lascio.
Se qualcuno ha commenti o domande è il benvenuto!

[onlyReferee]

Ciao Giova411
Anche secondo me è corretto: ogni volta che estrai un nuovo nodo tutti gli adiacenti allo stesso dovranno per forza avere un colore attribuito diverso da quello del nodo stesso o (detto in maniera analoga) uguale al colore correntemente considerato che si vuole attribuire ai nodi (ed il cambio di colore serve appunto a questo). In caso contrario, come giustamente mostrato dall'ultimo if dell'algoritmo, non siamo di fronte ad un grafo bipartito.

[Giova411]

Mitico

[geeek]

Scusate ragazzi ma l'avete provato l'algoritmo prima di dire che è corretto??
Se alla prima iterazione ho tre nodi adiacenti a U, per la seconda iterazione che estraggo uno di quei nodi mi va bene perche cambiando colore becco gli altri dall'altra parte. Ma alla terza che ho il 2 nodo messo in coda nella prima iterazione ho lo stesso colore e non va bene!
Ditemi voi se è corretto o no