[C]eliminare vertice da un grafo

[Tony Hak]

ciao a tutti ! mi sapreste dire un algoritmo o il codice per eliminare un vertice da un grafo con liste di adiacenza ? ..grazie mille per l'aiuto !

[71104]

dunque, io non è che mi ricordi troppo bene come fosse organizzata la memorizzazione di un grafo con matrice di adiacenze, ma supponiamo che sia organizzata nel seguente modo: N vertici, M archi, hai una matrice da NxN, ciascuna casella della matrice contiene una X (chiamiamola così ) in corrispondenza di un arco, in tutto ci sono M X. per cancellare un vertice devi semplicemente eliminare la riga e la colonna corrispondenti a quel vertice, ed elimini automaticamente anche tutti gli archi incidenti a quel vertice.

edit: se come struttura di memorizzazione anziché una matrice tu hai una serie di liste di adiacenze, diciamo N liste ciascuna delle quali può contenere al massimo N nodi (un nodo per ogni vertice adiacente al vertice associato alla lista), allora devi eliminare la lista di adiacenze del vertice che stai eliminando e in più devi controllare ciascuna di tutte le altre liste ed eliminare da esse gli eventuali nodi corrispondenti sempre al vertice che stai eliminando.

[Tony Hak]

ok .. provo a seguire il tuo algoritmo .. il secondo ..quello delle lista..dovrebbe funzionare.. grazie ...
ps .. la reallocazione del grafo ..come la eseguo ?

[wingman87]

Se ho capito bene il secondo metodo non devi reallocare nulla, devi solo deallocare i nodi inutili e riagganciare i nodi che restano slegati.