Algorytmy i Struktury Danych - Znajdowanie ścieżki w grafie

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 możliwa ś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:

v_s : numer wierzchołka startowego, v_s ∈ C.
v_k : numer wierzchołka końcowego, v_k ≠ v_s, v_k ∈ 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.
vs : 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ę vs
     wartościami false
K02: P[v_s] ← -1 ; poprzednik wierzchołka startowego
K03: S.push(v_s) ; na stosie umieszczamy numer
     ; wierzchołka startowego
K04: vs[v_s] ← true ; wierzchołek startowy
     ; oznaczamy jako odwiedzony
K05: Dopóki S.empty() = false, ; rozpoczynamy DFS
     wykonuj kroki K06…K13
K06:   v ← S.top() ; pobieramy ze stosu
       ; numer wierzchołka
K07:   S.pop() ; usuwamy ze stosu
       ; pobrany wierzchołek
K08:   Jeśli v = v_k, ; sprawdzamy, czy bieżący
       to idź do kroku K16 ; wierzchołek jest
       ; wierzchołkiem końcowym
K09:   Dla każdego sąsiada u wierzchołka v:
       wykonuj kroki K10…K13 ; implementacja zależna
       ; od reprezentacji grafu
K10:     Jeśli vs[u] = true, ; szukamy nieodwiedzonego
         to następny obieg pętli K09 ; sąsiada
K11:     P[u] ← v ; w P[u] umieszczamy informację,
         ; skąd przyszliśmy
K12:     S.push(u) ; wierzchołek u umieszczamy na stosie
K13:     vs[u] ← true ; oznaczamy go jako odwiedzony
K14: Pisz "BRAK" ; nie ma ścieżki
K15: Zakończ
K16: Dopóki v > -1, ; cofamy się po ścieżce do wierzchołka
     wykonuj kroki K17…K18 ; startowego
K17:   Pisz v ; wypisujemy wierzchołki ścieżki
       ; w kolejności odwrotnej
K18:   v ← P[v] ; do v trafia wierzchołek poprzedni
K19: Zakończ

Przykładowe programy

Uwaga:

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.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

// 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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

  TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;
  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
  if empty then
    top := -1
  else
    top := S^.v;
end;

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

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

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

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

begin
  // Tworzymy tablice odwiedzin
  SetLength(vs, n);
  // Tablicę vs zerujemy
  for i := 0 to n-1 do
    vs[i] := false;
  // Inicjujemy stos
  S.init;
  // Tworzymy tablicę ścieżki
  SetLength(P, n);
  P[vs] := -1;
  // Na stosie umieszczamy
  // wierzchołek startowy
  S.push(vs);
  // Wierzchołek startowy
  // oznaczamy jako odwiedzony
  vs[vs] := true;
  found := false;
  while S.empty = false do
  begin
    // Pobieramy ze stosu wierzchołek v
    v := S.top;
    S.pop;
    // Sprawdzamy, czy osiągnęliśmy
    // wierzchołek końcowy
    if v = vk then
    begin
      // Zaznaczamy sukces
      found := true;
      // Przerywamy pętlę
      break;
    end;
    // Przeglądamy sąsiadów
    // wierzchołka v
    pv := A[v];
    while pv <> nil do
    begin
      u := pv^.v;
      if vs[u] = false then
      begin
        // W P zapisujemy
        // fragment ścieżki
        P[u] := v;
        // Sąsiad zostaje
        // umieszczony na stosie
        S.push(u);
        // i oznaczony jako odwiedzony
        vs[u] := true;
      end;
      // Następny sąsiad
      pv := pv^.next;
    end;
  end;
  if found = false then
    // Ścieżka nie została znaleziona
    write ('BRAK')
  else
    while v > -1 do
    begin
      // Wypisujemy wierzchołki ścieżki
      write(v:3);
      // Cofamy się do poprzedniego
      // wierzchołka ścieżki
      v := P[v];
    end;
  // Usuwamy zmienne dynamiczne
  SetLength(P, 0);
  SetLength(vs, 0);
  // Czyścimy stos
  S.destroy;
