Dobry wieczór,
W ostatnim czasie postanowiłam zacząć uczyć się grafów (najczęściej wykorzystywane algorytmy, implementacja samej struktur w pamięci komputera itp.)
Korzystam przy tym ze znalezionej w internecie książki pt. "Algorytmika praktyczna w konkursach informatycznych" autorstwa pana Piotra Stańczyka.
Dzisiaj wzięłam się za implementację algorytmu DFS - przeszukiwanie grafu wgłąb. Myślę, że nie muszę na ten temat pisać nic więcej, bo wystarczające wyjaśnienia dotyczące metody jego działania znajdą się w komentarzach przy kodzie programu.
Moim problemem są kosmiczne liczby, jakie dostaję (podczas wyświetlania) przy czasie wejścia i wyjścia. Prześledziłam już kilka razy całą część kodu związaną z DFS (na reszcie mniej się skupiałam, bo sama implementacja struktury grafu w pamięci komputera i metody dodawania krawędzi działały już wcześniej) i nie mogę dojść gdzie zrobiłam błąd logiczny. Bardzo proszę o wskazówki ;-)
#include <iostream>
#include <vector>
using namespace std;
#define FOR(x, b, e) for(int x = b; x <= (e); ++x)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define SIZE(x) ((int)(x).size())
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
template <class V, class E> struct Graph {
// Typ krawêdzi (Ed) dziedziczy po typie zawierajacym dodatkowe info zwiazane z krawedzia (E).
// Zawiera on rowniez pole v, okreslajace numer wierzcholka, do ktorego prowadzi krawedz.
// Zaimplementowany konstruktor pozwala na skrocenie zapisu wielu funkcji korzystajacych ze struktury grafu.
struct Ed : E
{
int rev;
int v;
Ed(E p, int w) : E(p), v(w) { }
};
// Typ wierzcholka (Ve) dziedziczy po typie zawierajacym dodatkowe info
// z nim zwiazane (V)
// oraz po wektorze krawedzi.
// To drugie dziedziczenie umozliwia latwe iterowanie po wszystkich krawedziach wychodzacych z wierzcholka v: FOREACH(it, g[v])
struct Ve : V, vector<Ed> {};
/*/// Wzbogacenie wierzcholkow musi zawierac pola wymagane przez a. BFS
struct Vs : V, vector<Ed>
{
int t, s;
};*/
// Wektor wierzcholkow w grafie:
vector<Ve> g;
// Konstruktor grafu- przyjmuje jako parametr liczbe wierzcholkow:
Graph(int n = 0) : g(n) { }
// Funkcja dodajaca do grafu nowa krawedz skierowana z wierzcholka b do e,
// zawierajaca dodatkowe info okreslone przez zmienna d.
void EdgeD(int b, int e, E d = E())
{
g[b].PB(Ed(d, e));
}
void EdgeU(int b, int e, E d = E())
{
Ed eg(d, e);
eg.rev = SIZE(g[e]) + (b==e);
g[b].PB(eg);
eg.rev = SIZE(g[eg.v = b]) - 1;
g[e].PB(eg);
}
void Write()
{
// Dla wszystkich wierzchołków w grafie zaczynając od 0...
REP(x, SIZE(g)) {
// Wypisz numer wierzchołka
cout << x << ":";
// Dla każdej krawędzi wychodzącej z przetwarzanego wierzchołka o numerze
// x, wypisz numer wierzchołka, do którego ona prowadzi
FOREACH(it, g[x]) cout << " " << it->v;
cout << endl;
}
}
// po wykonaniu agorytmu DFS, pola int d, int f kazdego wierzcholka zawiera odpowiednio czas wejscia i wyjscia
// natomiast pole int s zawiera numer ojca w drzewie DFS
// (dla wierzcholka bedacego zrodlem wyszukiwania oraz wierzcholkow nieodwiedzonych jest to -1)
// zmienna t jest uzywana do pamietania aktualnego czasu przetwarzania
int t;
// funkcja rekurencyjna przeszukujaca poddrzewo wierzcholka v metoda DFS
void DfsV(int v){ // przeszukiwwanie grafu wszerz
// ustaw czas wejscia do wierzcholka
g[v].d = t++;
// Dla kazdej krawedzi wychodzacej z wierzcholka v, jesli wierzcholek,
// do ktorego prowadzi krawedz nie byl jeszcze odwiedzony, to go odwiedz
FOREACH(it, g[v]) if(g[it->v].s == -1)
{
g[it->v].s = v;
DfsV(it->v);
}
// Ustaw czas wyjscia z wierzcholka
g[v].f = ++t;
}
void DfsR(int e = -1){
int t = -1;
int b=0;
// Dla wierzcholkow z przedzialu [b..e] zostanie wywolana funkcja void DfsV(int).
// Jesli do funkcji void DfsR(int) nie przekazano
// parametru, to przedzialem tym jest [0..SIZE(g)-1]
// (wszystkie wierzcholki w grafie),
// w przeciwnym wypadku [e..e] (tylko jeden wierzcholek)
e == -1 ? e = SIZE(g) - 1 : b = e;
REP(x, SIZE(g)) g[x].d = g[x].f = g[x].s = -1;
// Wykonaj algorytm DFS dla wszystkich wierzcholkow z przedzialu [b..e]
FOR(x,b,e) if(g[x].s == -1) DfsV(x);
}
};
// Krawedzie grafu nieskierowanego wymagaja dodatkowego pola int rev
struct Ve{
int rev;
};
// Wzbogacenie wierzcholkow musi zawierac pola wymagane przez a. DFS
struct Vs{
int d, f, s;
};
///
int main() {
int n, m, b, e, s;
// Wczytaj liczbę wierzchołków i krawędzi oraz numer wierzcholka startowego
cin >> n >> m >> s;
// Skonstruuj graf o odpowiednim rozmiarze, nie zawierający dodatkowych
// informacji dla wierzchołków ani krawędzi
Graph<Vs, Ve> gr(n);
// Dodaj do grafu wszystkie krawedzie
REP(x, m) {
// Wczytaj początek i koniec kolejnej krawędzi
cin >> b >> e;
// Dodaj do grafu krawędź skierowaną z wierzchołka b do e
gr.EdgeU(b, e);
}
// Wykonaj algorytm DFS
gr.DfsR(s);
// Wypisz wynik
REP(x, n) cout << "Wierzcholek " << x << ": czas wejscia = " << gr.g[x].d <<
", czas wyjscia = " << gr.g[x].f << ", ojciec w drzewie DFS = " << gr.g[x].s << endl;
return 0;
}
A o to, co dostaję w konsoli:
0 1
2 3
2 4
3 5
3 6
5 6
Wierzcholek 0: czas wejscia = -1, czas wyjscia = -1, ojciec w drzewie DFS = -1
Wierzcholek 1: czas wejscia = -1, czas wyjscia = -1, ojciec w drzewie DFS = -1
Wierzcholek 2: czas wejscia = 4354657, czas wyjscia = 4354667, ojciec w drzewie DFS = 3
Wierzcholek 3: czas wejscia = 4354658, czas wyjscia = 4354668, ojciec w drzewie DFS = 2
Wierzcholek 4: czas wejscia = 4354664, czas wyjscia = 4354666, ojciec w drzewie DFS = 2
Wierzcholek 5: czas wejscia = 4354659, czas wyjscia = 4354663, ojciec w drzewie DFS = 3
Wierzcholek 6: czas wejscia = 4354660, czas wyjscia = 4354662, ojciec w drzewie DFS = 5
Process returned 0 (0x0) execution time : 40.995 s
Press any key to continue.
*Może dodam jeszcze tylko dla jasności (tytuł książki), że na razie, to ja niewiele potrafię- więc na żaden konkurs się nie wybieram.