radmar
(radmar)
#1
Witam!
W jaki sposób reprezentować liste sąsiedztwa, co będzie najodpowiedniejsze
Tablica wierzchołków, taka że typem jest struktura, która zawiera wskaźnik na listę (jednokierunkową własnej implementacji bądź STL’a - co lepsze)
czy może może tablice list?
Kojot
(Kojot)
#2
Listę sąsiedztwa robi się po to, żeby właśnie uniknąć pamięciożernych tablic.
Ja bym zrobił po prostu:
typedef list> lista_sasiedztwa;
typedef pair krawedz;
lista_sasiedztwa moja_lista;
gdzie Node* to wskaźnik do Twojego wierzchołka. Wtedy dodanie krawędzi pomiędzy wierzchołkami to:
moja_lista.push_back(krawedz(&wierzcholek1, &wierzcholek2));
Wyszukiwanie też jest dosyć proste:
for(lista_sasiedztwa::iterator it = moja_lista.begin(); it != moja_lista.end(); it++)
{
Node* wierzcholek1 = (*it).first;
Node* wierzcholek2 = (*it).second;
}
Dobrze, żeby struktura Node miała jakiś unikalny identyfikator.