end;

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

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

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

  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // 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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listy A[v1]
    p^.next := A[v1];
    A[v1] := p;
  end;
  // Odczytujemy wierzchołek
  // startowy i końcowy ścieżki
  read(v1, v2);
  writeln;
  // Szukamy ścieżki
  DFS_Path(v1, v2);
  // 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.

C++

// 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 SLel
{
  SLel * next;
  int v;
};

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;
  public:
    // konstruktor
    Stack();
    // destruktor
    ~Stack();
    bool empty(void);
    int  top(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

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

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(empty())
    return -1;
  else
    return S->v;
}

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

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

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

// 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 * vs, found;
  int  * P, v, u, i;
  SLel * pv;

  // Tworzymy tablice odwiedzin
  vs = new bool [n];
  // Tablicę vs zerujemy
  for(i = 0; i < n; i++)
    vs[i] = false;
  // Tworzymy tablicę ścieżki
  P = new int [n];
  P [vs] = -1;
  // Na stosie umieszczamy
  // wierzchołek startowy
  S.push(vs);
  // Wierzchołek startowy
  // oznaczamy jako odwiedzony
  vs[vs] = true;
  found = false;
  while(!S.empty())
  {
    // Pobieramy ze stosu
    // wierzchołek v
    v = S.top();
    S.pop();

    // Sprawdzamy, czy osiągnęliśmy
    // wierzchołek końcowy
    if(v == vk)
    {
      // Zaznaczamy sukces
      found = true;
      // Przerywamy pętlę
      break;
    }
    // Przeglądamy sąsiadów
    // wierzchołka v
    for(pv = A[v]; pv; pv = pv->next)
    {
      u = pv->v;
      if(!vs[u])
      {
        // W P zapisujemy
        // fragment ścieżki
        P[u] = v;
        // Sąsiad zostaje umieszczony
        // na stosie
        S.push(u);
        // i oznaczony jako odwiedzony
        vs[u] = true;
      }
    }
  }
  if(!found)
    // Ścieżka nie została znaleziona
    cout << "BRAK";
  else
    while(v > -1)
    {
      // Wypisujemy wierzchołki ścieżki
      cout << setw(3) << v;
      // Cofamy się do poprzedniego
      // wierzchołka ścieżki
      v = P[v];
    }
  delete [] P;
  delete [] vs;
}

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

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

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // 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++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek
    // listy A[v1]
    p->next = A[v1];
    A[v1] = p;
  }
  // Odczytujemy wierzchołek
  // startowy i końcowy ścieżki
  cin >> v1 >> v2;
  cout << endl;
  // Szukamy ścieżki
  DFS_Path(v1, v2);
  // 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;
}

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 SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  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
  If empty() Then
    top = -1
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v    = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S Then
    e = S
    S = S->Next
    Delete e
  End If
End Sub

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

' 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 vs
  Dim As Integer Ptr P
  Dim As Integer found, v, u, i
  Dim As SLel Ptr pv

  ' Tworzymy tablice odwiedzin
  vs = New Byte [n]
  ' Tablicę vs zerujemy
  For i = 0 To n-1
    vs[i] = 0
  Next
  ' Tworzymy tablicę ścieżki
  P = New Integer [n]
  P[vs] = -1
  ' Na stosie umieszczamy
  ' wierzchołek startowy
  S.push(vs)
  ' Wierzchołek startowy
  ' oznaczamy jako odwiedzony
  vs[vs] = 1
  found = 0
  While S.empty() = 0
    ' Pobieramy ze stosu wierzchołek v
    v = S.top()
    S.pop
    ' Sprawdzamy, czy osiągnęliśmy
    ' wierzchołek końcowy
    If v = vk Then
      ' Zaznaczamy sukces
      found = 1
      ' Przerywamy pętlę
      Exit While
    End If
    ' Przeglądamy sąsiadów wierzchołka v
    pv = A[v]
    While pv
      u = pv->v
      If vs[u] = 0 Then
        ' W P zapisujemy fragment ścieżki
        P[u] = v
        ' Sąsiad zostaje umieszczony
        ' na stosie
        S.push(u)
        ' i oznaczony jako odwiedzony
        vs[u] = 1
      End If
      pv = pv->Next
    Wend     
  Wend
  If found = 0 Then
    ' Ścieżka nie została znaleziona
    Print "BRAK";
  Else          
    While v > -1
      ' Wypisujemy wierzchołki ścieżki
      Print Using "###";v;
      ' Cofamy się do poprzedniego
      ' wierzchołka ścieżki
      v = P[v]
    Wend
  EndIf
  delete [] P
  delete [] vs
End Sub

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

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

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' 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
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A[v1]
  p->next = A[v1]
  A[v1] = p
Next
' Odczytujemy wierzchołek
' startowy i końcowy ścieżki
Input #1, v1, v2
Close #1
Print
' Szukamy ścieżki
DFS_Path(v1, v2)
' 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

Python (dodatek)

# DFS-szukanie ścieżki
# Data: 21.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Klasa dla dynamicznej tablicy
# list sąsiedztwa i stosu
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Klasa stosu
class Stack:
    def __init__(self):
        # lista zawierająca stos
        self.s = None

    #---------------------
    # Metody obiektu Stack
    #---------------------

    # Destruktor
    def __del__(self):
        while self.s: self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu
    def top(self):
        if self.empty():
            return -1
        else:
            return self.s.v


    # Zapisuje na stos
    def push(self,v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Procedura szukania ścieżki
# vs-numer wierzchołka startowego
# vk-numer wierzchołka końcowego
#--------------------------------
def dfs_path(vs, vk):
    global s, a
    # Tworzymy tablice odwiedzin
    vs = [False] * n
    # Tworzymy tablicę ścieżki
    p = [0] * n
    p[vs] = -1
    # Na stosie umieszczamy
    # wierzchołek startowy
    s.push(vs)
    # Wierzchołek startowy
    # oznaczamy jako odwiedzony
    vs[vs] = True
    found = False
    while not s.empty():
        # Pobieramy ze stosu
        # wierzchołek v
        v = s.top()
        s.pop()
        # Sprawdzamy, czy osiągnęliśmy
        # wierzchołek końcowy
        if v == vk:
            # Zaznaczamy sukces
            found = True
            # Przerywamy pętlę
            break
        # Przeglądamy sąsiadów
        # wierzchołka v
        pv = a[v]
        while pv:
            u = pv.v
            if not vs[u]:
                # W P zapisujemy
                # fragment ścieżki
                p[u] = v
                # Sąsiad zostaje
                # umieszczony na stosie
                s.push(u)
                # i oznaczony jako
                # odwiedzony
                vs[u] = True
            pv = pv.next
    if not found:
        # Ścieżka nie została znaleziona
        print("BRAK", end="")
    else:
        while v > -1:
            # Wypisujemy wierzchołki
            # ścieżki
            print(v, end=" ")
            # Cofamy się do poprzedniego
            # wierzchołka ścieżki
            v = p[v]
    del p, vs

# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Stos
s = Stack()
# Czytamy liczbę wierzchołków
# i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [None] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek
    # listy A[v1]
    p.next = a[v1]
    a[v1] = p
# Odczytujemy wierzchołek
# startowy i końcowy ścieżki
x = input().split()
v1 = int(x[0])
v2 = int(x[1])
print()
# Szukamy ścieżki
dfs_path(v1, v2)
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a
print()

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

Utwórz podobny program dla grafu nieskierowanego.
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:

Wyjście:

Lista wierzchołków tworzących ścieżkę lub informacja, że ścieżka nie istnieje.

Elementy pomocnicze:

S : stos liczb całkowitych.
vs : n elementowa tablica logiczna.
dfs(v,v_k) : rekurencyjna funkcja dfs() szukająca ścieżki. Zwraca true, jeśli v = v_k. Zapisuje na stos wierzchołki tworzące ścieżkę.

Lista kroków:

K01: Wyzeruj tablicę vs[]
K02: Wyzeruj S ; ustawiamy stos
K03: Jeśli dfs(v_s,v_k) = false, ; szukamy ścieżki
     to pisz "BRAK" i zakończ
K04: Dopóki S.empty() = false, ; wypisujemy ścieżkę ze stosu
     wykonuj kroki K05…K06
K05:   Pisz S.top()
K06:   S.pop()
K07: Zakończ

Algorytm rekurencyjnej funkcji dfs(v, v_k)

Wejście:

v : numer wierzchołka bieżącego, v ∈ C.
S : stos liczb całkowitych.
v_k : numer wierzchołka docelowego, v_k ∈ C.
vs : 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: vs[v] ← true ; zaznaczamy bieżący wierzchołek
     ; jako odwiedzony
K02: S.push(v) ; bieżący wierzchołek umieszczamy na stosie
K03: Jeśli v = v_k, ; jeśli doszliśmy do wierzchołka końcowego,
     to zakończ z wynikiem true ; kończymy
K04: Dla każdego sąsiada w wierzchołka v : ; to zależy od
     wykonuj kroki K05…K06 ; sposobu reprezentacji grafu
K05:   Jeśli vs[w] = true, ; szukamy nieodwiedzonego sąsiada
       to następny obieg pętli K04
K06:   Jeśli DSF(w, v_k) = true, ; jeśli znaleziono ścieżkę,
       to zakończ z wynikiem true ; kończymy
K07: S.pop() ; ścieżki brak, usuwamy ze stosu
     ; wierzchołek bieżący
K08: Zakończ z wynikiem false ; kończymy

Przykładowe programy

Uwaga:

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.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

// 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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

  TList = array of PSLel;

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

  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
  if empty then
    top := -1
  else
    top := S^.v;
end;

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

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

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

// Rekurencyjna funkcja DFS
//-------------------------
function dfs(v : integer) : boolean;
var
  p : PSLel;
begin
  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[v] := true;
  // Zapamiętujemy wierzchołek
  // na stosie
  S.push(v);
  // Jeśli koniec, kończymy
  if v = vk then exit(true);
  // Przetwarzamy nieodwiedzonych
  // sąsiadów
  p := A[v];
  while p <> nil do
  begin
    if (vs[p^.v] = false) and
       (dfs(p^.v) = true) then exit(true);
    // Następny sąsiad
    p := p^.next;
  end;
  // Brak ścieżki, usuwamy
  // wierzchołek ze stosu
  S.pop;
  // Kończymy z wynikiem false
  exit(false);
end;

// Procedura szukania ścieżki
//---------------------------
procedure DFS_Path;
var
  i : integer;
begin
  // Tworzymy tablice odwiedzin
  SetLength(vs, n);
  // Tablicę vs zerujemy
  for i := 0 to n-1 do
    vs[i] := false;
  // Inicjujemy stos
  S.init;
  if dfs(vs) = false then
    write('BRAK')
  else
    // Wypisujemy ścieżkę
    while S.empty = false do
    begin
      write(S.top:3);
      S.pop;
    end;
  writeln;
  SetLength (vs, 0);
end;

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

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

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // 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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(vs, vk);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako vk
    p^.v := vk;
    // Dodajemy go na początek
    // listy A[vs]
    p^.next := 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.

C++

// 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 SLel
{
  SLel * next;
  int v;
};

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

  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
//-----------
Stack::~Stack()
{
  while(S) pop();
}

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

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(empty())
    return -1;
  else
    return S->v;
}

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

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

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

