REPREZENTACJA GRAFU

 

CO trzeba umieć:

-- LISTY 

-- HASH-OWANIE

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

Graf reprezentujemy za pomocą macierzy przejść, tzn. takiej tabelki, w której pokazany jest wierzchołek, a potem wierzchołki gdzie możemy przejść.

np.:                      

0 1,3,4

1 0,4

2 1,3

3 0,2,4

4 3

Wierzchołki będziemy numerować od 0, ponieważ informatycy liczą od zera :P. Nazwy wierzchołków mogą być dowolne nawet literami alfabetu, ale jednak używanie liczb naturalnych jest wygodniejsze. A i oczywiście zakładam, że wiesz co oznaczają te strzałeczki i kreski na grafie (np. z Teorii Grafów i Sieci).

Jak widzimy możemy to zinterpretować za pomocą list. Więc mamy jedną listę, w której trzymamy wierzchołki od 0 do 4. Następnie mamy drugą listę w której trzymamy gałęzie. A teraz żebyś sobie to jakoś wyobraziła. Mamy funkcję hash-ująca „wierzchołek” i temu wierzchołkowi przypisuje element, ale ten element jest elementem listy z gałęziami. Element lista z gałęziami (tak naprawdę z łukami) zawiera adres wierzchołka do którego wchodzi.

Dodawanie połączenia między wierzchołkami (dodajemy łuk, czyli np. od 0 do 4). W praktyce oznacza to do listy gałęzi wierzchołka 0 dodajemy wierzchołek 4. Jeśli nasz graf ma krawędź z 0 do 4 to musimy dodać dodatkowo połączenie od 4 do 0.

Tyle jeśli chodzi o samą ideę grafów. Reszta to już działania na listach, a że jak już dotąd dotarłeś to listy juś umiesz, więc już nie będę się w nie zagłębiał tylko od razu polecimy z kodami. :)

STRUKTURY:

struct graf{ // struktura do listy z wierzchołkami

      int top; // nazwa wierzchołka

      struct graf *next,*prev; // wskazania listy dwukierunkowej

      struct branch *branch;

// wskazanie na listę z gałęziami,
// dla każdego wierzchołka inna głowa (inna lista)

};

struct branch{ // struktura listy gałęzi(łuków)

   int top; // nazwa wierzchołka

       struct branch *next, *prev; // wskazania listy dwukierunkowej

       struct graf *adress; //adres wierzchołka w liście wierzchołków

};

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

///............................GRAF..........................................///

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

void add_top(struct graf **root, int top){

// funkcja dodająca elementy do listy w określonej kolejności

// omawiałem ją przy listach, nie wiele się zmieniła

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

      struct graf *w=*root;

      new_top->next=new_top->prev=NULL;

      new_top->branch=NULL;

      new_top->top=top;

      if(!(*root)) *root=new_top;

      else{

          while(w->next && w->top != top) w=w->next;

          if(!w->next && w->top != top){
     // warunek, aby nie dodwało tego samego wierzchołka drugi raz

                  w->next=new_top;

                  new_top->prev=w;

          }

      }

}

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

void add_branch(struct branch **head, struct graf *top){

// funkcja podobna do tej wyżej, różnicą jest to,
// że dodajemy wierzchołek grafu

 

   struct branch *new_branch=(struct branch *)malloc(sizeof(struct branch));

      struct branch *w=*head,*y;

      int f=1; // flaga

      new_branch->next=new_branch->prev=NULL;

      new_branch->adress=top;

      new_branch->top=top->top;

      if(!(*head)) *head=new_branch;

      else{

           while(w && w->top < top->top){

                y=w;

                w=w->next;

           }

           if(w)if(w->top == top->top) f=0;
      // warunek, aby nie dodawało tego samego połączenia jeszcze raz

           if(f==1){

                if(w==*head){

                     new_branch->next=*head;

                    (*head)->prev=new_branch;

                    *head=new_branch;

                }else{

                    y->next=new_branch;

                    new_branch->prev=y;

                    new_branch->next=w;

                    if(w) w->prev=new_branch;

               }

          }

     }

}

Samo dodawanie elementów do grafu jest bardzo proste pod warunkiem, że umie się listy i to umie się całkiem dobrze te listy. W zasadzie nie ma specjalnie czego omawiać, bo już to zrobiłem, gdy omawiałem listy, więc zawsze można tam ponownie zajrzeć.

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

struct graf *find(struct graf *root, int top){

// funkcja szuka wierzchołka w liście z wierzchołkami i zwraca jego adres

      while(root && root->top != top) root=root->next;

      return root;

}

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

///.....................................WYPISYWANIE..........................///

