Algorytmy i Struktury Danych - Przechodzenie grafów wszerz

Algorytm przechodzenia wszerz (ang. breadth-first search, BFS) opisaliśmy już przy przechodzeniu drzew binarnych. Dla grafu działa on następująco:

Zaczynamy odwiedzanie od wierzchołka startowego. Następnie odwiedzamy wszystkich jego sąsiadów. Dalej odwiedzamy wszystkich nieodwiedzonych jeszcze sąsiadów sąsiadów. Itd.

Tutaj również musimy posiłkować się dodatkowym parametrem visited, jak przy algorytmie DFS, aby uniknąć zapętlenia w przypadku napotkania cyklu. Przypominam: parametr visited określa stan odwiedzin wierzchołka. Wartość false posiada wierzchołek jeszcze nie odwiedzony, a wartość true ma wierzchołek, który algorytm już odwiedził. Parametry te są zebrane w tablicy logicznej visited [ ], która posiada tyle elementów, ile jest wierzchołków w grafie. Element visited [ i ] odnosi się do wierzchołka grafu o numerze i.

Prześledźmy działanie tego algorytmu na przykładowym grafie.

	Rozpoczynamy od wierzchołka startowego.
	Wierzchołek startowy zaznaczamy jako odwiedzony (zielony) i odwiedzamy wszystkich jego sąsiadów pierwszego poziomu.
	Sąsiadów pierwszego poziomu oznaczamy jako odwiedzonych i odwiedzamy wszystkich ich sąsiadów, którzy jeszcze nie byli odwiedzeni.
	Sąsiadów drugiego poziomu oznaczamy jako odwiedzonych i odwiedzamy wszystkich ich sąsiadów, którzy jeszcze nie byli odwiedzeni.
	Sąsiadów trzeciego poziomu oznaczamy jako odwiedzonych i odwiedzamy wszystkich ich sąsiadów, którzy jeszcze nie byli odwiedzeni. Do odwiedzenia jest teraz tylko jeden taki wierzchołek.
	Sąsiada czwartego poziomu oznaczamy jako odwiedzonego i odwiedzamy wszystkich jego sąsiadów, którzy jeszcze nie byli odwiedzeni. Do odwiedzenia jest znów tylko jeden taki wierzchołek.
	Sąsiada piątego poziomu oznaczamy jako odwiedzonego i odwiedzamy wszystkich jego sąsiadów, którzy jeszcze nie byli odwiedzeni. Do odwiedzenia pozostały dwa ostatnie wierzchołki.
	Oznaczamy jako odwiedzonych dwóch sąsiadów stopnia 6. W grafie nie ma już nieodwiedzonych wierzchołków. Przejście zostało zakończone.

Taki sposób odwiedzania wierzchołków wymaga kolejki. Powód jest bardzo prosty. Kolejka jest sekwencyjną strukturą danych, z której odczytujemy elementy w kolejności ich zapisu. Na koniec kolejki wstawiamy wierzchołek startowy. Wewnątrz pętli wierzchołek ten zostanie odczytany z początku kolejki, po czym algorytm umieści w niej wszystkich nieodwiedzonych sąsiadów. W kolejnych obiegach pętli sąsiedzi ci (sąsiedzi poziomu 1) zostaną odczytani z początku kolejki, a na jej koniec zostaną wstawieni sąsiedzi poziomu 2. Gdy wszyscy sąsiedzi poziomu 1 zostaną przetworzeni, w kolejce pozostaną tylko sąsiedzi poziomu 2. Teraz oni będą odczytywani z początku kolejki, a na jej koniec trafią sąsiedzi poziomu 3. Całość będzie się powtarzała w pętli dotąd, aż algorytm przetworzy wszystkie dostępne wierzchołki w grafie.

Algorytm BFS – wersja poglądowa

Wejście:

v	–	numer wierzchołka startowego, v ∈ C.
visited	–	wyzerowana tablica logiczna n elementowa z informacją o odwiedzonych wierzchołkach.
graf	–	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.

Zmienne pomocnicze:

Q	–	kolejka.
u	–	wierzchołek roboczy, u ∈ C.

Lista kroków:

K01:	Q.push ( v )	w kolejce umieszczamy numer wierzchołka startowego
K02:	visited [ v ] ← true;	oznaczamy wierzchołek jako odwiedzony
K03:	Dopóki Q.empty( ) = false, wykonuj kroki K04...K10	tutaj jest pętla główna algorytmu BFS
K04:	v ← Q.front( )	odczytujemy z kolejki numer wierzchołka
K05:	Q.pop( )	odczytany numer usuwamy z kolejki
K06:	Przetwórz wierzchołek v	tutaj wykonujemy operacje na wierzchołku v
K07:	Dla każdego sąsiada u wierzchołka v wykonuj kroki K08...K10	przeglądamy wszystkich sąsiadów v
K08:	Jeśli visited [ u ] = true, to następny obieg pętli K07	szukamy nieodwiedzonego sąsiada
K09:	Q.push ( u )	umieszczamy go w kolejce
K10:	visited [ u ] ← true	i oznaczamy jako odwiedzonego
K11:	Zakończ

Algorytm szczegółowy zależy od wybranego sposobu reprezentacji grafu w pamięci komputera. Zmiany będą dotyczyły tylko kroku K08, w którym należy znaleźć wszystkich nieodwiedzonych sąsiadów wierzchołka v.

Algorytm BFS dla macierzy sąsiedztwa

Wejście:

n	–	liczba wierzchołków, n ∈ C.
v	–	numer wierzchołka startowego, v ∈ C.
visited	–	wyzerowana tablica logiczna n elementowa z informacją o odwiedzonych wierzchołkach.
A	–	macierz sąsiedztwa o rozmiarze n × n.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.

Zmienne pomocnicze:

Q	–	kolejka.
i	–	indeks, i ∈ C.

Lista kroków:

K01:	Q.push ( v )	w kolejce umieszczamy numer wierzchołka startowego
K02:	visited [ v ] ← true
K03:	Dopóki Q.empty( ) = false, wykonuj kroki K04...K10	tutaj jest pętla główna algorytmu BFS
K04:	v ← Q.front( )	odczytujemy z kolejki numer wierzchołka
K05:	Q.pop( )	odczytany numer usuwamy z kolejki
K06:	Przetwórz wierzchołek v	tutaj wykonujemy operacje na wierzchołku v
K07:	Dla i = 0, 1, ..., n - 1: wykonuj kroki K08...K10	przeglądamy wszystkich sąsiadów v
K08:	Jeśli ( A [ v ][ i ] = 0 ) ( visited [ i ] = true ), to następny obieg pętli K07	szukamy nieodwiedzonego sąsiada
K09:	Q.push ( i )	numer sąsiada umieszczamy w kolejce
K10:	visited [ i ] ← true	i oznaczamy go jako odwiedzonego
K11:	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, tworzy macierz sąsiedztwa i przechodzi ten graf algorytmem BFS poczynając od wierzchołka o numerze 0. Program wyświetla numery kolejno odwiedzanych wierzchołków. Kolejka jest utworzona za pomocą listy jednokierunkowej.

Przykładowe dane (od teraz wierzchołki będziemy oznaczać tylko numerami ):

14 21
0 1 0 2 0 8
1 4 1 5 1 7
2 9
3 0 3 10 3 11
4 13
5 6 5 7 5 13
7 8
8 9
10 9 10 11
12 0 12 3
13 12

Pascal

// BFS - macierz sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------

program bfs_adj;

// Typy dla dynamicznej macierzy i kolejki
type
  nptr = array of byte;  // Wiersz
  mptr = array of nptr;  // Cała macierz

  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : integer;
  end;

// Zmienne globalne
var
  n : integer;           // Liczba wierzchołków
  A : mptr;              // Macierz sąsiedztwa
  visited : array of boolean; // Tablica odwiedzin

// Procedura przejścia wszerz
//---------------------------
procedure BFS ( v : integer );
var
  i : integer;
  q, head, tail : PslistEl; // Kolejka
begin
  new ( q );                 // W kolejce umieszczamy v
  q^.next := nil;
  q^.data := v;
  head := q; tail := q;

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

  while head <> nil do
  begin
    v := head^.data;      // Odczytujemy v z kolejki

    q := head;            // Usuwamy z kolejki odczytane v
    head := head^.next;
    if head = nil then tail := nil;
    dispose ( q );

    write ( v:3 );

    for i := 0 to n - 1 do
      if( A [ v ][ i ] = 1 ) and ( visited [ i ] = false ) then
      begin
        new ( q );         // W kolejce umieszczamy nieodwiedzonych sąsiadów
        q^.next := nil;
        q^.data := i;
        if tail = nil then head := q
        else tail^.next := q;
        tail := q;
        visited [ i ] := true; // i oznaczamy ich jako odwiedzonych
      end;
  end;
end;

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