// Rekurencyjna funkcja DFS
//-------------------------
bool dfs(int v)
{
  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[v] = true;
  // Zapamiętujemy wierzchołek
  // na stosie
  S.push(v);
  // Jeśli koniec, kończymy
  if(v == vk)
    return true;
  // Przetwarzamy nieodwiedzonych
  // sąsiadów
  for(SLel * p = A[v]; p; p = p->next)
    if(!vs[p->v] && dfs(p->v))
      return true;
  // Brak ścieżki, usuwamy wierzchołek
  // ze stosu
  S.pop();
  // Kończymy z wynikiem false
  return false;
}

// Procedura szukania ścieżki
//---------------------------
void DFS_Path()
{
  // Tworzymy tablice odwiedzin
  vs = new bool [n];
  // Tablicę vs zerujemy
  for(int i = 0; i < n; i++)
    vs[i] = false;
  if(!dfs(vs))
    cout << "BRAK";
  else
    // Wypisujemy ścieżkę
    while(!S.empty())
    {
      cout << setw(3) << S.top();
      S.pop();
    }
  cout << endl;
  delete [] vs;
}

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

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

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // 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++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> vs >> vk;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako vk
    p->v = vk;
    // Dodajemy go na początek
    // listy A[vs]
    p->next = 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;
}

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 SLel
  next As SLel Ptr
  v As Integer
End Type

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

  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
  If empty Then
    top = -1
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v    = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  EndIf
End Sub

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

' Rekurencyjna funkcja DFS
'-------------------------
Function dfs(byval v As Integer) _
                     As Integer
  Dim As SLel Ptr p

  ' Oznaczamy wierzchołek
  ' jako odwiedzony
  vs[v] = 1
  ' Zapamiętujemy wierzchołek na stosie
  S.push(v)
  ' Jeśli koniec, kończymy
  If v = vk Then Return 1
  ' Przetwarzamy nieodwiedzonych
  ' sąsiadów
  p = A[v]
  While p
    if (vs[p->v] = 0) AndAlso _
       (dfs(p->v) = 1) Then Return 1
    p = p->Next
  Wend
  ' Brak ścieżki, usuwamy
  ' wierzchołek ze stosu
  S.pop
  ' Kończymy z wynikiem false
  Return 0
End Function

' Procedura szukania ścieżki
'---------------------------
Sub DFS_Path
  Dim i As Integer
  
  ' Tworzymy tablice odwiedzin
  vs = New Byte [n]
  ' Tablicę vs zerujemy
  For i = 0 To n-1
    vs[i] = 0
  Next
  If dfs(vs) = 0 Then
    Print "BRAK";
  Else
    ' Wypisujemy ścieżkę
    While S.empty = 0
      Print Using "###";S.top;
      S.pop
    Wend
  End If
  Print
  Delete [] vs
End Sub

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

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

Open Cons For Input As #1
' Czytamy liczbę wierzchołków
' i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' 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
  ' Wierzchołek startowy
  ' i końcowy krawędzi
  Input #1, vs, vk
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako vk
  p->v = vk
  ' Dodajemy go na początek listy A[vs]
  p->next = A[vs]
  A[vs] = p
Next
' Odczytujemy wierzchołek
' startowy i końcowy ścieżki
Input #1, vs, vk
Close #1
Print
' Szukamy ścieżki
DFS_Path
' 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

Python (dodatek)

# DFS-szukanie ścieżki
# Data: 22.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# Klasa dla dynamicznej tablicy
# list sąsiedztwa i stosu
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Klasa stosu: Stack
#-------------------
class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu
    def top(self):
        if self.empty():
            return -1
        else:
            return self.s.v


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Rekurencyjna funkcja DFS
def dfs(v):
    global a, s, vs, vk
    # Oznaczamy wierzchołek
    # jako odwiedzony
    vs[v] = 1
    # Zapamiętujemy wierzchołek na stosie
    s.push(v)
    # Jeśli koniec, kończymy
    if v == vk: return True
    # Przetwarzamy nieodwiedzonych
    # sąsiadów
    p = a[v]
    while p:
        if (not vs[p.v]) and dfs(p.v):
            return True
        p = p.next
    # Brak ścieżki, usuwamy
    # wierzchołek ze stosu
    s.pop()
    # Kończymy z wynikiem false
    return False


