Znajdowanie ścieżki w grafie


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Rozwiązanie podstawowe
Znajdowanie jednej ze ścieżek za pomocą DFS
    Rozwiązanie nr 1
    Rozwiązanie nr 2
Znajdowanie najkrótszej ścieżki za pomocą BFS

Problem

Znaleźć ścieżkę prostą łączącą dwa wybrane wierzchołki grafu, jeśli taka istnieje.

 

 

Rozwiązanie podstawowe

Szukanie ścieżki, drogi w grafie, która łączy dwa wybrane wierzchołki jest jednym z podstawowych i często spotykanych problemów w teorii grafów. Na przykład, wyobraź sobie, że graf reprezentuje plan miasta. Skrzyżowania ulic są wierzchołkami grafu, a ulice to krawędzie, po których możemy przechodzić z jednego skrzyżowania do drugiego. Nasz problem brzmi wtedy: jak ze skrzyżowania A dojść do skrzyżowania B. Którymi ulicami jechać, aby nie utknąć w zaułku. Niektóre ulice mogą być jednokierunkowe. Inne ślepe, itd.

Problem ten można rozbić na dwa podproblemy:

Oba powyższe problemy rozwiązujemy w podobny sposób, wykorzystując przejście DFS lub BFS, które gwarantują nam odwiedzenie wszystkich dostępnych węzłów w grafie. Zasada jest następująca:

 

Rozpoczynamy przejście przez graf od wierzchołka startowego. Przejście kontynuujemy do momentu aż dojdziemy do wierzchołka końcowego lub wyczerpiemy wszystkie dostępne wierzchołki. W tym drugim przypadku ścieżka nie istnieje. W trakcie przechodzenia przez graf algorytm musi odpowiednio notować przebytą drogę, aby po dotarciu do węzła docelowego mógł ją odtworzyć.

 

Znajdowanie jednej ze ścieżek za pomocą DFS

Rozwiązanie nr 1

Do przechodzenia przez graf wykorzystamy algorytm DFS. W trakcie przechodzenia musimy notować przebytą drogę, aby otrzymać na końcu ścieżkę. Pozostaje pytanie, jak należy to zrobić. Rozwiązań jest kilka. Najprostsze z nich polega na wykorzystaniu osobnej tablicy P (ang. path – ścieżka), która składa się z tylu elementów, ile mamy wierzchołków w grafie, zatem każdy jej element odpowiada jednemu wierzchołkowi. W elementach tej tablicy zapisujemy numery wierzchołków, z których przyszliśmy w trakcie przechodzenia grafu. Jest to możliwe dlatego, że każdy wierzchołek grafu jest odwiedzany tylko jeden raz.

Działa to tak:

 

Załóżmy, że znajdujemy się w wierzchołku v. Nieodwiedzonym sąsiadem jest wierzchołek w. Gdy w algorytmie mamy zamiar przejść do wierzchołka w, to w jego elemencie P[w] zapisujemy numer wierzchołka v, czyli wierzchołek, z którego przyszliśmy do wierzchołka w. Gdy później zostanie osiągnięty wierzchołek docelowy, niech będzie to wierzchołek z, to w elemencie P[z] znajdzie się informacja, z którego wierzchołka grafu dotarliśmy do wierzchołka z, czyli jego poprzednik na ścieżce. Idąc wstecz do tego wierzchołka, niech będzie to wierzchołek y, znów w P[y] mamy informację, skąd do y dotarliśmy, czyli następny poprzednik. Zatem wystarczy teraz podążać wstecz po tych wierzchołkach, aby osiągnąć wierzchołek startowy (dla którego P[v] = -1, czyli brak poprzednika) i tak otrzymamy całą naszą ścieżkę.

 

Prześledźmy te operacje dla algorytmu DFS:

 

P[0] = -1
P[1] =  ?
P[2] =  ?
P[3] =  ?
P[4] =  ?
P[5] =  ?
P[6] =  ?
P[7] =  ?
Mamy wyznaczyć ścieżkę od wierzchołka 0 do 6. W P[0] wpisujemy -1 i rozpoczynamy przejście algorytmem DFS. Przy przechodzeniu umówmy się, że sąsiedzi będą odwiedzani w kolejności ich numerów.
P[0] = -1
P[1] =  0
P[2] =  ?
P[3] =  ?
P[4] =  ?
P[5] =  ?
P[6] =  ?
P[7] =  ?
Z wierzchołka 0 przejdziemy do 1. W P[1] zapisujemy numer wierzchołka 0, z którego wychodzimy do wierzchołka 1.
P[0] = -1
P[1] =  0

P[2] =  1
P[3] =  ?
P[4] =  ?
P[5] =  ?
P[6] =  ?
P[7] =  ?
Z 1 przechodzimy do 2 (zauważ, że gdybyśmy poszli do 3, to znaleźlibyśmy krótszą ścieżką, ale o tym komputer nie wie). Odpowiednio uaktualniamy P[2] na 1.
P[0] = -1
P[1] =  0
P[2] =  1

P[3] =  2
P[4] =  ?
P[5] =  ?
P[6] =  ?
P[7] =  ?
Z 2 przechodzimy do 3. W P[3] zapisujemy 2.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  2

P[4] =  3
P[5] =  ?
P[6] =  ?
P[7] =  ?
Z 3 idziemy do 4 (znów, gdybyśmy poszli do 5, ścieżka byłaby krótsza). W P[4] zapisujemy 3.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  2
P[4] =  3

P[5] =  4
P[6] =  ?
P[7] =  ?
Z 4 idziemy do 5. W P[5] umieszczamy 4.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  2
P[4] =  3
P[5] =  4

P[6] =  5
P[7] =  ?
Z 5 idziemy do 6. W p[6] umieszczamy 5.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  2
P[4] =  3
P[5] =  4
P[6] =  5
P[7] =  ?
Osiągnęliśmy wierzchołek docelowy. Zatem istnieje w tym grafie ścieżka od wierzchołka 0 do 6. Algorytm DFS zawsze nam taką ścieżkę znajdzie. Nie gwarantuje on nam natomiast, że będzie to najkrótsza ścieżka.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  2
P[4] =  3
P[5] =  4

P[6] =  5
P[7] =  ?

6
Informacja o ścieżce znajduje się w tablicy P (ang. path = ścieżka, droga, trasa). Aby ją odczytać musimy rozpocząć od wierzchołka końcowego ścieżki, czyli 6. Wyprowadzamy na wyjście 6, po czym za nowy wierzchołek przyjmujemy P[6], czyli 5.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  2
P[4] =  3

P[5] =  4
P[6] =  5
P[7] =  ?


6 5
Wyprowadzamy na wyjście 5 i za nowy wierzchołek przyjmujemy P[5], czyli 4.

...

   
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  2
P[4] =  3
P[5] =  4
P[6] =  5
P[7] =  ?


6 5 4 3 2 1 0
Postępujemy w ten sam sposób aż do momentu, gdy dojdziemy do wierzchołka startowego 0. P[0] ma wartość -1. Nie ma takiego wierzchołka w grafie, zatem kończymy. Na wyjściu otrzymaliśmy ciąg wierzchołków tworzących ścieżkę. Zwróć uwagę, że wierzchołki otrzymaliśmy w kierunku odwrotnym – od końca do początku. Należy zatem odwrócić ich kolejność, np. za pomocą prostego algorytmu ze stosem

 

Algorytmy znajdowania ścieżki podajemy w wersji poglądowej. Konkretne realizacje zależą od wybranej reprezentacji grafu. Jeśli jednak zapoznałeś się dokładnie z poprzednimi rozdziałami naszego artykułu, to implementacja nie powinna sprawiać ci trudności.

 

Algorytm znajdowania ścieżki przejściem DFS – wersja nr 1

Wejście
vs    numer wierzchołka startowego, vs C
vk    numer wierzchołka końcowego, vkvs, vk C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
Lista wierzchołków tworzących ścieżkę lub informacja, że ścieżka nie istnieje.
Elementy pomocnicze:
S    Stos liczb całkowitych
visited    n elementowa tablica logiczna
P    n elementowa tablica liczb całkowitych
v    wierzchołek bieżący, v C
u    wierzchołek roboczy, u C
Lista kroków:
K01: Wypełnij tablicę visited wartościami false  
K02: P[vs] ← -1 ; poprzednik wierzchołka startowego
K03: S.push(vs) ; na stosie umieszczamy numer wierzchołka startowego
K04: visited[vs] ← true; ; wierzchołek startowy oznaczamy jako odwiedzony
K05: Dopóki S.empty() = false, wykonuj K06...K13 ; rozpoczynamy DFS
K06:     vS.top() ; pobieramy ze stosu numer wierzchołka
K07:     S.pop() ; usuwamy ze stosu pobrany wierzchołek
K08:     Jeśli v = vk, to idź do K16 ; sprawdzamy, czy bieżący wierzchołek jest wierzchołkiem końcowym
K09:     Dla każdego sąsiada u wierzchołka v wykonuj K10...K13 ; implementacja zależna od reprezentacji grafu
K10:         Jeśli visited[u] = true, to następny obieg pętli K09 ; szukamy nieodwiedzonego sąsiada
K11:         P[w] ← v ; w P[u] umieszczamy informację, skąd przyszliśmy
K12:         S.push(u) ; wierzchołek w umieszczamy na stosie
K13:         visited[u] ← true ; oznaczamy go jako odwiedzonego
K14: Pisz "BRAK" ; nie ma ścieżki
K15: Zakończ  
K16: Dopóki v > -1, wykonuj K17...K18 ; cofamy się po ścieżce do wierzchołka startowego
K17:     Pisz v ; wypisujemy wierzchołki ścieżki w kolejności odwrotnej
K18:     vP[v] ; do w trafia wierzchołek poprzedni
K19: Zakończ  

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu, za którą należy podać dwie liczby: numer wierzchołka startowego oraz numer wierzchołka końcowego ścieżki. Na podstawie definicji utworzona zostaje tablica list sąsiedztwa. Następnie program szuka ścieżki algorytmem DFS pomiędzy podanymi wierzchołkami. Jeśli jej nie znajdzie, to wypisuje słowo BRAK. W przeciwnym razie zostaje wypisany ciąg numerów wierzchołków, które tworzą ścieżkę. Stos jest zaimplementowany jako obiekt.

 

Przykładowe dane:
       8 11
0 1
1 2 1 3
2 3
3 4 3 5
4 5
5 6
6 7
7 0 7 4
0
6

 

Lazarus
// DFS - szukanie ścieżki
// Data: 24.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program dfs_path;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;

// Definicja typu obiektowego stack
//---------------------------------
stack = object
  private
    S : PslistEl;  // lista przechowująca stos

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function stack.top : integer;
begin
  top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure stack.push(v : integer);
var
  e : PslistEl;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure stack.pop;
var
  e :PslistEl;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Zmienne globalne
//-----------------
var
  n : integer;             // Liczba wierzchołków
  A : TList;               // Tablica list sąsiedztwa

// Procedura szukania ścieżki
// vs - numer wierzchołka startowego
// vk - numer wierzchołka końcowego
//----------------------------------
procedure DFS_Path(vs,vk : integer);
var
  S       : stack;
  visited : array of boolean;
  P       : array of integer;
  v,u,i   : integer;
  pv      : PslistEl;
  found   : boolean;

begin
  SetLength(visited,n);    // Tworzymy tablice odwiedzin
  for i := 0 to n - 1 do   // Tablicę visited zerujemy
    visited[i] := false;

  S.init;                  // Inicjujemy stos

  SetLength(P,n);          // Tworzymy tablicę ścieżki

  P[vs] := -1;

  S.push(vs);              // Na stosie umieszczamy wierzchołek startowy

  visited[vs] := true;     // Wierzchołek startowy oznaczamy jako odwiedzony

  found := false;

  while S.empty = false do
  begin
    v := S.top;            // Pobieramy ze stosu wierzchołek v
    S.pop;

    if v = vk then         // Sprawdzamy, czy osiągnęliśmy wierzchołek końcowy
    begin
      found := true;       // Zaznaczamy sukces
      break;               // Przerywamy pętlę
    end;

    pv := A[v];          // Przeglądamy sąsiadów wierzchołka v
    while pv <> nil do
    begin
      u := pv^.v;
      if visited[u] = false then
      begin
        P[u] := v;       // W P zapisujemy fragment ścieżki
        S.push(u);       // Sąsiad zostaje umieszczony na stosie
        visited[u] := true; // i oznaczony jako odwiedzony
      end;
      pv := pv^.next;    // Następny sąsiad
    end;
  end;

  if found = false then write('BRAK') // Ścieżka nie została znaleziona
  else
    while v > -1 do
    begin
      write(v:3);  // Wypisujemy wierzchołki ścieżki
      v := P[v];   // Cofamy się do poprzedniego wierzchołka ścieżki
    end;

  // Usuwamy zmienne dynamiczne

  SetLength(P,0);
  SetLength(visited,0);
  S.destroy;              // Czyścimy stos
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  m,i,v1,v2 : integer;
  p,r : PslistEl;

begin
  read(n,m);             // Czytamy liczbę wierzchołków i krawędzi

  SetLength(A,n);        // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do A[i] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(v1,v2);        // Wierzchołek startowy i końcowy krawędzi
    new(p);             // Tworzymy nowy element
    p^.v := v2;         // Numerujemy go jako v2
    p^.next := A[v1];   // Dodajemy go na początek listy A[v1]
    A[v1] := p;
  end;

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  read(v1,v2);

  writeln;

  DFS_Path(v1,v2);      // Szukamy ścieżki

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);

  writeln;
end.
Code::Blocks
// DFS - szukanie ścieżki
// Data: 24.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu

struct slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  public:
    stack();       // konstruktor
    ~stack();      // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------
stack::stack()
{
  S = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int stack::top(void)
{
  return S->v;
}

// Zapisuje na stos
//-----------------
void stack::push(int v)
{
  slistEl * e = new slistEl;
  e->v    = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void stack::pop(void)
{
  if(S)
  {
    slistEl * e = S;
    S = S->next;
    delete e;
  }
}

// Zmienne globalne
//-----------------
int n;                   // Liczba wierzchołków
slistEl ** A;            // Macierz sąsiedztwa

// Procedura szukania ścieżki
// vs - numer wierzchołka startowego
// vk - numer wierzchołka końcowego
//----------------------------------
void DFS_Path(int vs, int vk)
{
  stack S;
  bool * visited, found;
  int  * P,v,u,i;
  slistEl * pv;

  visited = new bool[n];   // Tworzymy tablice odwiedzin
  for(i = 0; i < n; i++)   // Tablicę visited zerujemy
    visited[i] = false;

  P = new int[n];          // Tworzymy tablicę ścieżki

  P[vs] = -1;

  S.push(vs);              // Na stosie umieszczamy wierzchołek startowy

  visited[vs] = true;      // Wierzchołek startowy oznaczamy jako odwiedzony

  found = false;

  while(!S.empty())
  {
    v = S.top();           // Pobieramy ze stosu wierzchołek v
    S.pop();

    if(v == vk)            // Sprawdzamy, czy osiągnęliśmy wierzchołek końcowy
    {
      found = true;        // Zaznaczamy sukces
      break;               // Przerywamy pętlę
    }

    // Przeglądamy sąsiadów wierzchołka v

    for(pv = A[v]; pv; pv = pv->next)
    {
      u = pv->v;
      if(!visited[u])
      {
        P[u] = v;        // W P zapisujemy fragment ścieżki
        S.push(u);       // Sąsiad zostaje umieszczony na stosie
        visited[u] = true; // i oznaczony jako odwiedzony
      }
    }
  }

  if(!found) cout << "BRAK"; // Ścieżka nie została znaleziona
  else
    while(v > -1)
    {
      cout << setw(3) << v;  // Wypisujemy wierzchołki ścieżki
      v = P[v];    // Cofamy się do poprzedniego wierzchołka ścieżki
    }

  delete [] P;
  delete [] visited;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int m,i,v1,v2;
  slistEl *p,*r;

  cin >> n >> m;               // Czytamy liczbę wierzchołków i krawędzi

  A = new slistEl * [n];       // Tworzymy tablicę list sąsiedztwa

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++) A[i] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = v2;          // Numerujemy go jako v2
    p->next = A[v1];    // Dodajemy go na początek listy A[v1]
    A[v1] = p;
  }

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  cin >> v1 >> v2;

  cout << endl;

  DFS_Path(v1,v2);      // Szukamy ścieżki

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;

  cout << endl;

  return 0;
}
Free Basic
' DFS - szukanie ścieżki
' Data: 24.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------
Constructor stack()
  S = 0
End Constructor

' Destruktor
'-----------
Destructor stack()
  While S
  	 pop()
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty() As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function stack.top() As Integer
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub stack.push(ByVal v As Integer)
  Dim e As slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop()
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

' Zmienne globalne
'-----------------
Dim Shared As Integer n                   ' Liczba wierzchołków
Dim Shared As slistEl Ptr Ptr A           ' Tablica list sąsiedztwa

' Procedura szukania ścieżki
' vs - numer wierzchołka startowego
' vk - numer wierzchołka końcowego
'----------------------------------
Sub DFS_Path(vs As integer, vk As integer)
	
  Dim As stack S
  Dim As Byte Ptr visited
  Dim As Integer Ptr P
  Dim As Integer found,v,u,i
  Dim As slistEl Ptr pv

  visited = new Byte [n]   ' Tworzymy tablice odwiedzin
  For i = 0 To n - 1       ' Tablicę visited zerujemy
    visited[i] = 0
  Next

  P = new Integer [n]      ' Tworzymy tablicę ścieżki

  P[vs] = -1

  S.push(vs)               ' Na stosie umieszczamy wierzchołek startowy

  visited[vs] = 1          ' Wierzchołek startowy oznaczamy jako odwiedzony
  
  found = 0

  While S.empty() = 0

    v = S.top()            ' Pobieramy ze stosu wierzchołek v
    S.pop()

    If v = vk Then         ' Sprawdzamy, czy osiągnęliśmy wierzchołek końcowy
      found = 1            ' Zaznaczamy sukces
      Exit While           ' Przerywamy pętlę
    End If

    ' Przeglądamy sąsiadów wierzchołka v

    pv = A[v]
    While pv
      u = pv->v
      If visited[u] = 0 Then
        P[u] = v         ' W P zapisujemy fragment ścieżki
        S.push(u)        ' Sąsiad zostaje umieszczony na stosie
        visited[u] = 1   ' i oznaczony jako odwiedzony
      End If
        
      pv = pv->Next
        
    Wend      

  Wend

  If found = 0 Then
  	  Print "BRAK"; ' Ścieżka nie została znaleziona
  Else           
    While v > -1
      Print Using "###";v;  ' Wypisujemy wierzchołki ścieżki
      v = P[v]     ' Cofamy się do poprzedniego wierzchołka ścieżki
    Wend
  EndIf

  delete [] P
  delete [] visited
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer m,i,v1,v2
Dim As slistEl Ptr p,r

