Componenti connesse di un grafo

[andra_zx]

Ciao a tutti ho biosgno di una delucidazione sui grafi. Allora, sò che con l' algoritmo DFS, su di un grafo G non orientato, e implementato con lista delle aiacenza, impiega un tempo O(n + m) (nel caso di n vertici e m lati) per etichettare tutti i lati come discovey edge o back edge. Per definizione, l' algoritmo DFS serve a trovare le componenti connesse di G. Il problema sta nel fatto che un esercizio mi chiede di trovare un algoritmo eseguibile in O(n + m) per trovare TUTTE le componenti connesse di G. é proprio questo ciò che non capisco, perchè di fatto al DFS trova già tutte le componenti connesse di G. In poche parole tutti i vertici di un grafo non orientato sono già connessi. Evidentemente c'è qualcosa che mi sfugge..

Grazie in anticipo..

[apatriarca]

Immagino che l'esercizio chiedesse di trovare tutte le componenti fortemente connesse del grafo (strongly connected component) trattandosi di un grafo orientato, cioè i sottografi massimali in cui ogni vertice del sottografo è collegato a qualsiasi altro. Su si tratta di questo prova a dare un occhiata a questa pagina di wikipedia

[andra_zx]

"apatriarca":Immagino che l'esercizio chiedesse di trovare tutte le componenti fortemente connesse del grafo (strongly connected component) trattandosi di un grafo orientato, cioè i sottografi massimali in cui ogni vertice del sottografo è collegato a qualsiasi altro. Su si tratta di questo prova a dare un occhiata a questa pagina di wikipedia

nono chiedee di trovare le componenti conesse, si un grafo NON orientato.

[apatriarca]

Bhe... allora devi semplicemente scrivere l'algoritmo che già conosci. Non vedo molto il senso, ma quell'algoritmo ha la complessità richiesta.