# Procedura szukania ścieżki
def dfs_path():
    global a, s, vs, n, vs, vk
    # Tworzymy tablice odwiedzin
    vs = [False] * n
    if not dfs(vs):
        print("BRAK", end="")
    else:
        # Wypisujemy ścieżkę
        while not s.empty():
            print("%3d" % s.top(), end="")
            s.pop()
    print()
    vs = None


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Stos
s = Stack()
# Czytamy liczbę wierzchołków
# i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [None] * n
#Tworzymy tablicę odwiedzin
vs = None
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    vs = int(x[0])
    vk = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako vk
    p.v = vk
    # Dodajemy go na początek listy A[vs]
    p.next = a[vs]
    a[vs] = p
# Odczytujemy wierzchołek
# startowy i końcowy ścieżki
x = input().split()
vs = int(x[0])
vk = int(x[1])
print()
# Szukamy ścieżki
dfs_path()
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a
print()

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

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

do podrozdziału do strony

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 P[4] i P[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 P[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.
	P0] = -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 P[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:

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.
vs : 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ę vs

K02: P[v_s] ← -1 ; poprzednik wierzchołka startowego
K03: Q.push(v_s) ; w kolejce umieszczamy numer
     ; wierzchołka startowego
K04: vs[v_s] ← true ; i oznaczamy go
     ; jako odwiedzonego
K05: Dopóki Q.empty() = false, ; rozpoczynamy DFS
     wykonuj kroki K06…K13
K06:   v ← Q.front() ; pobieramy do v wierzchołek
       ; z początku kolejki
K07:   Q.pop() ; usuwamy pobrany element z kolejki
K08:   Jeśli v = v_k, ; test końca ścieżki
       to idź do kroku K16
K09:   Dla każdego sąsiada u wierzchołka v :
       wykonuj kroki K10…K13
K10:   Jeśli vs[u] = true, ; szukamy nieodwiedzonych
       to następny obieg pętli K09 ; jeszcze sąsiadów
K11:   P[u] ← v ; w P[u] umieszczamy informację o tym,
       ; skąd przyszliśmy
K12:   Q.push(u) ; jeśli nieodwiedzony, to umieszczamy
       ; sąsiada u w kolejce
K03:   vs[u] ← true ; i oznaczamy go
       ; jako odwiedzony
K14: Pisz "BRAK" ; ścieżka nie istnieje
K15: Zakończ
K16: Dopóki v > -1, 
     wykonuj kroki K17…K18
K17:   Pisz v ; wypisujemy wierzchołki ścieżki
       ; w kolejności odwrotnej
K18:   v ← P[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.

Przykładowe programy

Uwaga:

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.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

// 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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;
  TList = array of PSLel;

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

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

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

// Konstruktor
//------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor
//-----------
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 : PSLel;
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 : PSLel;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then
      tail := nil;
    dispose(p);
  end;
end;

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

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

begin
  // Inicjujemy kolejkę
  Q.init;
  // Tworzymy tablice odwiedzin
  SetLength(vs, n);
  // Tablicę vs zerujemy
  for i := 0 to n-1 do
    vs[i] := false;
  // Tworzymy tablicę ścieżki
  SetLength(P, n);
  P[vs] := -1;
  // W kolejce umieszczamy
  // wierzchołek startowy
  Q.push(vs);
  // i oznaczamy go
  // jako odwiedzony
  vs[vs] := true;
  found := false;
  while Q.empty = false do
  begin
    // Pobieramy z kolejki
    // wierzchołek v
    v := Q.front;
    Q.pop;
    // Sprawdzamy koniec ścieżki
    if v = vk then
    begin
       // Zaznaczamy sukces
      found := true;
      // Przerywamy pętlę
      break;
    end;
    // Przeglądamy sąsiadów
    // wierzchołka v
    pv := A[v];
    while pv <> nil do
    begin
      u := pv^.v;
      if vs[u] = false then
      begin
        // W P zapisujemy
        // fragment ścieżki
        P[u] := v;
        // Sąsiad zostaje
        // umieszczony w kolejce
        Q.push(u);
        // i oznaczony jako
        // odwiedzony
        vs[u] := true;
      end;
      // Następny sąsiad
      pv := pv^.next;
    end;
  end;
  if found = false then
    // Ścieżka nie została
    // znaleziona
    write('BRAK')
  else
    while v > -1 do
    begin
      // Wypisujemy wierzchołki
      // ścieżki
      write(v:3);
      // Cofamy się do poprzedniego
      // wierzchołka ścieżki
      v := P[v];
    end;
  SetLength(P, 0);
  SetLength(vs, 0);
  // Czyścimy kolejkę
  Q.destroy;
end;

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

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

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // 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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listyA [v1]
    p^.next := A[v1];
    A[v1] := p;
  end;
  // Odczytujemy wierzchołek
  // startowy i końcowy ścieżki
  read(v1, v2);
  writeln;
  // Szukamy ścieżki
  BFS_Path(v1, v2);
  // 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.

C++

// 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 SLel
{
  SLel * next;
  int v;
};

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

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

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

// Konstruktor
//------------
queue::queue()
{
  head = tail = nullptr;
}

// Destruktor
//-----------
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)
{
  SLel * p = new SLel;
  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)
  {
    SLel * p = head;
    head = head->next;
    if(!head) tail = nullptr;
    delete p;
  }
}

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

// 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 * vs, found;
  int  * P, v, u, i;
  SLel * pv;

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

  // Tworzymy tablicę ścieżki
  P = new int [n];
  P[vs] = -1;
  // W kolejce umieszczamy
  // wierzchołek startowy
  Q.push(vs);
  // i oznaczamy go
  // jako odwiedzony
  vs[vs] = true;
  found = false;
  while(!Q.empty())
  {
    // Pobieramy z kolejki
    // wierzchołek v
    v = Q.front();
    Q.pop();
    // Sprawdzamy koniec ścieżki
    if(v == vk)
    {
      // Zaznaczamy sukces
      found = true;
      // Przerywamy pętlę
      break;
    }
    // Przeglądamy sąsiadów
    // wierzchołka v
    for(pv = A[v]; pv; pv = pv->next)
    {
      u = pv->v;
      if(!vs[u])
      {
        // W P zapisujemy
        // fragment ścieżki
        P[u] = v;
        // Sąsiad zostaje
        // umieszczony w kolejce
        Q.push(u);
        // i oznaczony jako
        // odwiedzony
        vs[u] = true;
      }
    }
  }

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

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

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // Tablicę wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
    A[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek
    // listy A[v1]
    p->next = A[v1];
    A[v1] = p;
  }
  // Odczytujemy wierzchołek
  // startowy i końcowy ścieżki
  cin >> v1 >> v2;
  cout << endl;
  // Szukamy ścieżki
  BFS_Path(v1, v2);
  // 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;
}

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 SLel
  next As SLel Ptr
  v As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As SLel Ptr
    tail As SLel 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 SLel Ptr
  p = new SLel
  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 SLel Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

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