void write_branch(struct branch *head){

// wypisuje powiązania danego wierzchołka

      while(head){

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

           head=head->next;

      }

}

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

void write_graf(struct graf *root){

// wypisuje wierzchołki

      while(root){

          printf("%d : ", root->top); // wierzchołek

           write_branch(root->branch); // wywołanie funkcji dla gałęzi

          printf("\n");

         root=root->next;

     }

}

Tutaj też w zasadzie wszystko powinno być jasne, bo nic nowego tutaj nie wymyśliłem tylko zastosowałem to co już umiesz, prawda? :)

////////////////////////////////////REMOVE//////////////////////////////////////

///................................USUWANIE..................................///

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

void remove_branch(struct branch **head, int top){

// funkcja usuwa elementy z listy z gałęziami

      struct branch *w=*head,*y;

          while(w && w->top!=top){

                y=w;

                w=w->next;

          }

          if(w){

               if(w==*head){

                    *head=(*head)->next;

                    free(w);

                    w=NULL;

               }else{

                    y->next=w->next;

                   if(w->next) w->next->prev=y;

                   free(w);

                   w=NULL;

               }

         }

}

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

void remove_graf(struct graf **head, int top){

// funkcja usuwa elementy z listy wierzchołków

 

  struct graf *w=*head,*y;

    

         while(w && w->top!=top){

               y=w;

               w=w->next;

         }

         if(w){

              if(w==*head){

                      *head=(*head)->next;

                      free(w);

                      w=NULL;

              }else{

                      y->next=w->next;

                      if(w->next) w->next->prev=y;

                      free(w);

                      w=NULL;

              }

        }

}

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

void remove_top(struct graf **root, int top){

// funkcja główna naszego usuwania

 

    struct graf *el=find(*root,top); // el-nasz wierzchołek

        remove_branch(&(el->branch),top); // gdy są pętle w wierzchołku

 

    while(el->branch){

                remove_branch(&(el->branch->adress->branch),top);

                // kasuje element w liście wierzchołka przyległego

                remove_branch(&(el->branch),el->branch->top);

                // kasuje element z listy wierzchołków przyległych

       // gdy skończą się elementy w tej liście pętla robi STOP

        }

        remove_graf(root,top); // kasuje sam wierzchołek

}

 

Z kasowaniem też wielkiej filozofii nie ma. Dwie funkcje praktycznie identyczne. Obie mają za zadanie znaleźć i skasować element. Te funkcje również omawiałem już przy listach. Natomiast ostatni funkcja jest, powiedzmy, „nowa” i na niej możemy się chwilkę zatrzymać. Funkcja remove_top jest funkcją główną naszego usuwania, więc przyjmuje graf i nazwę(numer) wierzchołka do skasowania. Zmienne el jest wskazanie na nasz wierzchołek w liście wierzchołków. Pierwsze wywołanie funkcji remove_branch jest po to aby skasować ewentualne pętle z listy przyległości. Następnie jest pętla, która wykonuje się jeśli w liście przyległości naszego wierzchołka są jeszcze elementy. Więc wchodzimy do listy przyległości przyległego wierzchołka do naszego kasowanego i usuwamy połączenie z naszym wierzchołkiem (kasujemy z tej listy nasz wierzchołek). Radzę to zdanie przeczytać tak parę razy, aż się go dobrze zrozumie, bo może być zawiłe. Następnie kasujemy przyległy wierzchołek z listy przyległości naszego wierzchołka do skasowania. Czynności te powtarzamy, aż skończą się wierzchołki w liście przyległości naszego wierzchołka. Następnie możemy bez obaw usunąć nasz wierzchołek z listy.

Wywoływanie tych funkcji może wyglądać tak:

for(i=0;i<t;i++) add_top(&root,i);
// dodajemy wierzchołki do listy wierzchołków

 

for(i=0;i<b;i++){

    scanf("%d %d",&x,&y); // odczyt połączenie

    add_branch(&find(root,x)->branch,find(root,y));

    // dodawanie ŁUK (strzałki) z x do y

     

  add_branch(&find(root,y)->branch,find(root,x));

     // dodawanie ŁUK (strzałki) z y do x

}

funkcja add_branch dodaje połączenie ale tylko w jedną stronę, czyli mamy połączenie z x do y, jeśli zakładamy że chcemy mieć graf nieskierowany (taki który nie ma łuków) musimy wywołać naszą funkcję jeszcze raz i dodać połączenie z y do x. Jeśli natomiast nasz graf może posiadać krawędzie, łuki i pętle to po prostu dodajemy połączenia pamiętając, że krawędź to łuk z x do y i z y do x.