Open Cons For Input As #1

Input #1,n,m            ' Czytamy liczbę wierzchołków i krawędzi

A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A[i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1,v1,v2       ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = v2            ' Numerujemy go jako v2
  p->next = A[v1]      ' Dodajemy go na początek listy A[v1]
  A[v1] = p
Next

' Odczytujemy wierzchołek startowy i końcowy ścieżki

Input #1,v1,v2

Close #1

Print

DFS_Path(v1,v2)        ' Szukamy ścieżki

' Usuwamy tablicę list sąsiedztwa

For i = 0 To n - 1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A

Print

End
Wynik
8 11
0 1
1 2 1 3
2 3
3 4 3 5
4 5
5 6
6 7
7 0 7 4
0
6

6 5 3 1 0

 

Zadanie

  1. Utwórz podobny program dla grafu nieskierowanego.
  2. Utwórz podobne programy dla reprezentacji grafu macierzami sąsiedztwa i incydencji.

 

Rozwiązanie nr 2

Rozwiązanie nr 1 wykorzystywało tablicę P do przechowywania informacji o ścieżce. Nie jest to efektywne, ponieważ tablica P musi posiadać n elementów (po jednym dla każdego wierzchołka grafu). Jeśli graf jest bardzo duży, to również duża będzie tablica P. Tymczasem ścieżka nie musi przebiegać przez wszystkie wierzchołki grafu, zatem wiele komórek tablicy P nie będzie wcale wykorzystywane (tylko te, które odpowiadają odwiedzonym wierzchołkom). Z tego powodu opracowano również inne sposoby szukania ścieżki, które efektywniej wykorzystują pamięć komputera. Jednym z najprostszych jest algorytm stosowy, który przechodzi graf za pomocą rekurencyjnego przejścia DFS, a przebytą drogę zapamiętuje na stosie lub liście. Idea jego działania jest następująca:

 

Algorytm składa się z dwóch części. Pierwsza z nich ma na celu odpowiednie przygotowanie potrzebnych struktur danych. Następnie zostaje wywołana rekurencyjna funkcja DFS, która dokonuje przejścia przez graf oraz jednocześnie zapamiętuje przebytą drogę na stosie. Funkcja ta zwraca wartość logiczną true, jeśli dojdzie do wierzchołka docelowego. W takim przypadku na stosie będziemy mięli całą ścieżkę (w kierunku od końca do początku). Jeśli DFS zwróci wartość logiczną false, to ścieżka nie została znaleziona, a stos będzie pusty.

Funkcja DFS jako parametr otrzymuje numer wierzchołka bieżącego grafu, czyli wierzchołek, w do którego doszło przejście DFS. Wierzchołek oznaczamy jako odwiedzony (aby uniknąć zapętlenia) i umieszczamy go na stosie (stos zawsze przechowuje ciąg wierzchołków tworzących ścieżkę od wierzchołka startowego do bieżącego). Teraz sprawdzamy, czy bieżący wierzchołek jest wierzchołkiem docelowym. Jeśli tak, to kończymy z wynikiem true, a stos zawiera poszukiwaną ścieżkę. Jeśli nie dotarliśmy do wierzchołka końcowego, to kontynuujemy przejście DFS: szukamy kolejnych sąsiadów wierzchołka bieżącego, którzy jeszcze nie zostali odwiedzeni. Dla każdego z tych sąsiadów rekurencyjnie wywołujemy funkcję DFS. Jeśli wywołana funkcja zwróci wartość true, to ścieżka jest znaleziona i w takim przypadku przerywamy dalsze przeglądanie grafu – kończymy funkcję DFS z wartością true. Jeśli wywołana dla sąsiada funkcja DFS zwróci false, to ścieżka wciąż nie jest znaleziona. W takim przypadku wywołujemy funkcję DFS dla kolejnych sąsiadów, aż zostaną wyczerpani. Jeśli żadne z wywołań funkcji DFS dla sąsiadów bieżącego wierzchołka nie zwróci wartości true, to ze stosu usuwamy wierzchołek bieżący i kończymy funkcję DFS z wartością false, co oznacza, że ścieżka nie została znaleziona. Poszukiwanie będzie kontynuowane w innej gałęzi grafu na poprzednim poziomie rekurencji.

 

Poniżej przedstawiamy wersję poglądową tego algorytmu. Wersja implementacyjna powstaje po ustaleniu reprezentacji grafu.

 

Algorytm znajdowania ścieżki przejściem DFS – wersja nr 2

Wejście
vs    numer wierzchołka startowego, vs C
vk    numer wierzchołka końcowego, vkvs, vk C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
Lista wierzchołków tworzących ścieżkę lub informacja, że ścieżka nie istnieje.
Elementy pomocnicze:
S    stos liczb całkowitych
visited    n elementowa tablica logiczna
DFS(v)    rekurencyjna funkcja DFS() szukająca ścieżki. Zwraca true, jeśli v = vk. Zapisuje na stos wierzchołki tworzące ścieżkę.
Lista kroków:
K01: Wyzeruj tablicę visited[]  
K02: Wyzeruj S ; ustawiamy stos
K03: Jeśli DFS(vs) = false, to pisz "BRAK" i zakończ ; szukamy ścieżki
K04: Dopóki S.empty() = false, wykonuj K05...K06 ; wypisujemy ścieżkę ze stosu
K05:     Pisz S.top()  
K06:     S.pop()  
K07: Zakończ  

 

Algorytm rekurencyjnej funkcji DFS(v)

Wejście
v    numer wierzchołka bieżącego, v C
S    stos liczb całkowitych
vk    numer wierzchołka docelowego, vk C
visited    logiczna tablica odwiedzin
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
true – stos S zawiera ścieżkę,
false – ścieżka nie została znaleziona.
Elementy pomocnicze:
w    numer wierzchołka grafu, w C
Lista kroków:
K01: visited[v] ← true ; zaznaczamy bieżący wierzchołek jako odwiedzony
K02: S.push(v) ; bieżący wierzchołek umieszczamy na stosie
K03: Jeśli v = vk, to zakończ z wynikiem true ; jeśli doszliśmy do wierzchołka końcowego, kończymy
K04: Dla każdego sąsiada w wierzchołka v wykonuj K05...K06 ; to zależy od sposobu reprezentacji grafu
K05:     Jeśli visited[w] = true, to następny obieg pętli K04 ; szukamy nieodwiedzonego sąsiada
K06:     Jeśli DSF(w) = true, to zakończ z wynikiem true ; jeśli znaleziono ścieżkę, kończymy
K07: S.pop() ; ścieżki brak, usuwamy ze stosu wierzchołek bieżący
K08: Zakończ z wynikiem false ; i kończymy w tej gałęzi

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu, za którą należy podać dwie liczby: numer wierzchołka startowego oraz numer wierzchołka końcowego ścieżki. Na podstawie definicji utworzona zostaje tablica list sąsiedztwa. Następnie program szuka ścieżki algorytmem DFS pomiędzy podanymi wierzchołkami. Jeśli jej nie znajdzie, to wypisuje słowo BRAK. W przeciwnym razie zostaje wypisany ciąg numerów wierzchołków, które tworzą ścieżkę. Wierzchołki otrzymamy w kolejności odwrotnej. Stos jest zaimplementowany jako obiekt globalny.

 

Przykładowe dane:
       8 11
0 1
1 3 1 2
2 3
3 5 3 4
4 5
5 6
6 7
7 4 7 0
0
6

 

Lazarus
// DFS - szukanie ścieżki
// Data: 26.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bfs_path;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu
//-----------------------------------------------------
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;

// Definicja typu obiektowego stack
//---------------------------------
stack = object
  private
    S : PslistEl;  // lista przechowująca stos

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function stack.top : integer;
begin
  top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure stack.push(v : integer);
var
  e : PslistEl;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure stack.pop;
var
  e :PslistEl;
begin
  if S <> NIL then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Zmienne globalne
//-----------------
var
  n : integer;           // Liczba wierzchołków i krawędzi
  A : TList;             // Tablica list sąsiedztwa
  S       : stack;       // Stos
  visited : array of boolean; // Tablica odwiedzin
  vs,vk   : integer;     // Wierzchołki startowy i końcowy ścieżki

// Rekurencyjna funkcja DFS
//-------------------------
function DFS(v : integer) : boolean;
var
  p : PslistEl;
begin
  visited[v] := true;    // Oznaczamy wierzchołek jako odwiedzony

  S.push(v);             // Zapamiętujemy wierzchołek na stosie

  if v = vk then exit(true); // Jeśli koniec, kończymy

  p := A[v];             // Przetwarzamy nieodwiedzonych sąsiadów
  while p <> nil do
  begin

    if (visited[p^.v] = false) and (DFS(p^.v) = true) then exit(true);

    p := p^.next;        // Następny sąsiad
  end;

  S.pop;                 // Brak ścieżki, usuwamy wierzchołek ze stosu
  exit(false);           // Kończymy z wynikiem false
end;

// Procedura szukania ścieżki
//---------------------------
procedure DFS_Path;
var
  i : integer;
begin
  SetLength(visited,n);  // Tworzymy tablice odwiedzin
  for i := 0 to n - 1 do // Tablicę visited zerujemy
    visited[i] := false;

  S.init;                // Inicjujemy stos

  if DFS(vs) = false then write('BRAK')
  else
    while S.empty = false do // Wypisujemy ścieżkę
    begin
      write(S.top:3);
      S.pop;
    end;

  writeln;

  SetLength(visited,0);
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  m,i : integer;
  p,r : PslistEl;

begin
  read(n,m);             // Czytamy liczbę wierzchołków i krawędzi

  SetLength(A,n);        // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do A[i] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(vs,vk);        // Wierzchołek startowy i końcowy krawędzi
    new(p);             // Tworzymy nowy element
    p^.v := vk;         // Numerujemy go jako vk
    p^.next := A[vs];   // Dodajemy go na początek listy A[vs]
    A[vs] := p;
  end;

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  read(vs,vk);

  writeln;

  // Szukamy ścieżki

  DFS_Path;

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);

  writeln;
end.
Code::Blocks
// DFS - szukanie ścieżki
// Data: 26.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu
//-----------------------------------------------------
struct slistEl
{
  slistEl * next;
  int v;
};

// Definicja typu obiektowego stack
//---------------------------------
class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  public:
    stack();       // konstruktor
    ~stack();      // destruktor
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------
stack::stack()
{
  S = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int stack::top(void)
{
  return S->v;
}

// Zapisuje na stos
//-----------------
void stack::push(int v)
{
  slistEl * e = new slistEl;
  e->v    = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void stack::pop(void)
{
  if(S)
  {
    slistEl * e = S;
    S = S->next;
    delete e;
  }
}

// Zmienne globalne
//-----------------

int n;                   // Liczba wierzchołków
slistEl ** A;            // Macierz sąsiedztwa
stack S;                 // Stos
bool * visited;          // Tablica odwiedzin
int vs,vk;               // Wierzchołki startowy i końcowy ścieżki

// Rekurencyjna funkcja DFS
//-------------------------
bool DFS(int v)
{
  visited[v] = true;     // Oznaczamy wierzchołek jako odwiedzony

  S.push(v);             // Zapamiętujemy wierzchołek na stosie

  if(v == vk) return true; // Jeśli koniec, kończymy

  // Przetwarzamy nieodwiedzonych sąsiadów

  for(slistEl * p = A[v]; p; p = p->next)
    if(!visited[p->v] && DFS(p->v)) return true;

  S.pop();               // Brak ścieżki, usuwamy wierzchołek ze stosu
  return false;          // Kończymy z wynikiem false
}

// Procedura szukania ścieżki
//---------------------------
void DFS_Path()
{
  visited = new bool [n];// Tworzymy tablice odwiedzin
  for(int i = 0; i < n; i++) // Tablicę visited zerujemy
    visited[i] = false;

  if(!DFS(vs)) cout << "BRAK";
  else
    while(!S.empty())   // Wypisujemy ścieżkę
    {
      cout << setw(3) << S.top();
      S.pop();
    }

  cout << endl;

  delete [] visited;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int m,i;
  slistEl *p,*r;

  cin >> n >> m;               // Czytamy liczbę wierzchołków i krawędzi

  A = new slistEl * [n];       // Tworzymy tablicę list sąsiedztwa

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++) A[i] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> vs >> vk;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = vk;          // Numerujemy go jako vk
    p->next = A[vs];    // Dodajemy go na początek listy A[vs]
    A[vs] = p;
  }

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  cin >> vs >> vk;

  cout << endl;

  // Szukamy ścieżki

  DFS_Path();

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;

  cout << endl;

  return 0;
}
Free Basic
' DFS - szukanie ścieżki
' Data: 26.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu
'-----------------------------------------------------
Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Definicja typu obiektowego stack
'---------------------------------
Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos

  Public:

    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------
