Klasa II kolejka, BFS

Kolejka (ang. queue) jest sekwencyjną strukturą danych o takiej własności, iż element zapisany jako pierwszy jest również odczytywany jako pierwszy. Taka struktura w literaturze informatycznej nosi nazwę FIFO (ang. First In First Out – pierwszy wchodzi, pierwszy wychodzi). Kolejkę możemy sobie wyobrazić jako tubę – elementy wstawiamy do tuby z jednej strony, po czym przesuwają się one wewnątrz i wychodzą z drugiej strony w tej samej kolejności, w jakiej zostały do tuby włożone.

obrazek

Dla kolejki są zdefiniowane operacje:

Sprawdzenie, czy kolejka jest pusta – operacja empty zwraca true, jeśli kolejka nie zawiera żadnego elementu, w przeciwnym razie zwraca false.
Odczyt elementu z początku kolejki – operacja front zwraca wskazanie do elementu, który jest pierwszy w kolejce.
Zapis elementu na koniec kolejki – operacja push dopisuje nowy element na koniec elementów przechowywanych w kolejce.
Usunięcie elementu z kolejki – operacja pop usuwa z kolejki pierwszy element.

Jeśli porównasz te operacje z operacjami dostępnymi dla stosu, to okaże się, że obie te struktury są bardzo do siebie podobne. Różnią się jedynie kolejnością dostępu do elementów.

Kolejka jako tablica

Naturalną strukturą danych dla kolejek jest lista, jednakże w prostszych przypadkach kolejkę da się zrealizować w tablicy. W takim przypadku musimy założyć z góry maksymalny rozmiar kolejki (ilość przechowywanych w niej elementów). Będziemy potrzebowali trzech zmiennych:

Q	–	tablica, w której będzie tworzona kolejka. Tablica ma n elementów, indeksy rozpoczynają się od 0.
qptr	–	indeks elementu, który jest początkiem kolejki
qcnt	–	liczba elementów, którą przechowuje kolejka

Kolejkę tworzą kolejne elementy o indeksach rozpoczynających się od qptr. Na początku qptr wskazuje pierwszy element tablicy o indeksie 0:

obrazek

Koniec kolejki wyznacza indeks równy qptr + qcnt. Jeśli indeks ten wykracza poza ostatni element tablicy, to należy go zmniejszyć o n. Dopisanie elementu zwiększa licznik qcnt o 1:

obrazek

Odczyt elementu z kolejki polega na przetworzeniu elementu o indeksie qptr. Usunięcie elementu z kolejki polega na zwiększeniu o 1 indeksu qptr. Jeśli po zwiększeniu qptr wskazuje poza ostatni element tablicy, to qptr należy wyzerować – kolejka znów rozpocznie się od początku tablicy. Licznik qptr zawsze zmniejszamy o 1.

obrazek

Zwróć uwagę, że w tej implementacji kolejka nie zajmuje stałego położenia w tablicy. Co więcej, jej elementy mogą być rozdzielone:

obrazek

Kolejka w tablicy – algorytm sprawdzania, czy kolejka jest pusta

Wejście

qcnt

–

liczba elementów przechowywana w kolejce

Wyjście:

True, jeśli kolejka jest pusta, inaczej false

Lista kroków:

K01	Jeśli qcnt = 0, to zakończ z wynikiem true
K02:	Zakończ z wynikiem false

Kolejka w tablicy – algorytm odczytu kolejki

Wejście

Q	–	tablica, w której przechowywana jest kolejka
qcnt	–	liczba elementów przechowywana w kolejce
qptr	–	indeks początku kolejki

Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:

K01	Jeśli qcnt = 0, to zakończ z wynikiem wartość specjalna	; kolejka pusta?
K02:	Zakończ z wynikiem Q[qptr]

Kolejka w tablicy – algorytm zapisu do kolejki

Wejście

n	–	liczba elementów w tablicy
Q	–	tablica, w której przechowywana jest kolejka
qcnt	–	liczba elementów przechowywana w kolejce
qptr	–	indeks początku kolejki
v	–	dopisywany element

Wyjście:

Jeśli w tablicy jest miejsce, to do kolejki zostaje dopisana nowa wartość. Inaczej kolejka nie jest zmieniana.

Elementy pomocnicze:

–

indeks

Lista kroków:

K01	Jeśli qcnt = n, to zakończ	; sprawdzamy, czy w tablicy jest miejsce na nowy element
K02:	i ← qptr + qcnt	; wyznaczamy położenie końca kolejki
K03:	Jeśli i ≥ n, to i ← i - n	; korygujemy i w razie potrzeby
K04:	Q[i] ← v	; umieszczamy element na końcu kolejki
K05:	qcnt ← qcnt + 1	; zwiększamy liczbę elementów
K06:	Zakończ

Kolejka w tablicy – algorytm usuwania z kolejki

Wejście

n	–	liczba elementów w tablicy
Q	–	tablica, w której przechowywana jest kolejka
qcnt	–	liczba elementów przechowywana w kolejce
qptr	–	indeks początku kolejki

Wyjście:

Kolejka pomniejszona o pierwszy element.

Lista kroków:

K01	Jeśli qcnt = 0, to zakończ	; sprawdzamy, czy kolejka zawiera jakieś elementy
K02:	qcnt ← qcnt - 1	; zmniejszamy licznik elementów
K03:	qptr ← qptr + 1	; przesuwamy początek kolejki
K04:	Jeśli qptr = n, to qptr ← 0	; korygujemy indeks początku kolejki
K05:	Zakończ

Kolejka jako lista

Do realizacji kolejki posłużymy się lekko zmodyfikowaną listą jednokierunkową. Będziemy potrzebowali dwóch wskaźników:

head	–	wskaźnik pierwszego elementu na liście
tail	–	wskaźnik ostatniego elementu na liście

Nowe elementy dodajemy na koniec listy – dzięki wskaźnikowi tail szybko będziemy mogli znaleźć ostatni element i dołączyć za nim element wstawiany. Pobieranie elementów będzie się odbywało z początku listy. Budowa elementów listy jest typowa: każdy zawiera pole next, które wskazuje kolejny element na liście, oraz pole data, które zawiera przechowywane dane:

Typ elementu listy

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

Kolejka na liście – algorytm sprawdzania, czy kolejka jest pusta

Wejście

head

–

wskaźnik początku kolejki

Wyjście:

True, jeśli kolejka jest pusta, inaczej false

Lista kroków:

K01	Jeśli head = nil, to zakończ z wynikiem true
K02:	Zakończ z wynikiem false

Kolejka na liście – algorytm odczytu kolejki

Wejście

head

–

wskaźnik pierwszego elementu listy

Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:

K01	Jeśli head = 0, to zakończ z wynikiem wartość specjalna	; kolejka pusta?
K02:	Zakończ z wynikiem (head→data)

Kolejka na liście – algorytm zapisu do kolejki

Wejście

head	–	wskaźnik pierwszego elementu listy
tail	–	wskaźnik ostatniego elementu listy
v	–	dopisywany element

Wyjście:

Kolejka z dopisanym na końcu elementem o wartości v.

Elementy pomocnicze:

–

wskaźnik elementu listy

Lista kroków:

K01	Utwórz nowy element listy
K02:	p ← adres nowego elementu
K03:	(p→next) ← nil	; inicjujemy pola nowego elementu
K04:	(p→data) ← v
K05:	Jeśli tail ≠ nil, to idź do K08	; sprawdzamy, czy lista jest pusta
K06:	head ← p	; jeśli tak, to wprowadzamy do niej element jako pierwszy i ostatni
K07	Idź do K09
K08:	(tail→next) ← p	; inaczej element dołączamy na koniec listy
K09:	tail ← p	; ustawiamy element jako ostatni na liście
K10:	Zakończ

Kolejka na liście – algorytm usuwania z kolejki

Wejście

head	–	wskaźnik pierwszego elementu listy
tail	–	wskaźnik ostatniego elementu listy

Wyjście:

Kolejka pomniejszona o pierwszy element.

Elementy pomocnicze:

–

wskaźnik elementu listy

Lista kroków:

K01	Jeśli head = nil, to zakończ	; jeśli lista jest pusta, kończymy
K02:	p ← head	;zapamiętujemy adres pierwszego elementu
K03:	head ← (head→next)	;odłączamy od listy pierwszy element
K04:	Jeśli head = nil, to tail ← nil	; jeśli lista stała się pusta, to nie posiada ostatniego elementu
K05:	Usuń z pamięci element wskazywany przez p
K06:	Zakończ

Przechodzenie drzewa wszerz

Przechodzenie drzewa binarnego wszerz (ang. breadth-first search, BFS) polega na odwiedzaniu kolejnych węzłów leżących na kolejnych poziomach.

obrazek

Najpierw odwiedzamy korzeń drzewa – węzeł nr 0, który znajduje się na poziomie 0. Dalej przechodzimy do jego synów i odwiedzamy węzły nr 1 i 2 na poziomie 1. W kolejnym kroku przechodzimy do poziomu 2 i odwiedzamy kolejno węzły nr 3, 4, 5 i 6. Operację tę kontynuujemy, aż do przejścia przez wszystkie węzły drzewa.