' 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 vs
  Dim As Integer Ptr P
  Dim As Integer found, v, u, i
  Dim As SLel Ptr pv

  ' Tworzymy tablice odwiedzin
  vs = new Byte [n]
  ' Tablicę vs zerujemy
  For i = 0 To n-1
    vs[i] = 0
  Next
  ' Tworzymy tablicę ścieżki
  P = new Integer [n]
  P[vs] = -1
  ' W kolejce umieszczamy
  ' wierzchołek startowy
  Q.push(vs)
  ' i oznaczamy go jako odwiedzony
  vs[vs] = 1
  found = 0
  While Q.empty() = 0
    ' Pobieramy z kolejki wierzchołek v
    v = Q.front()
    Q.pop()
    ' Sprawdzamy koniec ścieżki
    If v = vk Then
      ' Zaznaczamy sukces
      found = 1
      ' Przerywamy pętlę
      Exit While
    End If
    ' Przeglądamy sąsiadów wierzchołka v
    pv = A[v]
    While pv
      u = pv->v
      If vs[u] = 0 Then
        ' W P zapisujemy fragment ścieżki
        P[u] = v
        ' Sąsiad zostaje
        ' umieszczony w kolejce
        Q.push(u)
        ' i oznaczony jako odwiedzony
        vs[u] = 1
      End If
      pv = pv->Next
    Wend
  Wend
  If found = 0 Then
    ' Ścieżka nie została znaleziona
    Print "BRAK";
  Else
    While v > -1
      ' Wypisujemy wierzchołki ścieżki
      Print Using "###";v;
      ' Cofamy się do poprzedniego
      ' wierzchołka ścieżki
      v = P[v]
    Wend
  EndIf
  Delete [] P
  Delete [] vs
