[Grafi] Esercizio copertura

[Pablitos23]

Dato un grafo non diretto G si vuole trovare un suo albero di copertura. Si propone il seguente algoritmo:

INPUT un grafo non diretto G = (V, E)
SOL <- ∅
R <- {s} dove s è un qualsiasi nodo di V
WHILE E ≠ ∅ DO
    Estrai un qualsiasi arco {u, v} da E
    IF |{u, v} ∩ R| = 1  THEN
        SOL <- SOL ∪ {{u, v}}
        R <- R ∪ {u, v}
OUTPUT SOL

Dare un'implementazione dell'algoritmo di complessità O(n + m).
Dire se l'algoritmo proposto risolve il problema e in caso affermativo spiegare perché l'algoritmo è corretto (meglio ancora dimostrarne la correttezza) mentre in caso negativo fornire un controesempio.

Qui si richiede un'implementazione di uno spanning tree per grafi non pesati ??
Qualche piccolo consiglio?

[Pablitos23]

Dato che il grafo non è pesato potrebbe andare bene una semplice DFS e l'albero ricoprende coinciderebbe proprio con l'albero della DFS??
Però quanto impiegherei a ricostruire l'albero solo dal vettore dei padri?

[apatriarca]

Qualsiasi visita potrebbe andare bene. Non capisco cosa intendi con l'ultima domanda. La visita ti fornisce già l'albero..