[Algoritmi] Connettere k componenti connesse di un grafo
Salve! Ho una gran difficoltà nella risoluzione di questo problema:
Dimostrare che, per rendere connesso un grafo avente $k$ componenti connesse, è necessario
aggiungere almeno $k – 1$ 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 Θ(1), come
normalmente avviene negli attraversamenti.
Dimostrare che ci vogliono minimo k-1 rami è abbastanza ovvio: basta sostituire le componenti connesse con dei nodi indipendenti e abbiamo una catena senza rami. Ci vogliono k-1 rami per formare una catena di k nodi.
La domanda è: come connettere le componenti connesse con questi $k-1$ rami in $O(n+m)$ dove $n$ sono il numero di nodi e $m$ 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 O(1)? 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 O(1) 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 $O(1)$, è possibile?) Cancello ora anche il riferimento al primo nodo che avevo salvato, e riparto con la nuova componente connessa. $O(n+m)$
SICURAMENTE ci sono soluzioni MIGLIORI! Qualcuno ha qualche idea?
Dimostrare che, per rendere connesso un grafo avente $k$ componenti connesse, è necessario
aggiungere almeno $k – 1$ 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 Θ(1), come
normalmente avviene negli attraversamenti.
Dimostrare che ci vogliono minimo k-1 rami è abbastanza ovvio: basta sostituire le componenti connesse con dei nodi indipendenti e abbiamo una catena senza rami. Ci vogliono k-1 rami per formare una catena di k nodi.
La domanda è: come connettere le componenti connesse con questi $k-1$ rami in $O(n+m)$ dove $n$ sono il numero di nodi e $m$ 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 O(1)? 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 O(1) 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 $O(1)$, è possibile?) Cancello ora anche il riferimento al primo nodo che avevo salvato, e riparto con la nuova componente connessa. $O(n+m)$
SICURAMENTE ci sono soluzioni MIGLIORI! Qualcuno ha qualche idea?
Risposte
Sinceramente ti stai facendo più problemi del necessario. Il testo dell'esercizio dice che è possibile decorare un nodo in tempo costante. È quindi sufficiente visitare un nodo per volta, iniziando una visita a partire da questo nodo e decorando ogni nodo visitato in un qualche modo (non ha importanza il metodo). In questo modo ogni volta che trovi un nodo iniziale non decorato puoi assumere faccia parte di una nuova componente connessa e puoi connetterlo a qualsiasi dei nodi visitati in precedenza.
Ma dopo aver completato la visita della prima componente connessa, come trovo un nodo iniziale non decorato? devo di nuovo tornare alla lista dei vertici (o nodi) e scandirli tutti finché non trovo un nodo non decorato, perché facendo l'attraversamento non posso in nessun modo arrivare a un nodo appartenente a un'altra componente connessa (mi sposto attraverso i rami, non ci sono rami tra due componenti connesse distinte).
Se scandisco ogni volta quella lista non posso avere $O(n+m)$ : se nel caso peggiore avessi semplicemente k nodi indipendenti verrebbe addirittura $O(1+2+...+n-1)=O(n^2)$ dove $n$ è il numero di vertici...
Se scandisco ogni volta quella lista non posso avere $O(n+m)$ : se nel caso peggiore avessi semplicemente k nodi indipendenti verrebbe addirittura $O(1+2+...+n-1)=O(n^2)$ dove $n$ è il numero di vertici...
Ma stai scorrendo quella lista una sola volta. Tutti i nodi non visitati saranno necessariamente successivi a quello corrente usato per partire nella visita. Non ha senso ripartire dall'inizio. L'algoritmo è del tutto equivalente alla ricerca delle componenti connesse..
"apatriarca":
Tutti i nodi non visitati saranno necessariamente successivi a quello corrente usato per partire nella visita.
Ma questo vale anche in generale? I nodi dentro la vertex list potrebbero in certi casi essere ordinati in base a un loro valore interno, magari per la prima componente connessa questi valori sono 1,3,4... per la seconda 2,7,8...in modo che l'ordine dei nodi visitati o delle componenti connesse non corrisponde all'ordinamento dentro la Vertex List( anche perché l'ordine della visita dipende anche se l'attraversamento è BFS o DFS etc..). Se attraverso il grafo con un BFS per liste incidenti, dipende dall'ordine "topologico" della visita: l'ultimo nodo che visito di una componente connessa potrebbe anche essere il secondo nodo della Vertex List.
Il seguente pseudocodice (simile a Python) rappresenta quello che intendo:
A meno di fare qualcosa di incredibilmente sbagliato, in cui vai a modificare l'ordine della lista dei nodi durante la visita, l'iterazione esterna scorrerà la lista una sola volta. Credo che tu abbia in mente un qualche tipo di implementazione particolare in cui tutto questo sia complicato, perché non c'è nulla di diverso rispetto ad una normale visita in un grafo non connesso.
for node in nodes(G):
if not marked(node):
visit(node)
A meno di fare qualcosa di incredibilmente sbagliato, in cui vai a modificare l'ordine della lista dei nodi durante la visita, l'iterazione esterna scorrerà la lista una sola volta. Credo che tu abbia in mente un qualche tipo di implementazione particolare in cui tutto questo sia complicato, perché non c'è nulla di diverso rispetto ad una normale visita in un grafo non connesso.
Lo so dove stai parando e che un qualsiasi attraversamento di un qualsiasi grafo con tante o poche componenti connesse dovrebbe essere $O(n+m)$ ma non capisco concretamente come funziona questo salto da una componente connessa a un'altra perché leggo questi pseudocodici ma sono troppo astratti e sembrano fatti solo per grafi connessi. Come faccio nella vertex list a saltare ad un altro nodo non visitato in O(1)?
Anche questo codice che hai messo mi sembra molto astratto come un pseudocodice (non conosco Python)
La mia proposta (di cancellarli tutti quelli visitati grazie ai riferimenti contenuti nei nodi ai nodi della catena Linked Vertex List) funzionerebbe ma mi sembra troppo complicata
L'unica visita approfondita che conosco è questa ma qua per esempio ho segnato col rosso il passaggio che non è chiaro cioè dà per scontato che alla fine, l'iteratore o l'indice successivo di G.verticles appartenga a una nuova componente connessa
[img]http://i.imgur.com/2Fz3311.png?1[/img]
Anche questo codice che hai messo mi sembra molto astratto come un pseudocodice (non conosco Python)
La mia proposta (di cancellarli tutti quelli visitati grazie ai riferimenti contenuti nei nodi ai nodi della catena Linked Vertex List) funzionerebbe ma mi sembra troppo complicata
L'unica visita approfondita che conosco è questa ma qua per esempio ho segnato col rosso il passaggio che non è chiaro cioè dà per scontato che alla fine, l'iteratore o l'indice successivo di G.verticles appartenga a una nuova componente connessa
[img]http://i.imgur.com/2Fz3311.png?1[/img]
La descrizione nell'immagine è del tutto equivalente a quella che ti ho scritto. G.vertices() è la lista dei nodi che è fissa, NON cambia. Visiti la lista un elemento per volta e se un vertice non è stato precedentemente visitato, visiti tutta la sua componente connessa. Siccome i vertici vengono visitati in ordine nel ciclo esterno, solo i nodi successivi nella lista apparterranno a questa nuova componente connessa e cambieranno. Tutti quelli precedenti saranno invece già stati visitati.
L'implementazione di grafi può essere complicata, ma supponi di avere semplicemente nodi rappresentati da valori interi da 0 a n-1. Per associare qualcosa ai nodi dovrai quindi semplicemente gestire degli array di lunghezza \(n\). Il tuo algoritmo sarà quindi a questo punto qualcosa come segue:
BFS è poi corrispondente al codice nella tua slide.
L'implementazione di grafi può essere complicata, ma supponi di avere semplicemente nodi rappresentati da valori interi da 0 a n-1. Per associare qualcosa ai nodi dovrai quindi semplicemente gestire degli array di lunghezza \(n\). Il tuo algoritmo sarà quindi a questo punto qualcosa come segue:
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);
}
}
BFS è poi corrispondente al codice nella tua slide.
ecco così è molto più chiaro... ho fatto un po' di confusione in effetti tenendo conto dell'indice rimango a $O(n+m)$ come prestazioni. Basta fare il ciclo...
Grazie mille per la spiegazione!
Grazie mille per la spiegazione!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo