Przechodzenie grafu metodą DFS - droga w labiryncie

Napiszemy prosty program, który w sposób wizualny ilustruje działanie metody DFS. Polem doświadczalnym będzie labirynt, który zrealizujemy w tablicy kwadratowej. Labirynt jest oczywiście grafem zrealizowanym w tablicy dwuwymiarowej. Przykład obrazuje tablicę o wymiarze 9 x 9. Wymiary x i y labiryntu muszą spełniać warunek:

 

wymiar = 1 + 2 x k, k = 2,3,...

 

                                            
                 
                 
                 
                 
                 
                 
                 
                 
Najpierw wypełnimy wszystkie komórki ścianami - czyli specjalną wartością, która oznacza, iż nie można wejść do danego segmentu labiryntu. Na ekranie ściany będą wyświetlane jako segmenty ciemnoniebieskie.
                                            
                 
                 
                 
                 
                 
                 
                 
                 
W labiryncie utworzymy komory - będą to jakby odpowiedniki węzłów w grafie. Komory będą od siebie odległe o dwie komórki. Komorę zaznaczymy jako pustą - specjalna wartość, która oznacza, iż można przejść do danego segmentu. Na ekranie puste segmenty będą wyświetlane w kolorze żółtym.
                                            
                 
                 
                 
                 
                 
                 
                 
                 
Wykorzystując funkcję pseudolosową, utworzymy korytarze leżące na lewo od komór (w grafie będą one odpowiadały krawędziom). Korytarz będzie tworzony, jeśli wyrażenie rand() % stała przyjmie wartość zero. Wartość stałej wpływa na gęstość tworzenia korytarzy. Generacje korytarzy rozpoczniemy od drugiej kolumny komór.
                                            
                 
                 
                 
                 
                 
                 
                 
                 
Teraz utworzymy w podobny sposób korytarze pionowe u góry komór, poczynając od drugiego wiersza komór. W efekcie powstanie prosty labirynt korytarzy.
                                            
      S          
                 
                 
                 
                 
                 
              K  
                 
Na koniec w labiryncie określimy komorę startową S oraz końcową K. Algorytm DFS rozpocznie przechodzenie labiryntu od komory S. Jeśli dojdzie do komory K, ścieżka zostanie znaleziona.
                                            
  S          
               
  X          
                 
                 
                 
              K  
                 
Przechodząc przez labirynt, procedura DFS będzie wpisywała do komórek informację, skąd przyszła - to odpowiednik rozwijania nici wzdłuż korytarzy labiryntu. Umożliwi jej to późniejsze wycofanie się, jeśli skończy się droga. Trafiwszy do komory, DFS sprawdza, czy może przejść odpowiednio w lewo, w górę, w dół lub w prawo. Jeśli któryś z tych kierunków jest wolny (tzn. nie zawiera ściany ani nie był już wcześniej odwiedzony), DFS przechodzi zgodnie z tym kierunkiem. Gdy żaden nie jest wolny, DFS cofa się, zwijając nić, czyli wpisując do komórki informację, że została odwiedzona (odpowiednik końca przetwarzania wierzchołka w algorytmie DFS), Jeśli dojdzie do komory końcowej, ścieżka będzie znaleziona - w naszym programie ścieżkę będziemy oznaczali kolorem czerwonym. Dzięki takiemu rozwiązaniu DFS nie musi posiadać stosu - sam graf (czyli nasz labirynt) zawiera wszelkie niezbędne informacje, Które DFS potrzebuje do przechodzenia przez labirynt.

 

Ponieważ operujemy w programie kolorem, wykorzystujemy opracowaną w naszej szkole bibliotekę newconio. Informacje na temat tej biblioteki znajdziecie tutaj.

 

Code::Blocks
// Demonstracja działania procedury DFS
// wykorzystanej do poszukiwania drogi
// w labiryncie.
//-------------------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//-------------------------------------

#include <iostream>
#include <string>
#include <ctime>
#include "newconio.h"

using namespace std;

// Stałe

const int PUSTE      =  0;  // pusta komora/korytarz
const int SCIANA     =  1;  // komórka zawierająca ścianę
const int W_LEWO     =  2;  // komórka z nitką w lewo
const int W_PRAWO    =  3;  // komora z nitką w prawo
const int W_GORE     =  4;  // komora z nitką w górę
const int W_DOL      =  5;  // komora z nitką w dół
const int ODWIEDZONE =  6;  // komora już odwiedzona, bez nitki

const int KROK       = 10;  // opóźnienie kroków w ms

const int LX         = 79;  // rozmiar labiryntu w poziomie = 1 + 2 * k
const int LY         = 47;  // rozmiar labiryntu w pionie

// Zmienne globalne

int labirynt[LX][LY];       // labirynt
int xs,ys;                  // współrzędne punktu startowego
int xk,yk;                  // współrzędne punktu końcowego
int xp,yp;                  // współrzędne poszukiwacza drogi
int lk;                     // licznik kroków poszukiwacza

// Funkcja wyświetla przekazany jej tekst na środku ostatniego
// wiersza ekranu, oczekuje na wciśnięcie przez użytkownika
// klawisza i zwraca jego kod.
//------------------------------------------------------------

int czekaj(string t)
{
  int klawisz;

  fillrect(' ',0xf0,0,49,79,49);
  textcolor(RED); textbackground(WHITE);
  center(49,_pl(t));

  while(!(klawisz = getch()));

  return klawisz;
}

// Funkcja tworzy labirynt w tablicy labirynt
//-------------------------------------------

void tworz_labirynt()
{
  int x,y,c;

  // wypełniamy cały labirynt ścianami;

  for(x=0; x<LX; x++)
    for(y=0; y<LY; y++) labirynt[x][y] = SCIANA;

  // tworzymy komory i korytarze. Komory tworzone są co 2 komórki.
  // Korytarze łączą komory z lewej i z góry

  for(x=1; x<LX; x+=2)
    for(y=1; y<LY; y+=2)
    {
        labirynt[x][y] = PUSTE;        // komora
        c = 0;                         // licznik korytarzy
        if(rand() % 3 == 0)
        {
            if(x > 1)
              labirynt[x-1][y] = PUSTE; // korytarz z lewej
            c++;                        // zwiększamy licznik korytarzy
        }
        if(rand() % 3 == 0)
        {
            if(y > 1)
              labirynt[x][y-1] = PUSTE;  // korytarz z góry
            c++;                         // zwiększamy licznik korytarzy
        }
        if(c == 0)                     // jeśli nie został utworzony korytarz,
        {                              // tworzymy go z lewej albo u góry
            if(rand() % 2)
            {
                if(x > 1) labirynt[x-1][y] = PUSTE;
            }
            else
            {
                if(y > 1) labirynt[x][y-1] = PUSTE;
            }
        }
    }

    // zerujemy współrzędne początku, końca ścieżki, poszukiwacza
    // oraz licznik kroków

    xs = ys = xk = yk = xp = yp = lk = 0;
}

// Procedura wyświetla labirynt na ekranie
//----------------------------------------

void pokaz_labirynt()
{
    int x,y,rxs,rxk,rys,ryk;

    if(xp)                      // jeśli poszukiwacz jest w labiryncie,
    {
        rxs = xp-1; rxk = xp+1; // to wyświetlimy tylko fragment
        rys = yp-1; ryk = yp+1; // wokół niego - reszta labiryntu już wyświetlona
    }
    else
    {
        rxs = 0; rxk = LX-1;
        rys = 0; ryk = LY-1;
    }

    for(x = rxs; x <= rxk; x++)
      for(y = rys; y <= ryk; y++)
        switch(labirynt[x][y])
        {
            case PUSTE      : putxy(' ',0xe0,x,y); break;
            case SCIANA     : putxy(' ',0x10,x,y); break;
            case ODWIEDZONE : putxy(' ',0xf0,x,y); break;
            default         : putxy(' ',0x40,x,y); break;
        }

     if(xp + yp > 0) putxy('P',0xe4,xp,yp);  // Poszukiwacz
     if(xs + ys > 0) putxy('S',0x0c,xs,ys);  // Start
     if(xk + yk > 0) putxy('K',0x0a,xk,yk);  // Koniec

     if(lk)                                  // Licznik kroków
     {
         gotoxy(0,48);
         textattr(0x0e);
         cout << _pl("Liczba kroków : ");
         textcolor(LIGHTRED);
         cout << lk;
     }
}

// Procedura umożliwia użytkownikowi wybranie
// pozycji startowej i końcowej w labiryncie
//------------------------------------------

void ustaw_start_koniec(string t,int & x, int & y)
{
    x = y = 1;                             // rozpoczynamy w lewym górnym rogu

    while(true)
    {
        pokaz_labirynt();                  // wyświetlamy labirynt

        switch(czekaj(t))                  // czekamy na klawisz
        {                                  // i przesuwamy punkt wg klawisza
            case 72:  if(y > 1) y -= 2;    // w górę
                      break;
            case 77:  if(x < LX-2) x += 2; // w w prawo
                      break;
            case 80:  if(y < LY-2) y += 2; // w dół
                      break;
            case 75:  if(x > 1) x -= 2;    // w lewo
                      break;
            case 13:  return;              // klawisz ENTER kończy
        }
    }
}

// Procedura DFS szukająca drogi w labiryncie
// od punktu startowego do punktu końcowego
//-------------------------------------------

void szukaj_wyjscia()
{
  fillrect(' ',0xf0,0,49,79,49);
  textcolor(BLACK); textbackground(WHITE);
  center(49,_pl("Poszukiwanie ścieżki do punktu końcowego"));

  xp = xs;  // ustawiamy poszukiwacza w punkcie startowym
  yp = ys;

  labirynt[xp][yp] = ODWIEDZONE; // zaznaczamy tę komórkę jako odwiedzoną

  // DFS

  while(true)
  {
      lk++;                     // zwiększamy licznik
      pokaz_labirynt();         // wyświetlamy labirynt (fragment)
      delay(KROK);              // odczekujemy

      if(xp == xk && yp == yk)  // jeśli w punkcie końcowym, kończymy
      {
          putxy('K',0xf4,xp,yp);
          return;
      }

      // droga w lewo?

      if(labirynt[xp-1][yp] == PUSTE)
      {
          xp--;                      // przechodzimy w lewo
          labirynt[xp][yp] = W_LEWO; // rozwijamy nić w lewo
          continue;                  // wracamy na początek pętli
      }

      // brak drogi w lewo. Droga w górę?

      if(labirynt[xp][yp-1] == PUSTE)
      {
          yp--;                      // przechodzimy w górę
          labirynt[xp][yp] = W_GORE; // rozwijamy nić w górę
          continue;                  // wracamy na początek pętli
      }

      // w lewo i w górę brak drogi. Droga w prawo?

      if(labirynt[xp+1][yp] == PUSTE)
      {
          xp++;                       // przechodzimy w prawo
          labirynt[xp][yp] = W_PRAWO; // rozwijamy nić w prawo
          continue;                   // wracamy na początek pętli
      }

      // w lewo, w górę i w prawo brak drogi. Droga w dół?

      if(labirynt[xp][yp+1] == PUSTE)
      {
          yp++;                     // przechodzimy w dół
          labirynt[xp][yp] = W_DOL; // rozwijamy nić w dół
          continue;                 // wracamy na początek pętli
      }

    // nie udało się pójść w żadnym z dostępnych kierunków, gdyż
    // albo była tam ściana, albo już tam byliśmy. Próbujemy zatem
    // cofnąć się po nici do poprzedniego segmentu labiryntu.

    switch(labirynt[xp][yp])
    {
        case ODWIEDZONE : return;  // wróciliśmy na początek - brak ścieżki.
        case W_LEWO     : labirynt[xp++][yp] = ODWIEDZONE; break;
        case W_PRAWO    : labirynt[xp--][yp] = ODWIEDZONE; break;
        case W_GORE     : labirynt[xp][yp++] = ODWIEDZONE; break;
        case W_DOL      : labirynt[xp][yp--] = ODWIEDZONE; break;
    }
  }
}

int main()
{
    _cinit();
    srand(time(NULL));
    fullscreen(true);
    cursoroff();
    tworz_labirynt();
    ustaw_start_koniec("Wybierz punkt startowy i naciśnij ENTER",xs,ys);
    ustaw_start_koniec("Wybierz punkt końcowy i naciśnij ENTER",xk,yk);
    szukaj_wyjscia();
    czekaj("Koniec przejścia. Naciśnij dowolny klawisz, aby zakończyć program.");
    textattr(7);
    cursoron();
    fullscreen(false);
    return 0;
}




 

Zwróć uwagę na sposób zachowania się algorytmu DFS. Jeśli ścieżka nie zostanie znaleziona, to DFS przechodzi cały dostępny labirynt. Fragmenty nieodwiedzone przez DFS są częściami labiryntu odseparowanymi od przeglądanej części. Dzięki tej własności DFS można wykorzystywać do badania, czy graf jest spójny - uruchamiamy DFS, a następnie sprawdzamy, czy zostały odwiedzone wszystkie wierzchołki. Jeśli tak, graf jest spójny. Jeśli nie, nie jest - proste?

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.