End Sub

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

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

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' 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
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A[v1]
  p->next = A[v1]
  A[v1] = p
Next
' Odczytujemy wierzchołek
' startowy i końcowy ścieżki
Input #1, v1, v2
Close #1
Print
' Szukamy ścieżki
BFSPath(v1, v2)
' 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

Python (dodatek)

# BFS-szukanie ścieżki
# Data: 23.12.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

MAXINT = 2147483647

# Klasy dla dynamicznej tablicy
# list sąsiedztwa i kolejki
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Definicja klasy queue
#----------------------
class Queue:
    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destruktor
    def __del__(self):
        while not self.empty():
            self.pop()


    # Sprawdza, czy kolejka jest pusta
    def empty(self):
        return not self.head


    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        global MAXINT
        if not self.head:
            return -MAXINT
        else:
            return self.head.v


    # Zapisuje do kolejki
    def push(self,v):

        p = SLel()
        p.v = v
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p


    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None


# Procedura szukania ścieżki
# vs-numer wierzchołka startowego
# vk-numer wierzchołka końcowego
def bfs_path(vs, vk):
    global a, n

    # Kolejka
    q = Queue()
    # Tworzymy tablice odwiedzin
    vs = [False] * n
    # Tworzymy tablicę ścieżki
    p = [0] * n
    p[vs] = -1
    # W kolejce umieszczamy
    # wierzchołek startowy
    q.push(vs)
    # i oznaczamy go jako odwiedzony
    vs[vs] = True
    found = False
    while not q.empty():
        # Pobieramy z kolejki
        # wierzchołek v
        v = q.front()
        q.pop()
        # Sprawdzamy koniec ścieżki
        if v == vk:
            # Zaznaczamy sukces
            found = True
            # Przerywamy pętlę
            break
        # Przeglądamy sąsiadów
        # wierzchołka v
        pv = a[v]
        while pv:
            u = pv.v
            if not vs[u]:
                # W P zapisujemy
                # fragment ścieżki
                p[u] = v
                # Sąsiad zostaje
                # umieszczony
                # w kolejce
                q.push(u)
                # i oznaczony jako
                # odwiedzony
                vs[u] = 1
            pv = pv.next
    if not found:
        # Ścieżka nie została
        # znaleziona
        print("BRAK", end="")
    else:
        while v > -1:
            # Wypisujemy wierzchołki
            # ścieżki
            print("%3d" % v, end="")
            # Cofamy się do
            # poprzedniego
            # wierzchołka ścieżki
            v = p[v]
    del p, vs, q


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków
# i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [None] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek
    # listy A[v1]
    p.next = a[v1]
    a[v1] = p
# Odczytujemy wierzchołek
# startowy i końcowy ścieżki
x = input().split()
v1 = int(x[0])
v2 = int(x[1])
print()
# Szukamy ścieżki
bfs_path(v1, v2)
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a

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

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

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Znajdowanie ścieżki w grafie

Problem

Rozwiązanie podstawowe

Znajdowanie jednej ze ścieżek za pomocą DFS

Rozwiązanie nr 1

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie

Rozwiązanie nr 2

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm rekurencyjnej funkcji dfs(v, v_k)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie

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

Algorytm znajdowania ścieżki przejściem BFS

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie

Znajdowanie ścieżki w grafie

Problem

Rozwiązanie podstawowe

Znajdowanie jednej ze ścieżek za pomocą DFS

Rozwiązanie nr 1

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie

Rozwiązanie nr 2

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm rekurencyjnej funkcji dfs(v, vk)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie

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

Algorytm znajdowania ścieżki przejściem BFS

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie

Algorytm rekurencyjnej funkcji dfs(v, v_k)