Lista sąsiedztwa - Grafy

Question

(Nie wiem jak tego szukać tutaj xD)

Potrzebuję zrobić metodę usuwanie w swoim projekcie, projekt dotyczy utworzenia trzech Grafów: w postaci macierzy, listy sąsiedztwa i z haszowaniem. Nie wiem jak usunąć z listy sąsiedztwa i haszowania (chyba na tej samej zasadzie będzie to usuwanie się wykonywało). Zrobiłem taki kod jak niżej:

void GrafL::remove(unsigned v1, unsigned v2) {
	vector<int>::iterator it;
	for (unsigned i = 0;i < List[v1].size();i++) {
		if (List[v1][i] == List[v1][v2]) {
			it = List[v1].end();
			*List[v1].end() = List[v1][i];
			List[v1][i] = *it;
		}
	}
	for (unsigned i = 0;i < List[v2].size();i++) {
		if (List[i][v2] == List[v2][v1]) {
			it = List[v2].end();
			*List[v2].end() = List[i][v2];
			List[i][v2] = *it;
		}
	}
	List[v1].pop_back();
	List[v2].pop_back();
	density--;
}

I ewentualnie mogę prosić o ciekawsze wykonanie usuwania właśnie z tej listy, bo zrobiłem to (też nie wiem czy dobrze) metodą ze zmienną pomocniczą.

Answer 1

Ogólnie jeżeli użyjemy vectora zamiast listy i dla kazdej krawedzi a -> b zapiszemy w ktorym indeksie w graf[b] znajduje sie b -> a, to mozna zaimplementowac usuwanie w czasie stalym (niby usuwanie z vectora ma czas liniowy, ale podmieniamy usuwany element z ostatnim i usuwamy ostatni element, co ma czas staly). 
A co do kodu i błędów:
- Lista[i].end() nie jest ostatnim elementem tablicy, tylko elementem po ostatnim (pierwszy element nie nalezacy do vectora), wiec jest tu blad uzywania niezaalokowanej pamieci.
- Nawet po poprawieniu tego bledu podmiana korzystająca ze wskaźnika się nie uda. (trzeba przepisac wartosc jak byla na koncu listy do srodka, zamiast iteratora potrzebny jest int) Błąd polega na tym, że po operacji w 6 linijce, 7 to tak naprawde
Lista[v1][i] = Lista[v1][i]

Co do haszowanej wersji, to zalezy ona od implementacji haszy i jej wlasciwosci