Constructor stack()
  S = 0
End Constructor

' Destruktor
'-----------
Destructor stack()
  While S
  	 pop()
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty() As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function stack.top() As Integer
  top = S->v
End Function

' Zapisuje na stos
'-----------------
Sub stack.push(ByVal v As Integer)
  Dim e As slistEl Ptr
  e = New slistEl
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub stack.pop()
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  EndIf
End Sub

' Zmienne globalne
'-----------------
Dim Shared As Integer n                   ' Liczba wierzchołków
Dim Shared As slistEl Ptr Ptr A           ' Tablica list sąsiedztwa
Dim Shared As stack S                     ' Stos
Dim Shared As Byte Ptr visited            ' Tablica odwiedzin
Dim Shared As Integer vs,vk               ' Wierzchołki startowy i końcowy ścieżki

' Rekurencyjna funkcja DFS
'-------------------------
Function DFS(byval v As Integer) As Integer

  Dim As slistEl Ptr p

  visited[v] = 1                          ' Oznaczamy wierzchołek jako odwiedzony

  S.push(v)                               ' Zapamiętujemy wierzchołek na stosie

  If v = vk Then return 1                 ' Jeśli koniec, kończymy

  ' Przetwarzamy nieodwiedzonych sąsiadów

  p = A[v]
  While p
  	
    If (visited[p->v] = 0) AndAlso (DFS(p->v) = 1) Then Return 1
    
    p = p->Next
  Wend

  S.pop()                                 ' Brak ścieżki, usuwamy wierzchołek ze stosu
  return 0                                ' Kończymy z wynikiem false
End Function

' Procedura szukania ścieżki
'---------------------------
Sub DFS_Path

  Dim i As Integer
  
  visited = new byte [n]                  ' Tworzymy tablice odwiedzin
  For i = 0 To n - 1                      ' Tablicę visited zerujemy
    visited[i] = 0
  Next

  If DFS(vs) = 0 Then
  	 Print "BRAK";
  Else
    While S.empty() = 0                   ' Wypisujemy ścieżkę
      Print Using "###";S.top;
      S.pop
    Wend
  End If
  
  Print

  Delete [] visited
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer m,i
Dim As slistEl Ptr p,r

Open Cons For Input As #1

Input #1,n,m            ' Czytamy liczbę wierzchołków i krawędzi

