Jasne.
Są co najmniej dwie metody reprezentacji grafów w pamięci.
Pierwsza to tzw. lista sąsiedztwa - dla każdego wierzchołka w grafie v przechowujemy listę sąsiadów, do których prowadzi krawędźz v. To implementuje się za pomocą std::vector zazwyczaj, albo std:
t.
Jeżeli graf jest ważony, można to rozwiązać na kilka sposobów - albo zadeklarowaćdodatkową, dwuwymiarową tablicę (jeżeli graf jest prosty, tj. nie ma pętli i krawędzi wielokrotnych) jeżeli jest mały, lub też w wektorach/listach przechowywać pary <koszt, wierzchołek>. Przykład takiej reprezentacji:
Kod :
std::vector<int> graf[4]; // Reprezentujemy graf czterowierzchołkowy.
graf[2].push_back(3); // Wierzchołek 2 jest połączony krawędzią (skierowaną) z 3.
// ... i tak dalej. Jeżeli graf ma byćnieskierowany zawsze dodajemy dwie krawędzie - z v do w i z w do v.
Przejście przez wszystkie krawędzie wychodzące z danego wierzchołka realizujemy za pomocą prostej pętli:
Kod :
for(int v = 0; v < graf[2].size(); ++v) {
// g[2][v] - wierzchołek z którego jest krawędźz 2.
}
Drugą reprezentacją, przydatną szczególnie gdy potrzebujemy sprawdzić, czy v jest połączone z w w czasie stałym jest macierz sąsiedztwa. Mając np. graf 10x10 tworzymy sobie tablicę 10x10 i wsadzamy jeden (lub koszt krawędzi, jeżeli graf jest skierowany) gdy krawędź istnieje, lub 0 gdy nie istnieje. Zauważmy, że nie jesteśmy w stanie reprezentować w ten sposób grafów złożonych (znaczy, mała modyfikacja byłaby wymagana - musielibyśmy zamiast np. intów trzymać listę intów w każdym polu).
Ta reprezentacja zajmuje więcej w pamięci (V*V gdzie V to liczba wierzchołków), ale czasem jest przydatna.
A co do algorytmów DFS i BFS - ich ogólna idea jest identyczna, zmienia się tylko struktura danych, która pod nimi leży. W przypadku DFSa jest to stos (LIFO - last in, first out), a w przypadku BFS - kolejka. Załóżmy,że mamy generyczny typ kolekcja, który ma metody niepusta, dodaj i wyciągnij_pierwszy, gdzie pierwszy to w przypadku kolejki pierwszy wrzucony element, a w przypadku stosu ostatni wrzucony element. Wyciąga go i usuwa. Implementacja tych algorytmów w tej kolejce jest IDENTYCZNA (zmienia się struktura wewnątrz kolejki) i realizuje ją następujący pseudokod:
Kod :
<wstaw wierzchołek startowy do kolejki>
dopóki Kolejka.niepusta()
Wierzchołek w = Kolejka.wyciągnij_pierwszy()
odwiedzony[w] = true
dla wszystkich sąsiadów w, nazwijmy ich v:
jeżeli v nie jest odwiedzony:
Kolejka.dodaj(v)
Z racji tego, że stos to taka struktura danych, która jest naturalna przy rekurencji i nie trzeba jej implementować, implementuje się DFS zwyczajową za pomocą rekurencji, a w BFSie potrzeba kolejki.
Kod :
// zakładam, że graf realizujemy jako listę sąsiedztwa
void dfs(int v) {
used[v] = true;
for(int i = 0; i < g[v].size(); ++i) {
if(!used(g[v][i]))
dfs(g[v][i]);
}
}
// Zakładam, że istnieje kolejka k z wrzuconym elementem startowym.
// std::queue<int> q;
// q.push(1);
void bfs() {
while(!k.empty()) {
int w = k.pop();
used[w] = true;
for(int i = 0; i < g[w].size(); ++i) {
if(!used[g[w][i]]) {
k.push(g[w][i]);
}
}
}
}
Jak widzisz, implementacja BFS jest bardzo podobna do pseudokodu. Implementacja DFS korzysta z tego, że stos rekurencji jest stosem - więc nie wygląda już tak samo.
Implementację na podstwie macierzy sąsiedztwa pozostawiam jako proste ćwiczenie ;). Podpowiem, że wystarczy zmienić wewnętrzną pętlę na inny format.
Pozdrawiam
Killavus
