Pagina 1 di 3 1 2 3 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 25
  1. #1
    Utente di HTML.it
    Registrato dal
    Oct 2012
    Messaggi
    53

    [c]algoritmo grafi connessi

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

  2. #2
    Utente di HTML.it
    Registrato dal
    Oct 2012
    Messaggi
    53
    Tanto per essere chiari, io non voglio il codice, vorrei l'idea! Spiegatemi a parole come potrebbe funzionare la cosa!!!

  3. #3
    Utente bannato
    Registrato dal
    Apr 2012
    Messaggi
    510
    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.

  4. #4
    Utente di HTML.it
    Registrato dal
    Oct 2012
    Messaggi
    53
    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?

  5. #5
    Utente bannato
    Registrato dal
    Apr 2012
    Messaggi
    510
    Si, però poi quando l' hai fatto tieni presente che puoi ottimizzarlo.

  6. #6
    Utente di HTML.it
    Registrato dal
    Oct 2012
    Messaggi
    53
    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?

  7. #7
    Scusami
    ma non potresti postare il codice che hai fatto fino ad ora?
    Your time is limited, so don't waste it living someone else's life. Stay hungry, stay foolish. (Steve Jobs)

  8. #8
    Utente di HTML.it
    Registrato dal
    Dec 2006
    Messaggi
    156
    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.

  9. #9
    Utente di HTML.it
    Registrato dal
    Oct 2012
    Messaggi
    53
    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


    PSer 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.

  10. #10
    Utente bannato
    Registrato dal
    Apr 2012
    Messaggi
    510
    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.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.