A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A[i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1,vs,vk       ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = vk            ' Numerujemy go jako vk
  p->next = A[vs]      ' Dodajemy go na początek listy A[vs]
  A[vs] = p
Next

' Odczytujemy wierzchołek startowy i końcowy ścieżki

Input #1,vs,vk

Close #1

Print

DFS_Path              ' Szukamy ścieżki

' Usuwamy tablicę list sąsiedztwa

For i = 0 To n - 1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A

Print

End
Wynik
8 11
0 1
1 3 1 2
2 3
3 5 3 4
4 5
5 6
6 7
7 4 7 0
0
6

 6  5  4  3  2  1  0

 

Zadanie

  1. Utwórz podobny program dla grafu nieskierowanego.
  2. Utwórz podobne programy dla reprezentacji grafu macierzami sąsiedztwa i incydencji.

 

Znajdowanie najkrótszej ścieżki za pomocą BFS

Algorytm wykorzystujący przejście DFS gwarantuje nam znalezienie ścieżki, jeśli taka istnieje, jednak nie gwarantuje, iż będzie to ścieżka najkrótsza (o najmniejszej liczbie wierzchołków lub krawędzie). Aby otrzymać ścieżkę najkrótszą, musimy wykorzystać przejście BFS. Dlaczego? Wiąże się to ze sposobem działania przejścia BFS. Otóż najpierw są odwiedzani wszyscy sąsiedzi wierzchołka startowego. Zatem ścieżki prowadzące do tych sąsiadów z wierzchołka startowego mają wszystkie długość 1. W następnej kolejności zostaną odwiedzeni wszyscy sąsiedzi tych sąsiadów. Ścieżki będą miały długość 2. Później 3, 4... Jeśli w trakcie tego przejścia natrafimy na wierzchołek końcowy, to otrzymamy najkrótszą ścieżkę (gdyby istniała krótsza, to algorytm znalazł by ten wierzchołek wcześniej, prawda?).

Prześledźmy działanie tego algorytmu na przykładowym grafie. Do notowania przebytej drogi wykorzystujemy tablicę P na takich samych zasadach jak w rozwiązaniu nr 1 dla DFS.

 

P[0] = -1
P[1] =  ?
P[2] =  ?
P[3] =  ?
P[4] =  ?
P[5] =  ?
P[6] =  ?
P[7] =  ?
Mamy wyznaczyć ścieżkę od wierzchołka 0 do 6. W P[0] wpisujemy -1 i rozpoczynamy przejście algorytmem BFS.
P[0] = -1
P[1] =  0
P[2] =  ?
P[3] =  ?
P[4] =  ?
P[5] =  ?
P[6] =  ?
P[7] =  ?
Wierzchołek 0 ma tylko jednego sąsiada, czyli wierzchołek 1. W P[1] zapisujemy 0, czyli numer wierzchołka, z którego przyszliśmy.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  1

P[4] =  ?
P[5] =  ?
P[6] =  ?
P[7] =  ?
Wierzchołek 1 posiada dwóch sąsiadów: wierzchołki 2 i 3. Odwiedzamy je, a w P[2] i P[3] zapisujemy 1.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  1
P[4] =  3
P[5] =  3

P[6] =  ?
P[7] =  ?
Teraz odwiedzamy wszystkich sąsiadów wierzchołków 2 i 3. Są to wierzchołki 4 i 5. W T[4] i T[5] zapisujemy 3, ponieważ to są jego sąsiedzi.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  1
P[4] =  3
P[5] =  3
P[6] =  5
P[7] =  ?
Odwiedzamy sąsiadów wierzchołków 4 i 5, czyli wierzchołek 6. W T[6] zapisujemy 5.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  1
P[4] =  3
P[5] =  3
P[6] =  5
P[7] =  ?
Dotarliśmy do wierzchołka docelowego. Dalsze przechodzenie grafu nie jest nam już potrzebne. Kończymy przejście BFS.
P[0] = -1
P[1] =  0
P[2] =  1
P[3] =  1
P[4] =  3
P[5] =  3
P[6] =  5

P[7] =  ?

6 5 3 1 0
Informację o ścieżce przechowuje tablica P. Idąc po komórkach od T[6] wg ich zawartości, otrzymamy ciąg wierzchołków tworzących najkrótszą ścieżkę. Wierzchołki będą podane w kolejności odwrotnej.

 

Algorytm znajdowania ścieżki przejściem BFS

Wejście
vs    numer wierzchołka startowego, vs C
vk    numer wierzchołka końcowego, vkvs, vk C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
Lista wierzchołków tworzących najkrótszą ścieżkę lub informacja, że ścieżka nie istnieje. Wierzchołki są podawane w kierunku odwrotnym.
Elementy pomocnicze:
Q    Kolejka liczb całkowitych
visited    n elementowa tablica logiczna
P    n elementowa tablica liczb całkowitych
v    wierzchołek bieżący, v C
u    wierzchołek roboczy, u C
Lista kroków:
K01: Wyzeruj tablicę visited  
K02: P[vs] ← -1 ; poprzednik wierzchołka startowego
K03: Q.push(vs) ; w kolejce umieszczamy numer wierzchołka startowego
K04: visited[vs] ← true ; i oznaczamy go jako odwiedzonego
K05: Dopóki Q.empty() = false, wykonuj K06...K13 ; rozpoczynamy DFS
K06:     vQ.front() ; pobieramy do v wierzchołek z początku kolejki
K07:     Q.pop() ; usuwamy pobrany element z kolejki
K08:     Jeśli v = vk, to idź do K16 ; test końca ścieżki
K09:     Dla każdego sąsiada u wierzchołka v wykonuj K10...K13  
K10:         Jeśli visited[u] = true, to następny obieg pętli K09 ; szukamy nieodwiedzonych jeszcze sąsiadów
K11:         P[u] ← v ; w P[w] umieszczamy informację o tym, skąd przyszliśmy
K12:         Q.push(u) ; jeśli nie, to umieszczamy sąsiada w w kolejce
K03:         visited[u] ← true ; i oznaczamy go jako odwiedzony
K14: Pisz "BRAK" ; ścieżka nie istnieje
K15: Zakończ  
K16: Dopóki v > -1, wykonuj K17...K18  
K17:     Pisz v ; wypisujemy wierzchołki ścieżki w kolejności odwrotnej
K18:     vP[v]  
K19: Wyczyść kolejkę Q ; kolejka może coś zawierać
K20: Zakończ  

 

Zwróć uwagę, że algorytm wyszukiwania ścieżki przejściem BFS różni się od algorytmu wyszukiwania ścieżki przejściem DFS jedynie zamianą stosu S na kolejkę Q. Wszystkie pozostałe operacje są identyczne.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu, za którą należy podać dwie liczby: numer wierzchołka startowego oraz numer wierzchołka końcowego ścieżki. Na podstawie definicji utworzona zostaje tablica list sąsiedztwa. Następnie program szuka ścieżki algorytmem BFS pomiędzy podanymi wierzchołkami. Jeśli jej nie znajdzie, to wypisuje słowo BRAK. W przeciwnym razie zostaje wypisany ciąg numerów wierzchołków, które tworzą ścieżkę. Kolejka jest zaimplementowana jako lista jednokierunkowa.

 

Przykładowe dane:
       8 11
0 1
1 2 1 3
2 3
3 4 3 5
4 5
5 6
6 7
7 0 7 4
0
6

 

Lazarus
// BFS - szukanie ścieżki
// Data: 24.08.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bfs_path;

// Typy dla dynamicznej tablicy list sąsiedztwa i kolejki
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.v := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;

// Zmienne globalne
//-----------------
var
  n : integer;             // Liczba wierzchołków
  A : TList;               // Tablica list sąsiedztwa

// Procedura szukania ścieżki
// vs - numer wierzchołka startowego
// vk - numer wierzchołka końcowego
//----------------------------------
procedure BFS_Path(vs,vk : integer);
var
  Q       : queue;
  visited : array of boolean;
  P       : array of integer;
  v,u,i   : integer;
  pv      : PslistEl;
  found   : boolean;

begin
  Q.init;                  // Inicjujemy kolejkę

  SetLength(visited,n);    // Tworzymy tablice odwiedzin
  for i := 0 to n - 1 do   // Tablicę visited zerujemy
    visited[i] := false;

  SetLength(P,n);          // Tworzymy tablicę ścieżki

  P[vs] := -1;

  Q.push(vs);              // W kolejce umieszczamy wierzchołek startowy

  visited[vs] := true;     // i oznaczamy go jako odwiedzonego

  found := false;

  while Q.empty = false do
  begin
    v := Q.front;          // Pobieramy z kolejki wierzchołek v
    Q.pop;

    if v = vk then         // Sprawdzamy koniec ścieżki
    begin
      found := true;       // Zaznaczamy sukces
      break;               // Przerywamy pętlę
    end;

    pv := A[v];          // Przeglądamy sąsiadów wierzchołka v
    while pv <> nil do
    begin
      u := pv^.v;
      if visited[u] = false then
      begin
        P[u] := v;       // W P zapisujemy fragment ścieżki
        Q.push(u);       // Sąsiad zostaje umieszczony w kolejce
        visited[u] := true; // i oznaczony jako odwiedzony
      end;
      pv := pv^.next;    // Następny sąsiad
    end;
  end;

  if found = false then write('BRAK') // Ścieżka nie została znaleziona
  else
    while v > -1 do
    begin
      write(v:3);         // Wypisujemy wierzchołki ścieżki
      v := P[v];          // Cofamy się do poprzedniego wierzchołka ścieżki
    end;

  SetLength(P,0);
  SetLength(visited,0);
  Q.destroy;              // Czyścimy kolejkę
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  m,i,v1,v2 : integer;
  p,r : PslistEl;

begin
  read(n,m);             // Czytamy liczbę wierzchołków i krawędzi

  SetLength(A,n);        // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do A[i] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read(v1,v2);        // Wierzchołek startowy i końcowy krawędzi
    new(p);             // Tworzymy nowy element
    p^.v := v2;         // Numerujemy go jako v2
    p^.next := A[v1];   // Dodajemy go na początek listy A[v1]
    A[v1] := p;
  end;

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  read(v1,v2);

  writeln;

  BFS_Path(v1,v2);      // Szukamy ścieżki

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);

  writeln;

