Reprezentacja grafów C++


(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) #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.