PRZESZUKIWANIE GRAFU W GŁĄB

CO trzeba umieć:

-- LISTY 

-- REPREZENTACJA GRAFU

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

PRZESZUKIWANIE GRAFU

Przeszukiwanie grafu to jest nic innego, jak przejście po grafie tak, aby przejść wszystkie wierzchołki (pod warunkiem że graf jest spójny). Ja omówię przechodzenie grafu w głąb(DFS) i w szerz(BFS), ponieważ to nam do szczęścia może być potrzebne.

PRZESZUKIWANIE W GŁĄB (DFS)

Nasz graf i jego macierz przejść.

 

0	1	2	3
1	0	3
2	0	3	4
3	0	1	2	5
4	2	6
5	3
6	4

Będą nam teraz potrzebne dwie listy, identyczne co do implementacji. Do jednej będziemy dodawać element które odwiedziliśmy (nazwiemy ją Visit) oraz nasz stos, w którym będziemy umieszczać wierzchołki grafu do których będziemy przechodzić (nazwiemy ją Stos).

Na początku wybieramy sobie wierzchołek początkowy (wybieramy 0 dla wygody) i dodajemy go do listy Visit. Następnie na Stos dodajemy wierzchołki przyległe do naszego wierzchołka 0. 
 

Visit: [0]

Stos: [1,2,3]

Teraz bierzemy kolejny wierzchołek, ale teraz naszym następnym wierzchołkiem jest ostatni element Stosu (u nas 3). Więc musimy przejść do wierzchołka 3 (dodać do Visit), ale i usunąć wierzchołek 3 (ostatni element stosu) ze Stosu. Następnie dodać wierzchołki sąsiadujące z naszym wierzchołkiem 3. Są to elementy 1,2,5.

Visit: [0,3]

Stos: [1,2,1,2,5]

Teraz ponownie bierzemy wierzchołek ze Stosu (ostatni – 5) dodajemy do Visit, a wierzchołki przyległe dodajemy do Stosu. Tutaj mamy taką sytuację, że wierzchołkiem przyległy do wierzchołka jest wierzchołek 3. Tego wierzchołka już na stosie nie ma, ale ten wierzchołek jest na liście Visit, więc nie dodajemy go na Stos, bo już w 3 byliśmy. Czyli nic nie dodajemy na stos.

Visit: [0,3,5]

Stos: [1,2,1,2]

Teraz ponownie bierzemy ostatni element stosu. Jest to wierzchołek 2. Zdejmujemy element ze Stosu i dodajemy wierzchołki przyległe do 2 ale takie, w których nie byliśmy, czyli wierzchołek 4.

 










 


Visit: [0,3,5,2]

Stos: [1,2,1,4]

Znowu czynność powtarzamy w taki sam sposób. Więc 4 idzie do Visit, a 6 na Stos.

 

















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

Stos: [1,2,1,6]

Teraz kolejny element, czyli 6 do Visit. I zdejmujemy go ze stosu.

Visit:[0,3,5,2,4,6]

Stos: [1,2,1]

Teraz ponownie bierzemy ostatni element ze Stosu. Dodajemy do Visit 1.

 










 


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

Stos: [1,2]

My już zauważyliśmy, że przeszliśmy cały graf, ale program tego jeszcze nie wie, więc kontynuuje swoją prace, ale wierzchołek 2 był już odwiedzony, więc zostaje zdjęty ze stosu i nic się z nim nie robi. Następnie wierzchołek 1 również był odwiedzony i zdejmujemy go ze Stosu. Nasz Stos teraz jest pusty, więc program kończy swoje działanie. Jeśli nasz graf był grafem spójnym to w liście Visit powinny znajdować się wszystkie wierzchołki. Kolejność przechodzenia wierzchołków może być trochę inna, ale zawsze po przejściu DFS powinniśmy otrzymać graf acykliczny (zielony zaznaczony). Możemy zrobić tak, że nie będziemy dodawać zdublowanych elementów na Stos co może przyspieszyć nasz program. Ale spowoduje to, że troszeczkę inaczej będziemy przez graf przechodzić.

KOD:

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

///............................DFS.............(w głąb)......................///

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

void add_queue(struct graf **root,struct graf *top){

// dodawanie na koniec naszych list

// argumentami funkcj jest głowa listy (Stos/Visit) i wierzchołek

    struct graf *new_elem=(struct graf*)malloc(sizeof(struct graf));

    struct graf *w=*root,*y;

    new_elem->next=new_elem->prev=NULL;

    new_elem->top=top->top;

    new_elem->branch=top->branch;

    if(!w)*root=new_elem;

    else{

        while(w->next){

        w=w->next;

    }

    w->next=new_elem;

    new_elem->prev=w;

   }

}

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

void write_queue(struct graf *root){

// funkcja wypisuje naszą listę

 
  while(root){

       printf(" %d ", root->top);

       root=root->next;

   }

}

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

void pop(struct graf **Stos){

// funkcja kasuje ostatni element ze Stosu

 
   struct graf *w=*Stos;

   if(!(*Stos)->next){

          free(*Stos);

          *Stos=NULL;

      }else{

          while(w->next->next)w=w->next;

          free(w->next);

          w->next=NULL;

      }

}

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

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

// funkcja główna naszego przeszukiwania

// pierwszy argument to wierzchołek który odwiedzamy

// drugi i trzeci to głowy list (Stos/Visit)

    if(!find(*Visit,root->top)) add_queue(Visit,root);

  // dodajemy wierzchołek do Visit jeżeli o tam już nie ma

 
  if(*Stos) pop(Stos); // zdejmujemy element ze stosu

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

     
  while(w){ // pętla przechodzi po wierzchołkach sąsiednich z naszym

  // warunek jeżli chcemy aby nie dodawało zdublowanych elementów na stos

       if( !find(*Visit,w->top) && !find(*Stos,w->top))

             add_queue(Stos,w->adress);
   // dodwanie wierzchołka na stos

   w=w->next;

    }

  // wypisanie naszych list

    printf("VISIT: ");

    write_queue(*Visit);

    printf(" STOS: ");

    write_queue(*Stos);

    printf("\n");

  //

    if(*Stos){ // jeżeli stos istnieje to wykonujemy jeszcze raz wszystko

        struct graf *p=*Stos;

        while(p->next)p=p->next; // p – ostatni element stosu

        DFS(p,Stos,Visit);

    }

}

// *find – to funkcja ta sama której używałem przy grafie do szukania elementu

Jak widzimy tu też wszystko opiera się o listy i działania na nich. Sama funkcja DFS jest tylko ich wykorzystaniem. Czyli dodajemy do Visit, zdejmujemy ze Stosu, dodajemy na stos nowe wierzchołki. Możemy wypisać aby widzieć jak się to nam zmienia, a następnie wywołujemy ponownie, dopóki są elementy na stosie.