end.
Code::Blocks
// BFS - szukanie ścieżki
// Data: 24.08.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

const int MAXINT = -2147483647;

// Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

struct slistEl
{
  slistEl * next;
  int v;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

// Zmienne globalne
//-----------------
int n;                   // Liczba wierzchołków
slistEl ** A;            // Macierz sąsiedztwa

// Procedura szukania ścieżki
// vs - numer wierzchołka startowego
// vk - numer wierzchołka końcowego
//----------------------------------
void BFS_Path(int vs, int vk)
{
  queue Q;
  bool * visited, found;
  int  * P,v,u,i;
  slistEl * pv;

  visited = new bool[n];   // Tworzymy tablice odwiedzin
  for(i = 0; i < n; i++)   // Tablicę visited zerujemy
    visited[i] = false;

  P = new int[n];          // Tworzymy tablicę ścieżki

  P[vs] = -1;

  Q.push(vs);              // W kolejce umieszczamy wierzchołek startowy

  visited[vs] = true;      // i oznaczamy go jako startowy

  found = false;

  while(!Q.empty())
  {
    v = Q.front();         // Pobieramy z kolejki wierzchołek v
    Q.pop();

    if(v == vk)            // Sprawdzamy koniec ścieżki
    {
      found = true;        // Zaznaczamy sukces
      break;               // Przerywamy pętlę
    }

    // Przeglądamy sąsiadów wierzchołka v

    for(pv = A[v]; pv; pv = pv->next)
    {
      u = pv->v;
      if(!visited[u])
      {
        P[u] = v;          // W P zapisujemy fragment ścieżki
        Q.push(u);         // Sąsiad zostaje umieszczony w kolejce
        visited[u] = true; // i oznaczony jako odwiedzony  
      }
    }
  }

  if(!found) cout << "BRAK";// Ścieżka nie została znaleziona
  else
    while(v > -1)
    {
      cout << setw(3) << v;// Wypisujemy wierzchołki ścieżki
      v = P[v];            // Cofamy się do poprzedniego wierzchołka ścieżki
    }

  delete [] P;
  delete [] visited;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int m,i,v1,v2;
  slistEl *p,*r;

  cin >> n >> m;               // Czytamy liczbę wierzchołków i krawędzi

  A = new slistEl * [n];       // Tworzymy tablicę list sąsiedztwa

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++) A[i] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = v2;          // Numerujemy go jako v2
    p->next = A[v1];    // Dodajemy go na początek listy A[v1]
    A[v1] = p;
  }

  // Odczytujemy wierzchołek startowy i końcowy ścieżki

  cin >> v1 >> v2;

  cout << endl;

  BFS_Path(v1,v2);      // Szukamy ścieżki

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;

  cout << endl;

  return 0;
}
Free Basic
' BFS - szukanie ścieżki
' Data: 24.08.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

' Zmienne globalne
'-----------------
Dim Shared As Integer n                   ' Liczba wierzchołków
Dim Shared As slistEl Ptr Ptr A           ' Tablica list sąsiedztwa

' Procedura szukania ścieżki
' vs - numer wierzchołka startowego
' vk - numer wierzchołka końcowego
'----------------------------------
Sub BFSPath(vs As integer, vk As integer)
	
  Dim As queue Q
  Dim As Byte Ptr visited
  Dim As Integer Ptr P
  Dim As Integer found,v,u,i
  Dim As slistEl Ptr pv

  visited = new Byte [n]   ' Tworzymy tablice odwiedzin
  For i = 0 To n - 1       ' Tablicę visited zerujemy
    visited[i] = 0
  Next

  P = new Integer [n]      ' Tworzymy tablicę ścieżki

  P[vs] = -1

  Q.push(vs)               ' W kolejce umieszczamy wierzchołek startowy

  visited[vs] = 1          ' i oznaczamy go jako odwiedzonego

  found = 0

  While Q.empty() = 0

    v = Q.front()          ' Pobieramy z kolejki wierzchołek v
    Q.pop()

    If v = vk Then         ' Sprawdzamy koniec ścieżki
      found = 1            ' Zaznaczamy sukces
      Exit While           ' Przerywamy pętlę
    EndIf
      
    ' Przeglądamy sąsiadów wierzchołka v

    pv = A[v]
    While pv
      u = pv->v
      If visited[u] = 0 Then
        P[u] = v           ' W P zapisujemy fragment ścieżki
        Q.push(u)          ' Sąsiad zostaje umieszczony w kolejce
        visited[u] = 1     ' i oznaczony jako odwiedzony
      End If
      pv = pv->Next
    Wend
    
  Wend
  
  If found = 0 Then
  	  Print "BRAK"; ' Ścieżka nie została znaleziona
  Else
    While v > -1
      Print Using "###";v;  ' Wypisujemy wierzchołki ścieżki
      v = P[v]     ' Cofamy się do poprzedniego wierzchołka ścieżki
    Wend
  EndIf

  Delete [] P
  Delete [] visited
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer m,i,v1,v2
Dim As slistEl Ptr p,r

Open Cons For Input As #1

Input #1,n,m            ' Czytamy liczbę wierzchołków i krawędzi

A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A[i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1,v1,v2       ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = v2            ' Numerujemy go jako v2
  p->next = A[v1]      ' Dodajemy go na początek listy A[v1]
  A[v1] = p
Next

' Odczytujemy wierzchołek startowy i końcowy ścieżki

Input #1,v1,v2

Close #1

Print

BFSPath(v1,v2)        ' Szukamy ścieżki

' Usuwamy tablicę list sąsiedztwa

For i = 0 To n - 1
  p = A[i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] A

End
Wynik
8 11
0 1
1 2 1 3
2 3
3 4 3 5
4 5
5 6
6 7
7 0 7 4
0
6

 6  5  3  1  0

 

Zadanie

  1. Utwórz podobny program dla grafu nieskierowanego.
  2. Utwórz podobne programy dla reprezentacji grafu macierzami sąsiedztwa i incydencji.

 



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.