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.