Tego typu przejście wymaga zapamiętywania wskazań węzłów w kolejce. Kolejka pozwala odczytywać umieszczone w niej elementy w tej samej kolejności, w jakiej zostały do niej wstawione, czyli jest jakby buforem opóźniającym. Prześledźmy przejście BFS przedstawione w poniższej tabelce (dane dopisujemy na koniec kolejki, czyli z prawej strony, a pobieramy z początku kolejki, czyli z lewej strony):

Stan przejścia	Kolejka	Przetworzone węzły	Opis
	[ A ]		Umieszczamy w kolejce węzeł startowy, czyli A. Przejście wykonywane jest w pętli dotąd, aż kolejka stanie się pusta.
	[ B C ]	A	Pobieramy z kolejki węzeł A. Odwiedzamy go. W kolejce umieszczamy dzieci węzła A, czyli węzły B i C
	[ C D E ]	A B	Pobieramy z kolejki węzeł B. Odwiedzamy go. W kolejce umieszczamy synów D i E.
	[ D E F G ]	A B C	Pobieramy z kolejki węzeł C. Odwiedzamy go. W kolejce umieszczamy synów F i G.
	[ E F G H I ]	A B C D	Pobieramy z kolejki węzeł D. Odwiedzamy go. W kolejce umieszczamy synów H i I.
	[ F G H I J ]	A B C D E	Pobieramy z kolejki węzeł E. Odwiedzamy go. W kolejce umieszczamy syna J
	[ G H I J K ]	A B C D E F	Pobieramy z kolejki węzeł F. Odwiedzamy go. W kolejce umieszczamy syna K
	[ H I J K ]	A B C D E F G	Pobieramy z kolejki węzeł G. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
	[ I J K ]	A B C D E F G H	Pobieramy z kolejki węzeł H. Odwiedzamy go. Węzeł jest liściem, więc nic nie umieszczamy w kolejce.
	[ J K ]	A B C D E F G H I	Pobieramy z kolejki węzeł I. Odwiedzamy go.
	[ K ]	A B C D E F G H I J	Pobieramy z kolejki węzeł J. Odwiedzamy go.
	[ pusta ]	A B C D E F G H I J K	Pobieramy z kolejki węzeł K. Odwiedzamy go. Kończymy przechodzenie drzewa, ponieważ kolejka jest już pusta.

Na poniższym rysunku zaznaczyliśmy linię przejścia przez kolejne węzły drzewa.

→ BFS →

Rozmiar kolejki nie przekracza 2^h, gdzie h jest wysokością drzewa.

Algorytm kolejkowy BFS dla drzewa binarnego

Wejście

v	–	wskazanie węzła startowego drzewa binarnego
h	–	wysokość drzewa

Wyjście:

przetworzenie wszystkich węzłów drzewa kolejnymi poziomami od strony lewej do prawej.

Elementy pomocnicze:

–

kolejka, której elementy są wskazaniami węzłów drzewa. Długość kolejki jest równa 2^h.

Lista kroków:

K01:	Utwórz pustą kolejkę Q
K02:	Q.push(v)	; zapamiętujemy wskazanie węzła startowego w kolejce
K03:	Dopóki Q.empty() = false: wykonuj K04...K08
K04:	v ← Q.front()	; pobieramy wskazanie węzła z początku kolejki
K05:	Q.pop()	; usuwamy pobrany element z kolejki
K06:	Odwiedź węzeł wskazywany przez v	; przetwarzamy węzeł
K07:	Jeśli (v→left) ≠ nil, to Q.push(v→left)	; jeśli węzeł ma lewego syna, to umieszczamy jego wskazanie w kolejce
K08:	Jeśli (v→right) ≠ nil, to Q.push(v→right)	; jeśli węzeł ma prawego syna, to umieszczamy jego wskazanie w kolejce
K09:	Zakończ

Informatyka dla klas II

Kolejka

Kolejka jako tablica

Kolejka w tablicy – algorytm sprawdzania, czy kolejka jest pusta

Wejście

Wyjście:

Kolejka w tablicy – algorytm odczytu kolejki

Wejście

Wyjście:

Kolejka w tablicy – algorytm zapisu do kolejki

Wejście

Wyjście:

Elementy pomocnicze:

Kolejka w tablicy – algorytm usuwania z kolejki

Wejście

Wyjście:

Kolejka jako lista

Typ elementu listy

Kolejka na liście – algorytm sprawdzania, czy kolejka jest pusta

Wejście

Wyjście:

Kolejka na liście – algorytm odczytu kolejki

Wejście

Wyjście:

Kolejka na liście – algorytm zapisu do kolejki

Wejście

Wyjście:

Elementy pomocnicze:

Kolejka na liście – algorytm usuwania z kolejki

Wejście

Wyjście:

Elementy pomocnicze:

Przechodzenie drzewa wszerz

Algorytm kolejkowy BFS dla drzewa binarnego

Wejście

Wyjście:

Elementy pomocnicze: