PRZESZUKIWANIE GRAFU W SZERZ

CO trzeba umieć:

-- LISTY 

-- REPREZENTACJA GRAFU

//////////////////////////////////////////////////////////////////

PRZESZUKIWANIE GRAFU W SZERZ (BFS)

0	1	2	3	4
1	0	2	10
2	0	1	5
3	0	4	5
4	0	3	6	7
5	2	3	6	8	9
6	4	5	7
7	4	6	9
8	5	10	11
9	5	7	12	13
10	1	8	11
11	8	10	12
12	9	11	13
13	9	12

Tutaj również będzie nam potrzebna lista Visit i Stos. Bo w zasadzie przeszukiwanie BFS jest takie same jak DFS, tylko trochę inne :P.

Więc wybieramy sobie wierzchołek początkowy (my znowu wybierzemy sobie wierzchołek 0, bo jestem leniwy) i dodajemy go do Visit.

 

Visit:[0]

Stos: [0]

Teraz bierzemy ten nasz element i dodajemy na Stos i do Visit wszystkie (oprócz odwiedzonych) wierzchołki do niego przyległe, czyli 1,2,3,4. Natomiast 0 zdejmujemy ze stosu.

Visit: [0,1,2,3,4]

Stos: [1,2,3,4]

Teraz bierzemy pierwszy element ze stosu, czyli 1. Teraz dodajemy na Stos i do Visit element 10, bo 2 i 0 były już odwiedzone. Tutaj mamy taką ciekawostkę, że zawsze te same elementy będą szły na stos i do Visit.

Visit: [0,1,2,3,4,10]

Stos: [2,3,4,10]

Następnie bierzemy kolejny element ze stosu, czyli 2. Postępujemy tak samo. Zdejmujemy 2 ze stosu i dodajemy elementy, które nie odwiedziliśmy (5).

Visit: [0,1,2,3,4,10,5]

Stos: [3,4,10,5]

Teraz bierzemy kolejny element, ale 3 ma sąsiadów tylko takich których już odwiedziliśmy, więc tylko zdejmujemy go ze stosu i nic nie robimy. Dalej, bierzemy element 4 i dodajemy sąsiadów (nieodwiedzonych) 6,7. 

 

Visit:[0,1,2,3,4,10,5,6,7]

Stos:[10,5,6,7]

Teraz bierzemy wierzchołek 10 i dodajemy 8 i 11 potem wierzchołek 5 i dodajemy 9. Wierzchołek 6 i 7 już nie będą miały nieodwiedzonych sąsiadów więc tylko zdejmujemy je ze stosu. Następnie bierzemy wierzchołek 8 i dodajemy 11, a potem kolejne wierzchołki też będą miały odwiedzonych sąsiadów. Dopiero 11 będzie dawało 12, a potem wierzchołek 9 wstawi na stos 13. 

 

Visit:[0,1,2,3,4,10,5,6,7,8,11,9,12,13]

Stos:

[12,13]

Następnie program pójdzie dalej i sprawdzi kolejno 12 i 13, ale te wierzchołki już nie mają dodatkowych sąsiadów, więc stos będzie pusty i program się zakończy. Ogólnie zasada jest prosta wchodzimy do wierzchołka, wstawiamy wszystkich nieodwiedzonych sąsiadów zdejmujemy pierwszy element i tak, aż się skończą elementy w stosie.

Teraz jeśli chodzi o implementacje to można użyć całkiem przyjemnej sztuczki, która ułatwi nam robotę. Więc pewnie zauważyłeś, że nasze listy Stos i Visit są w zasadzie podobne. Dodajemy na nie te same elementy. Różnią się tylko tym, że ze Stosu zdejmujemy pierwszy element. To może tą zależność jakoś sprytnie wykorzystać. Więc my to wykorzystamy :D. Po co robić dwie listy prawie takie same, może zrobić jedną. A że jestem leniwy to zrobimy jedną i tą jedną będzie tylko Visit. No ale co z drugą? A no drugą listą też będzie Visit. TYLKO ustawimy sobie na nią jeszcze jeden wskaźnik (nazwiemy go Stos). Tym wskaźnikiem będziemy po nich „chodzić”. Na początku dajemy Stos = Visit. Następnie gdy chcemy zdjąć element ze Stosu to dajemy tylko Stos=Stos->next. Element „zdjęty” ze stosu. Usuwać nic już teraz nie musimy, bo w Visit muszą być wszystkie odwiedzone elementy. W ten prosty i szprytny sposób ominęliśmy jedno zbędne dodawanie, a nasz kod stanie się szybszy :D.

KOD:

////////////////////////////////////////////////////////////////////////////////

///............................BFS......w szerz..............................///

////////////////////////////////////////////////////////////////////////////////

void BFS(struct graf *root,struct graf *Stos,struct graf **Visit ){

// funkcja główna naszego przeszukiwania

// pozostałe funkcje takie same jak dla DFS

    struct branch *w=root->branch; // zmienna pomocnicza

    

    if(!*Visit){ // gdy nie ma jeszcze żadnego elementu w liście

              add_queue(Visit,root); // dodajemy element od którego zaczynamy

              Stos=(*Visit); // ustawiamy na początku głowy list takie same

        }

        while(w){ // przechodzimy po sąsiadach

            if(!find(*Visit,w->top)){ // jeśli element nie odwiedzony

                   add_queue(Visit,w->adress); // dodajemy

            }

            w=w->next;

        }

       if(Stos==*Visit)Stos=Stos->next;

 

// porównujemy adresy jeśli takie same to przestawiamy Stos o jedno dalej

// jest po to, aby pierwszy element,
// od którego zaczynaliśmy nie rozpatrywać ponownie

// wypisywanie

    printf("VISIT: ");

  write_queue(*Visit);

    printf(" STOS: ");

    write_queue(Stos);

    printf("\n");

//

 

    if(Stos) BFS(Stos,Stos->next,Visit);

 

// jeśli wskaźnikiem Stosu nie doszliśmy do końca listy to powtarzamy

}

Jak widzisz DFS i BFS w implementacji, w sumie też i w teorii są bardzo podobne. No oprócz tej jednej drobnej sztuczki magiczki, ale jakbyśmy zrobili dwie listy też byłoby dobrze, ale tak jest lepiej :). Różnice są tylko w użyciu tych funkcji, których akurat tu nie ma :P, bo one są wspólne. W obu przypadkach dodajemy elementy, wypisujemy (tego może nie być, ale ładnie widać jak się zmienia wszystko). Warunek stopu jest taki sam. Tylko tutaj musimy dodać wierzchołki sąsiadujące do Visit, a w DFS tylko wierzchołek w którym jesteśmy.

Jeśli chodzi o grafy to w sumie tyle, można jeszcze dodać, że BFS wykorzystuje się do szukania dróg najkrótszych. Ja oczywiście ze swojej strony zachęcam Cię do zapoznania się z innymi algorytmami na grafach i próbą ich implementacji.