Connettere k componenti connesse di un grafo

[Patras]

Salve! Ho una gran difficoltà nella risoluzione di questo problema:

Dimostrare che, per rendere connesso un grafo avente componenti connesse, è necessario
aggiungere almeno rami.
Poi, progettare (mediante pseudocodice) un algoritmo che renda connesso un grafo
aggiungendovi il minimo numero di rami. L’algoritmo deve avere le stesse prestazioni
dell’attraversamento DFS, indipendentemente dalla struttura che realizza il grafo (tra le tre
presentate a lezione). Si considerino i vertici e i rami “decorabili” in un tempo , come
normalmente avviene negli attraversamenti.

Dimostrare che ci vogliono minimo rami è abbastanza ovvio: basta sostituire le componenti connesse con dei nodi indipendenti e abbiamo una catena senza rami. Ci vogliono rami per formare una catena di nodi.

La domanda è: come connettere le componenti connesse con questi rami in dove sono il numero di nodi e numero di rami?

La mia idea sarebbe quella di prendere un nodo, e salvare il suo riferimento, e mentre faccio la visita di cancellare in qualche modo ogni nodo visitato, rimanendo con quello preso prima. Quando ho finito, della componente connessa mi rimane un solo nodo, quindi quando prendo un prossimo nodo sicuramente sarà appartenente a un'altra componente connessa e lo collego al nodo che ho preso prima attraverso un ramo. Poi cancello anche il riferimento al nodo della componente connessa precedente, e ripeto il passaggio per la nuova componente connessa. E' chiaro che facendo cosi le prestazioni sarebbero quelle di un attraversamento. Ma è possibile fare tutto questo in qualche modo?

Per "cancellare" i nodi mi viene in mente ora di clonare la lista dei riferimenti ai vertici (Vertex List) operando sempre su di essa per poi trovare quelli di un'altra componente connessa. Come faccio ora a cancellare questi riferimenti ai nodi che visito in tempo ? Bisognerebbe avere all'interno dei nodi del grafo un contenuto, ad esempio un riferimento a questa lista vertex in modo da trovare di volta in volta subito in vertex list e cancellarlo. Se fosse un array sarebbe l'indice della cella che però cambia sempre dopo le rimozioni, o resta uguale. Se fosse una Linked List (catena) sarebbe il riferimento al nodo della catena, che a sua volta contiene quindi il riferimento al nodo del grafo.
In una catena Linked List una volta che hai il riferimento al nodo - remove ci mette come tempo. In teoria dovremmo farcela a rimanere con nodi che mancano da visitare.

Qualunque sia la Vertex List originale, creo una sua copia/clone Vertex Linked List e mentre la creo, inserisco in ogni nodo del grafo, il riferimento al nodo Vertex Linked List che a sua volta contiene il riferimento al nodo del grafo
Ricapitalonda prendo un nodo di Vertex Linked List, lo tengo, e vado avanti attraversando il grafo con una BFS, cancellando di volta in volta i nodi nella Vertex Linked List che si riferiscono ai nodi visitati a parte il primo. Una volta finito, la Vertex Linked List contiene riferimenti ad altre componente connesse, prendo un nodo non visitato, e lo connetto al primo che ho salvato. (connettere due nodi dovrebbe essere , è possibile?) Cancello ora anche il riferimento al primo nodo che avevo salvato, e riparto con la nuova componente connessa.

SICURAMENTE ci sono soluzioni MIGLIORI ! Qualcuno ha qualche idea?

[Patras]

RISOLTO, non serviva tutta questa baracca che occupa anche tanta memoria, basta fare un ciclo for che automaticamente si tiene conto dell'indice del nodo scelto. In questo modo si visitano due volte i nodi di ogni componente connessa ma questo va bene, asintoticamente diventa $O(2n+m)=O(n+m)$... qualcosa di questo genere:

Codice: Seleziona tutto

for (int i = 0; i < G.vertex_number; ++i) {
    if (G.labels[i] == UNEXPLORED) {
        // Nuova componente connessa.. connetto il nodo e visito il grafo
        if (i > 0) {
            G.adjacents[0].append(i);
            G.adjacents[i].append(0);
        }
        BFS(G, i);
    }