Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
ProblemNależy wykonać przejście 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:
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.
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. |
Q | – | kolejka. |
u | – | wierzchołek roboczy, u ∈ C. |
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.
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. |
Q | – | kolejka. |
i | – | indeks, i ∈ C. |
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 )
![]() 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 |
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 ):
|
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 |
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. |
Q | – | kolejka. |
p | – | wskaźnik elementu listy sąsiedztwa. |
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.
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 ):
|
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 |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
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.