Drzewa i Grafy

Drzewo

Drzewo to taki graf, którego wszystkie wierzchołki są połączone, a pomiędzy dwoma dowolnymi wierzchołkami istnieje dokładnie jedna ścieżka. W takim grafie nie występują cykle. Innymi słowy graf musi być spójny i acykliczny.

Przykład

Poniższy graf nie może być drzewem, ponieważ zawiera on przykładowo cykl ACFD, a ponadto nie jest spójny. Istnieją dwie oddzielne części grafu: ABCDEF oraz GH.

Z kolei poniższy graf jest drzewem:

Nie można tutaj znaleźć cykli, a wszystkie wierzchołki są połączone w spójną całość. Oznacza to też, że pomiędzy dwoma wierzchołkami istnieje dokładnie jedna i tylko jedna droga.

Analiza problemu

Jednym ze sposobów na sprawdzenie czy graf jest drzewem polega na wykorzystaniu algorytmu BFS. W tym przypadku należałoby zbierać o każdym kolejnym wierzchołki dwie informacje: poprzednika oraz czy dany wierzchołek został już odwiedzony. Algorytm można rozpocząć w dowolnym wierzchołku - nie wpłynie to w jakikolwiek sposób na wynik. Podczas odwiedzania wierzchołka należy uważnie odwiedzać jego sąsiadów. Otóż jeśli sąsiad do odwiedzenia jest już odwiedzony, ale nie jest to poprzednik to znaczy, że w grafie występuje cykl! Nie będzie to wtedy drzewo. Ponadto na koniec algorytmu należy sprawdzić czy wszystkie wierzchołki zostały odwiedzone, aby potwierdzić też warunek spójności.

Implementacja

Poniższa funkcja czyDrzewo() na podstawie przekazanej macierzy zwraca informację czy podany graf jest drzewem.

1. def czyDrzewo(macierz):
2.   tab = []
3.   for i in range(0, len(macierz)):
4.     tab.append(dane(False, -1))
5.   q = queue.Queue()
6.   q.put(0)
7.   while (not q.empty()):
8.     u = q.get()
9.     tab[u].odwiedzony = True
10.     for i in range(0, len(macierz)):
11.       if (macierz[u][i] > 0):
12.         if(tab[i].odwiedzony and (not i == tab[u].poprzednik)):
13.           return False
14.         elif(not tab[i].odwiedzony):
15.           tab[i].poprzednik = u
16.           q.put(i)
18.   for i in range(0, len(macierz)):
19.     if (not tab[i].odwiedzony):
20.       return False
21.   return True

Funkcja wykorzystuje algorytm BFS. Początkowo wszystkie wierzchołki nie mają ustalonego poprzednika oraz nie są odwiedzone. Jako punkt początkowy jest wybierany pierwszy wierzchołek. Następnie odwiedzani są wszyscy kolejni sąsiedzi z którymi wierzchołek ma połączenie. Podczas przechodzenia sprawdzane jest czy nie występują cykle. Na koniec sprawdzana jest spójność. Jeśli algorytm nie zostanie przerwany to na koniec można zwrócić prawdę.

Testowanie funkcji

Do przetestowania funkcji można skorzystać z poniższego fragmentu kodu:

1. n = int(input('Podaj ile wierzchołków ma graf\n n = '))
2. print('Podaj elementy macierzy:')
3. macierz = []
4. for i in range(0, n):
5.   tab = [int(x) for x in input().split()]
6.   macierz.append(tab)
7.  
8. wynik = czyDrzewo(macierz)
9. print("Graf " + ("" if wynik else "nie ") + "jest drzewem")

Graf należy podać w formie macierzy takiej jak poniżej:

1. 0 1 1 1 0 0 0 0
2. 1 0 0 0 0 0 0 0
3. 1 0 0 0 0 0 0 0
4. 1 0 0 0 0 1 0 1
5. 0 0 0 0 0 1 0 0
6. 0 0 0 1 1 0 0 0
7. 0 0 0 0 0 0 0 1
8. 0 0 0 1 0 0 1 0

Graf ten reprezentuje przykład poprawnego grafu - drzewa na początku artykułu.

• Kod źródłowy Implementacja