Przeszukiwanie grafów

Zadanie AL14.1 Przedstawić listę sąsiedztw dla podanego niżej grafu nieskierowanego. Wypisać w jakiej kolejności będą odwiedzone wierchołki w czasie przeszukiwania grafu w głąb rozpoczynającego się od wierzchołka 0. Wypisać krwaędzie utworzonego drzewa przeszukiwania w głab. Powtórzyć to samo dla pzeszukiwania wszerz.

       0-----1-----2
       |\   / \   /   
       | \ /   \ /
       |  3     5
       | /      
       |/       
       4----6

Zadanie AL14.2 Powtórzyć to samo co w zadaniu AL14.1 traktując tym razem graf jako skierowany. Przyjmujemy, że kierunek krawędzi poziomych jest zawsze od lewej do prawej, a pionowych i ukośnych - z góry na dół.

Zadanie AL14.3 (2+2 pkt.) Zaimplementuj omawiane na wykładzie algorytmy przeszukiwania grafów

• DFS czyli przeszukiwanie w głąb (2 pkt);

• BFS czyli przeszukiwanie wszerz (2 pkt);

Wejście: Macierz sąsiedztwa grafu rozmiaru N×N zapisana w pliku. Pierwszy wiersz pliku zawiera liczbę N wierzchołków grafu. Każdy kolejny (i+1)-szy wiersz w pliku zawiera ciąg N liczb tworzących i-ty wiersz macierzy sąsiedztw.

Wyjście:

• Wierzchołki uporządkowane według pierwszego odwiedzenia przez dany algorytm przeszukiwania grafu, oraz
• krawędzie otrzymanego lasu spinającego.

Uwaga. Do przesyłanego programu należy dołączyć rysunki testowanych grafów.

Zadanie AL14.4 (5 pkt) Jak w zadaniu AL14.3, przy czym po wczytaniu z pliku, graf przechowywany jest w postaci listy sąsiedztw