W tym punkcie omawiać będziemy grafy i szczególny ich rodzaj - drzewa. Podstawowe pojęcia dotyczące grafów były omawiane w wykładzie matematyki dyskretnej. Tu zwrócimy uwagę na sposoby przedstawiania grafu w komputerze i na operacje, które najczęściej na grafach wykonujemy.

Graf podobnie jak stos i kolejka, służy do reprezentowania zbiorów skończonych. Elementy zbioru reprezentowanego przez graf będą etykietami wierzchołków grafu. Operacje, które najczęściej wykonujemy na grafach, dotyczą dołączania lub usuwania krawędzi lub wierzchołków grafu, wyszukiwania, wstawiania i usuwania wskazanych etykiet wierzchołków. Są to więc operacje teoriomnogościowe wykonywane na wierzchołkach, krawędziach i etykietach. Koszt tych operacji jest ściśle związany ze sposobem przedstawienia grafu.

Graf reprezentujemy zwykle przez macierz sąsiedztwa lub tablicę list incydencji. Poniżej omówimy krótko obie te reprezentacje. Inne sposoby reprezentowania grafu będą tematem zadań przedstawionych w ćwiczeniach.

Niech V będzie n elementowym zbiorem, V = {v₁,...,v_n}. Macierzą sąsiedztwa dla grafu G = <V, E> nazywamy macierz kwadratową M(nxn) taką, że

Operacje dołączania i usuwania krawędzi w tak przedstawionym grafie, wykonuje się bardzo prosto: usunięcie krawędzi polega na wstawieniu na odpowiedniej pozycji 0, a dołączenie nowej krawędzi, na wstawieniu w odpowiedni miejsce 1. Koszt tych operacji jest, ze względu na bezpośredni dostęp do elementów tablicy, stały. Bardziej kosztowne jest np. sprawdzenie stopnia wskazanego wierzchołka: trzeba w tym celu przejrzeć wszystkie pozycje jednego wiersza macierzy i ustalić liczbę pozycji w tym wierszu różnych od zera. Koszt takiej operacji jest rzędu n. Dołączenie nowego wierzchołka i usunięcie wierzchołka z grafu są operacjami bardziej kosztownymi w tej implementacji: musimy bowiem przepisać całą macierz do macierzy o innym rozmiarze.

Na rysunku 6.7 przedstawiono pewien graf zorientowany o pięciu wierzchołkach oraz jego reprezentację tablicową. W macierzy 6.7(b) zaznaczono (kolorem czerwonym) wynik usunięcia krawędzi (1,5) oraz wstawienia krawędzi (3,5). Graf przedstawiony na tym rysunku jest zorientowany, ma dwie pętle (1,1) i (2,2), oraz cykl np. 1, 3, 4, 5, 1.

Niech V będzie n elementowym zbiorem wierzchołków grafu G, V = {v₁,...,v_n}. Niech TAB będzie tablicą o n pozycjach, odpowiadających wierzchołkom grafu. Element TAB[i] tablicy jest referencją do listy wierzchołków sąsiadujących z wierzchołkiem v_i (tzn. połączonych z nim krawędzią). Listy mogą być dodatkowo zorganizowane tak jak stosy, czy kolejki, lub mieć elementy uporządkowane ze względu na pewien porządek. Operacje dołączania krawędzi wykonuje się, w zależności od rodzaju listy, z kosztem stałym (w przypadku stosów i kolejek) lub z kosztem proporcjonalnym do długości listy. Usuwanie krawędzi jest związane z przeglądaniem listy wierzchołków incydentnych z danym wierzchołkiem, wymaga więc przejrzenia całej listy sąsiedztwa tego wierzchołka.

Podobnie jak w poprzedniej implementacji, rozszerzenie grafu o nowy wierzchołek wymaga utworzenia większej tablicy, a co za tym idzie przepisania całej informacji.

Na rysunku 6.8(a) przedstawiono reprezentację grafu G, z poprzedniego przykładu, w postaci tablicy list incydencji oraz wynik usunięcia krawędzi (1,5) i dołączenia krawędzi (3,5).

Pytanie 5: Stopniem grafu nazwiemy maksymalny ze stopni jego wierzchołków. Jaki jest koszt ustalenia stopnia grafu, jeśli dana jest jego reprezentacja macierzowa?

Drzewa są pewnym szczególnym rodzajem grafów: są to grafy niezorientowane spójne, bez pętli (nie ma krawędzi postaci (x,x)) i bez cykli. W następnych wykładach tego kursu będziemy jeszcze wielokrotnie mówili o różnych typach drzew. Tu zajmiemy się ich dynamiczną reprezentacją. Najpierw rozważymy drzewa binarne, tzn. takie, w których każdy węzeł (wierzchołek) ma co najwyżej dwa następniki. Zakładać będziemy, że każde drzewo ma wyróżniony wierzchołek, zwany korzeniem drzewa, a węzły mają przyporządkowane etykiety, będące elementami pewnego zbioru Et.

