PDA

Visualizza la versione completa : [c]algoritmo grafi connessi


Iso90
27-10-2012, 11:05
Buongiorno a tutti.
Ho un problema a livello algoritmico, non tanto di codice:
come riesco a capire se un grafo orientato connesso?
Da notare, NON fortemente connesso, a me basta che sia connesso in qualche modo. Ho cercato un p su internet ma salta fuori tutta roba su componenti fortemente connesse e grafi non orientati. Come struttura dati ho a disposizione sia la lista di adiacenza che la matrice di adiacenza. Potete aiutarmi pls????? :(

Iso90
27-10-2012, 17:57
Tanto per essere chiari, io non voglio il codice, vorrei l'idea! Spiegatemi a parole come potrebbe funzionare la cosa!!! :)

Who am I
28-10-2012, 12:50
Per ogni nodo del grado esegui una visita BFS o DFS partendo da quel nodo.
Se alla fine della visita sei riuscito a visitare tutti gli altri nodi passi al nodo successivo.Se non sei riuscito a visitare tutti gli altri nodi, concludi che non connesso.
Alla fine sar connesso se riesci a visitare tutti gli altri nodi partendo da un nodo qualsiasi.Siccome il grafo connesso non detto che se vai dal nodo ui al nodo uj allora sia possibile andare da uj a ui.
Inoltre puoi rendere l' algoritmo meno complesso (ma prima ti consiglio di provare a fare la versione semplice) tenendo conto del fatto che se il nodo ui collegato al nodo uj e viceversa, allora anche tutti i nodi intermedi sono collegati tra di loro.
Inizia a scrivere il codice e fammi sapere.

Iso90
28-10-2012, 19:00
Praticamente per ogni nodo faccio una visita, mi segno i nodi che riesco a raggiungere e se alla fine delle visite ho segnato tutti i nodi del grafo, esso connesso...ho capito bene?

Who am I
29-10-2012, 11:43
Si, per poi quando l' hai fatto tieni presente che puoi ottimizzarlo.

Iso90
29-10-2012, 13:43
Scusa la mia ignoranza ma ho fatto una riflessione:
preso il grafo 1,2,3,4 con archi:
da 1 a 2
da 2 a 1
da 3 a 4
da 4 a 3
con l'algoritmo presentato ottengo:
vertice 1 -> segno il vertice n 2
vertice 2 -> segno vertice n 1
vertice 3 -> segno il vertice n 4
vertice 4 -> segno il vertice n 3
quindi ho segnato tutti i vertici e in teoria secondo l'algoritmo il grafo dovrebbe essere connesso, invece non lo ! Sono cretino io oppure davvero cos? come si pu rimediare?

21Edoardo96
29-10-2012, 17:23
Scusami
ma non potresti postare il codice che hai fatto fino ad ora?

zucchino
29-10-2012, 17:34
Originariamente inviato da Who am I
Per ogni nodo del grado esegui una visita BFS o DFS partendo da quel nodo.
Se alla fine della visita sei riuscito a visitare tutti gli altri nodi passi al nodo successivo.
Se non sei riuscito a visitare tutti gli altri nodi, concludi che non connesso.


devi chiederti se hai visitato tutti i nodi ad ogni passo.
nel tuo caso, alla fine della prima visita, non avendo toccato tutti i nodi, concludi che non connesso.

Iso90
29-10-2012, 17:43
Originariamente inviato da zucchino
devi chiederti se hai visitato tutti i nodi ad ogni passo.
nel tuo caso, alla fine della prima visita, non avendo toccato tutti i nodi, concludi che non connesso.

Allora vi faccio un altro esempio:
-grafo 1,2,3,4;
-archi:
da 1 a 2
da 2 a 4
da 3 a 2

Questo grafo costituito da una sola componente connessa per applicando l'algoritmo abbiamo:
partendo dal vertice 1, raggiungo il vertice 2 ed il vertice 4. non ho visitato il vertice 3.
Questo significa che ho 2 componenti connesse? Evidentemente no visto che il grafo connesso


PS:per 21edoardo96:
se avessi letto i reply precedenti attentamente avresti capito anche che finch non ho le idee chiare in testa non scrivo codice. Non un problema di debug il mio, ma concettuale.

Who am I
29-10-2012, 19:39
Originariamente inviato da zucchino
devi chiederti se hai visitato tutti i nodi ad ogni passo.
nel tuo caso, alla fine della prima visita, non avendo toccato tutti i nodi, concludi che non connesso.

Non capisco la differenza con quello che sto dicendo io.

Loading