Przechodzenie grafów wszerz – BFS


Tematy pokrewne
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

Problem

Dokonać przejścia grafu 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.
Elementy 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 K04...K10 ; tutaj jest pętla główna algorytmu BFS
K04:     vQ.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 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 x n
Wyjście:
Przetworzenie wszystkich wierzchołków w grafie.
Elementy 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 K04...K10 ; tutaj jest pętla główna algorytmu BFS
K04:     vQ.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 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  

 

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, 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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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.
Elementy 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 K04...K12 ; tutaj jest pętla główna algorytmu BFS
K04:     vQ.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:     pA[v] ; początek listy
K08:     Dopóki pnil: wykonuj K09...K12 ; przeglądamy listę sąsiedztwa wierzchołka v
K09:         Jeśli visited[pv] = true, to następny obieg pętli K08 ; szukamy nieodwiedzonego sąsiada
K10:         Q.push(pv) ; nieodwiedzonych sąsiadów umieszczamy w kolejce
K11:         visited[pv] ← true ; i oznaczamy jako odwiedzonych
K12:         p ← (pnext) ; 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.

 

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, 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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

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

 



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.