Każdy wierzchołek drzewa jest reprezentowany przez obiekt o trzech atrybutach val, left, right. Atrybut val służy do zapamiętania etykiety węzła, a left i right są wskaźnikami do lewego i prawego poddrzewa. Do wierzchołków drzewa mamy dostęp jedynie przez korzeń, który reprezentuje całe drzewo. Niech node będzie typem wierzchołków drzewa binarnego. Klasa node mogłaby być zaimplementowana następująco:

Przykład dynamicznej reprezentacji drzewa został przedstawiony na rysunku 6.9 (a). Korzeniem tego drzewa jest wierzchołek o etykiecie 4. Atrybuty left i right są zaznaczone literami l i r, odpowiednio, a strzałki wskazują obiekty, które są wartościami tych atrybutów.

Zauważmy, że referencje left i right pozwalają poruszać się po drzewie jedynie w dół, w kierunku liści. Wystarczy to jednak by móc odwiedzić wszystkie wierzchołki drzewa. "Spacery" po drzewach, to podstawowy element wielu algorytmów na drzewach. Przedstawimy tu trzy rekurencyjne metody przeglądania wierzchołków drzewa binarnego: InOrder, PreOrder i PostOrder. We wszystkich trzech algorytmach wynikiem jest ciąg etykiet wierzchołków drzewa, którego korzeniem jest obiekt root typu node.

InOrder(root : node){
	if root ¹ null then
	InOrder(root.left);	// odwiedź lewe poddrzewo
	write(root.val);	//wypisz etykietę tego wierzchołka
	InOrder(root.right)	// odwiedź prawe poddrzewo
	fi;
}

Jeżeli root jest korzeniem drzewa przedstawionego na rysunku 6.9(a), to w wyniku zastosowania procedury InOrder(root), zostanie wypisany następujący ciąg etykiet: 2, 5, 3, 9, 4, 8, 7. Rzeczywiście ciąg 2, 5, 3, 9, to etykiety lewego poddrzewa wierzchołka z etykietą 4, a ciąg 8,7, to etykiety prawego poddrzewa. Etykiety poddrzew są wypisane zgodnie z tą samą procedurą.

PreOrder(root : node){		PostOrder(root : node){
	if root ¹ null then	if root ¹ null then
	write(root.val);	PostOrder(root.left);
	PreOrder(root.left);	PostOrder(root.right);
	PreOrder(root.right)	write(root.val);
	fi;	fi;
}		}

Jeżeli root jest korzeniem drzewa przedstawionego na rysunku 6.9(a), to w wyniku zastosowania procedury PreOrder(root), zostanie wypisany ciąg etykiet: 4, 5, 2, 9, 3, 8, 7. Zastosowanie do tego samego drzewa procedury PostOrder da w wyniku ciąg 2, 3, 9, 5, 7, 8, 4.

W niektórych zastosowaniach jest wygodnie, by każdy wierzchołek miał jeszcze jeden atrybut father, będący referencją do wierzchołka sąsiedniego z poprzedniego poziomu drzewa. Atrybut ten pozwala wykonywać "spacery" po drzewie w kierunku korzenia.

Przedstawiony wyżej sposób reprezentowania drzewa binarnego, można uogólnić na drzewa o dowolnej, ale ograniczonej z góry liczbie następników. Na rysunku 6.9(b) przedstawiono przykładowy wierzchołek drzewa o k następnikach. Jest to obiekt, który składa się z atrybutu val oraz tablicy Next rozmiaru k, przechowującej referencje do następnych wierzchołków.

Oczywiście, konstruktor klasy node musi zawierać inicjalizację k elementowej tablicy Next.
Odwiedzanie wierzchołków drzewa można zrealizować zgodnie z ideą procedury PreOrder (lub PostOrder), odwiedzając najpierw korzeń takiego drzewa, a następnie rekurencyjnie kolejne poddrzewa wskazane przez referencje w tablicy Next.

Odwiedź(root : node){
	if root ¹ null then
	write(root.val);	//wypisz etykietę tego wierzchołka
	for i :=1 to k do
	Odwiedź (root. Next[i];	//odwiedź i-te poddrzewo
	od
	fi;
}

Pytanie 6: Jaka jest maksymalna liczba wierzchołków w drzewie o wysokości h, którego każdy wierzchołek ma co najwyżej 10 następników?


TAB:	1	®	1	®	2	®	3	®	5	TAB:	1	®	1	®	2	®	3
	2	®	2	®	4						2	®	2	®	4
	3	®	4								3	®	4	®	5
	4	®	2	®	5						4	®	2
	5	®	1								5	®	1

		(a)										(b)

	Rysunek 6.8 Reprezentacja grafu jako tablicy list incydencji.


	1	2	3	4	5		1	2	3	4	5
1	1	1	1	0	1	1	1	1	1	0	0
2	0	1	0	1	0	2	0	1	0	1	0
3	0	0	0	1	0	3	0	0	0	1	1
4	0	1	0	0	1	4	0	1	0	0	1
5	1	0	0	0	0	5	1	0	0	0	0

			(a)						(b)

Rysunek 6.7 Graf i jego macierzowa reprezentacja.