Algoritmo inusuale per grafo

[felpato]

Salve a tutti. Sto cercando un algoritmo che mi trovi il sottoinsieme più grande di componenti connesse in un grafo.

Esempio:
Grafo non orientato
G=<V,E>
V={a,b,c,d,e,f,g,h,i}
E={(a,b),(b,c),(c,d),(f,g),(g,h),(i,e)}

L'algoritmo dovrebbe dare come risultato
{a,b,c,d}

Ringrazio tutti anticipatamente per l'attenzione.

[tuccio`]

direi che ti conviene fare una dfs, e ogni volta che ritorni alla "prima" chiamata valuti quanti vertici hai visitato nell'ultima

[banryu79]

Salve a tutti. Sto cercando un algoritmo che mi trovi il sottoinsieme più grande di componenti connesse in un grafo.

Ma devi scriverlo tu?

Una visita in profondità (depth-first) o in larghezza (breadth-first) che parte da un dato vertice 'v', visita completamente il componente connesso che contiene 'v' prima di terminare.

Quindi puoi visitare tutti i componenti connessi del tuo grafo eseguendo un ciclo che inizia una nuova visita (in profondità oppure in larghezza) ogni volta che nel ciclo incontri un vertice 'v' che non è incluso in uno dei componenti connessi già scoperti.

Sapendo questo, una soluzione al tuo problema è quella di eseguire l'agoritmo per trovare tutti i componenti connessi di un grafo, modificato leggermente in modo che tenga traccia del numero di vertici 'v' visitati durante la visita di un componente e "salvi" questa informazione, come risultato di una visita completa, per poi confrontarla con le successive.

[khelidan1980]

Sto forum sta diventando un ritrovo di studenti....e quì sorvolo se no mi bannano...sicuramente ora risponderà che non era mica un esercizio ma la trovato sulle parole crociate