var
  m, i, j, v1, v2 : integer;

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

  SetLength ( A, n );         // Tworzymy tablicę wskaźników
  SetLength ( visited, n );   // Tworzymy tablicę odwiedzin

  for i := 0 to n - 1 do
    SetLength ( A [ i ], n ); // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for i := 0 to n - 1 do
  begin
    visited [ i ] := false; // Zerujemy tablicę odwiedzin
    for j := 0 to n - 1 do A [ i ][ j ] := 0;
  end;

  // Odczytujemy kolejne definicje krawędzi

  for i := 1 to m do
  begin
    read ( v1, v2 );        // Wierzchołek startowy i końcowy krawędzi
    A [ v1 ][ v2 ] := 1; // Krawędź v1->v2 obecna
  end;

  writeln;

  // Przechodzimy graf wszerz

  BFS ( 0 );

  // Usuwamy macierz

  for i := 0 to n - 1 do SetLength ( A [ i ], 0 );
  SetLength ( A, 0 );
  SetLength ( visited, 0 );

  writeln;
end.

C++

// BFS - macierz sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typ elementów listy dla kolejki

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

// Zmienne globalne

int n;                   // Liczba wierzchołków
char ** A;               // Macierz sąsiedztwa
bool * visited;          // Tablica odwiedzin

// Procedura przejścia wszerz
//---------------------------
void BFS ( int v )
{
  int i;
  slistEl *q, *head, *tail; // Kolejka

  q = new slistEl;        // W kolejce umieszczamy v
  q->next = NULL;
  q->data = v;
  head = tail = q;

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

  while( head )
  {
    v = head->data;       // Odczytujemy v z kolejki

    q = head;             // Usuwamy z kolejki odczytane v
    head = head->next;
    if( !head ) tail = NULL;
    delete q;

    cout << setw ( 3 ) << v;

    for( i = 0; i < n; i++ )
      if( ( A [ v ][ i ] == 1 ) && !visited [ i ] )
      {
        q = new slistEl; // W kolejce umieszczamy nieodwiedzonych sąsiadów
        q->next = NULL;
        q->data = i;
        if( !tail ) head = q;
        else tail->next = q;
        tail = q;
        visited [ i ] = true; // i oznaczamy ich jako odwiedzonych
      }
  }
}

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

int main( )
{
  int m, i, j, v1, v2;

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

  A = new char * [ n ];       // Tworzymy tablicę wskaźników
  visited = new bool [ n ];   // Tworzymy tablicę odwiedzin

  for( i = 0; i < n; i++ )
    A [ i ] = new char [ n ]; // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for( i = 0; i < n; i++ )
  {
    visited [ i ] = false; // Zerujemy tablicę odwiedzin
    for( j = 0; j < n; j++ ) A [ i ][ j ] = 0;
  }

  // Odczytujemy kolejne definicje krawędzi

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    A [ v1 ][ v2 ] = 1; // Krawędź v1->v2 obecna
  }

  cout << endl;

  // Przechodzimy graf wszerz

  BFS ( 0 );

  // Usuwamy macierz

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

  cout << endl;

  return 0;
}

Basic

' BFS - macierz sąsiedztwa
' Data: 23.07.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------

' Typ elementów listy dla kolejki

Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

' Zmienne globalne

Dim Shared As Integer n        ' Liczba wierzchołków
Dim Shared As Byte Ptr Ptr A   ' Macierz sąsiedztwa
Dim Shared As Byte Ptr visited ' Tablica odwiedzin

' Procedura przejścia wszerz
'---------------------------
Sub BFS ( byval v As Integer )

  Dim As Integer i
  Dim As slistEl Ptr q, head, tail ' Kolejka

  q = new slistEl         ' W kolejce umieszczamy v
  q->next = 0
  q->data = v
  head = q: tail = q

  visited [ v ] = 1       ' Wierzchołek v oznaczamy jako odwiedzony

  While head
    v = head->Data        ' Odczytujemy v z kolejki

    q = head              ' Usuwamy z kolejki odczytane v
    head = head->Next
    If head = 0 Then tail = 0
    delete q

    Print Using "###";v;
    For i = 0 To n - 1
      if( A [ v ][ i ] = 1 ) AndAlso ( visited [ i ] = 0 ) Then
        q = new slistEl  ' W kolejce umieszczamy nieodwiedzonych sąsiadów
        q->next = 0
        q->data = i
        If tail = 0 Then
          head = q
        Else
          tail->next = q
        End If
        tail = q
        visited [ i ] = 1  ' i oznaczamy ich jako odwiedzonych
      End If
    Next
  Wend
End Sub

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

Dim As Integer m, i, j, v1, v2

Open Cons For Input As #1

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

A = New Byte Ptr [ n ]    ' Tworzymy tablicę wskaźników
visited = New Byte [ n ]  ' Tworzymy tablicę odwiedzin

For i = 0 To n - 1
  A [ i ] = New Byte [ n ] ' Tworzymy wiersze
Next

' Macierz wypełniamy zerami

For i = 0 To n - 1
  visited [ i ] = 0        ' Zerujemy tablicę odwiedzin
  For j = 0 To n - 1
  	 A [ i ][ j ] = 0
  Next
Next

' Odczytujemy kolejne definicje krawędzi

For i = 1 To m 
  Input #1, v1, v2       ' Wierzchołek startowy i końcowy krawędzi
  A [ v1 ][ v2 ] = 1     ' Krawędź v1->v2 obecna
Next

Close #1

Print

' Przechodzimy graf wszerz

BFS ( 0 )

' Usuwamy macierz

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

Print

End

Wynik:

14 21
0 1 0 2 0 8
1 4 1 5 1 7
2 9
3 0 3 10 3 11
4 13
5 6 5 7 5 13
7 8
8 9
10 9 10 11
12 0 12 3
13 12

0 1 2 8 4 5 7 9 13 6 12 3 10 11

Algorytm BFS dla list sąsiedztwa

Wejście:

n	–	liczba wierzchołków, n ∈ C.
v	–	numer wierzchołka startowego, v ∈ C.
visited	–	wyzerowana tablica logiczna n elementowa z informacją o odwiedzonych wierzchołkach.
A	–	n elementowa tablica list sąsiedztwa.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.

Zmienne pomocnicze:

Q	–	kolejka.
p	–	wskaźnik elementu listy sąsiedztwa.

Lista kroków:

K01:	Q.push ( v )	w kolejce umieszczamy numer wierzchołka startowego
K02	visited [ v ] ← true	i oznaczamy go jako odwiedzony
K03:	Dopóki Q.empty( ) = false, wykonuj kroki K04...K12	tutaj jest pętla główna algorytmu BFS
K04:	v ← Q.front( )	odczytujemy z kolejki numer wierzchołka
K05:	Q.pop( )	odczytany numer usuwamy z kolejki
K06:	Przetwórz wierzchołek v	tutaj wykonujemy operacje na wierzchołku v
K07:	p ← A [ v ]	początek listy
K08:	Dopóki p ≠ nil: wykonuj kroki K09...K12	przeglądamy listę sąsiedztwa wierzchołka v
K09:	Jeśli visited [ p→v ] = true, to następny obieg pętli K08	szukamy nieodwiedzonego sąsiada
K10:	Q.push ( p→v )	nieodwiedzonych sąsiadów umieszczamy w kolejce
K11:	visited [ p→v ] ← true	i oznaczamy jako odwiedzonych
K12:	p ← ( p→next )	następny element listy
K13:	Zakończ

Podobnie jak w algorytmie DFS, reprezentacja grafu listami sąsiedztwa jest bardzo korzystna dla BFS, ponieważ nie są wykonywane puste przebiegi pętli wyszukującej sąsiadów.

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.

Przykładowe dane (od teraz wierzchołki będziemy oznaczać tylko numerami ):

14 21
0 1 0 2 0 8
1 4 1 5 1 7
2 9
3 0 3 10 3 11
4 13
5 6 5 7 5 13
7 8
8 9
10 9 10 11
12 0 12 3
13 12

Pascal

// BFS - listy sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bfs_adjl;

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

  TList = array of PslistEl;


// Zmienne globalne
var
  n : integer;           // Liczba wierzchołków i krawędzi
  A : TList;             // Tablica list sąsiedztwa
  visited : array of boolean; // Tablica odwiedzin

// Procedura przejścia wszerz
//---------------------------
procedure BFS ( v : integer );
var
  p, q, head, tail : PslistEl; // Kolejka
begin
  new ( q );                 // W kolejce umieszczamy v
  q^.next := nil;
  q^.v := v;
  head := q; tail := q;

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

  while head <> nil do
  begin
    v := head^.v;         // Odczytujemy v z kolejki

    q := head;            // Usuwamy z kolejki odczytane v
    head := head^.next;
    if head = nil then tail := nil;
    dispose ( q );

    write ( v:3 );
    p := A [ v ];
    while p <> nil do
    begin
      if visited [ p^.v ] = false then
      begin
        new ( q );         // W kolejce umieszczamy nieodwiedzonych sąsiadów
        q^.next := nil;
        q^.v := p^.v;
        if tail = nil then head := q
        else tail^.next := q;
        tail := q;
        visited [ p^.v ] := true; // i oznaczamy ich jako odwiedzonych
      end;
      p := p^.next;
    end;
   end;
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
  SetLength ( visited, n );  // Tworzymy tablicę odwiedzin

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do
  begin
    A [ i ] := nil;
    visited [ i ] := false;
  end;

  // 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;

  writeln;

  // Przechodzimy graf wszerz

  BFS ( 0 );

  // 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 );

  SetLength ( visited, 0 );

  writeln;

end.

C++

// BFS - listy sąsiedztwa
// Data: 23.07.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

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

// Zmienne globalne

int n;          // Liczba wierzchołków
slistEl ** A;   // Macierz sąsiedztwa
bool * visited; // Tablica odwiedzin

// Procedura przejścia wszerz
//---------------------------
void BFS (  int v )
{
  slistEl *p, *q, *head, *tail; // Kolejka

  q = new slistEl;      // W kolejce umieszczamy v
  q->next = NULL;
  q->v = v;
  head = tail = q;

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

  while( head )
  {
    v = head->v;        // Odczytujemy v z kolejki

    q = head;           // Usuwamy z kolejki odczytane v
    head = head->next;
    if( !head ) tail = NULL;
    delete q;

    cout << setw ( 3 ) << v;
 
    for( p = A [ v ]; p; p = p->next )
    if( !visited [ p->v ] )
    {
      q = new slistEl; // W kolejce umieszczamy nieodwiedzonych sąsiadów
      q->next = NULL;
      q->v = p->v;
      if( !tail ) head = q;
      else      tail->next = q;
      tail = q;
      visited [ p->v ] = true; // i oznaczamy ich jako odwiedzonych
    }
  }
}

// **********************
// *** 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
  visited = new bool [ n ]; // Tworzymy tablicę odwiedzin

  // Tablicę wypełniamy pustymi listami

  for( i = 0; i < n; i++ )
  {
    A [ i ] = NULL;
    visited [ i ] = false;
  }

  // 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;
  }

  cout << endl;

  // Przechodzimy graf wszerz

  BFS ( 0 );

  // 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;
  delete [ ] visited;

  cout << endl;

  return 0;
}

Basic

' BFS - listy sąsiedztwa
' Data: 23.07.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' 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 Byte Ptr visited   ' Tablica odwiedzin

' Procedura przejścia wszerz
'---------------------------
sub BFS ( ByVal v As Integer )

  Dim As slistEl Ptr p, q, head, tail ' Kolejka

  q = new slistEl        ' W kolejce umieszczamy v
  q->next = 0
  q->v = v
  head = q: tail = q

  visited [ v ] = 1      ' Wierzchołek v oznaczamy jako odwiedzony

  While head
    v = head->v          ' Odczytujemy v z kolejki

    q = head             ' Usuwamy z kolejki odczytane v
    head = head->Next
    If head = 0 Then tail = 0
    delete q

    Print Using "###";v;

    p = A [ v ] 
    while p <> 0
      If visited [ p->v ] = 0 Then
        q = new slistEl ' W kolejce umieszczamy nieodwiedzonych sąsiadów
        q->next = 0
        q->v = p->v
        If tail = 0 Then
          head = q
        Else
          tail->next = q
        End If
        tail = q
        visited [ p->v ] = 1  ' Wierzchołek v oznaczamy jako odwiedzony
      End If
      p = p->Next
    Wend  
  Wend
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
visited = New Byte [ n ]  ' Tworzymy tablicę odwiedzin

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A [ i ] = 0
  visited [ 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

Close #1

Print

' Przechodzimy graf wszerz

BFS ( 0 )

' 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
Delete [ ] visited

Print

End

Wynik:

14 21
0 1 0 2 0 8
1 4 1 5 1 7
2 9
3 0 3 10 3 11
4 13
5 6 5 7 5 13
7 8
8 9
10 9 10 11
12 0 12 3
13 12

0 8 2 1 9 7 5 4 13 6 12 3 11 10

Zadania

Opracuj algorytm przejścia BFS dla macierzy incydencji.
Zmodyfikuj podane programy, tak aby tworzyły reprezentację grafu nieskierowanego.

Na początek: podrozdziału 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.

Przechodzenie grafów wszerz – BFS

Problem

Rozwiązanie

Algorytm BFS – wersja poglądowa

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Algorytm BFS dla macierzy sąsiedztwa

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm BFS dla list sąsiedztwa

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Zadania