Scenariusz na lab 6 i 7:

Proszę wpierw dokończyć zadanie o rolniku. W razie kłopotów, chętnie pomogę.

Nowe zadanie jest następujące. Napisać prostą klasę opisującą graf nieskierowany z wierzchołkami numerowanymi 0,1,...,n-1. Klasa powinna mieć opcję dodawania nowego wierzchołka o kolejnym indeksie, dodawania nowej krawędzi pomiędzy dwoma wierzchołkami, oraz (najważniejsze) sprawdzania odległości między wierzchołkami. To znaczy, powinna być napisana metoda distance(int i, int j), która zwróci długość najkrótszej ścieżki między i-tym i j-tym wierzchołkiem (lub -1 jeśli taka ścieżka nie istnieje). Implementacja powinna się opierać o BFSa.

Proszę nie przekomplikowywać architektury zadania: w przypadku grafów można sobie wyobrazić naprawdę rozbudowane i ogólne architektury, ale tutaj chcielibyśmy postawić na prostotę. W szczególności o ile klasa opisująca wierzchołek wydaje się potrzebna, to wystarczy, żeby każdy wierzchołek pamiętał po prostu listę/tablicę sąsiadów (nie trzeba oddzielnej klasy opisującej krawędzie). Wartości pomocnicze do BFSa (odległość/czy wierzchołek został odwiedzony) mogą być trzymane w lokalnej tablicy w metodzie liczącej BFS, ale mogą też po prostu być atrybutami wierzchołka (wtedy warto dodać metodę grafu resetującą te wartości w każdym wierzchołku).

Rozwiązanie proszę opatrzeć funkcją main, która testuje implementację na kilku prostych przykładach. Zadanie dla ambitnych: zaimplementować metodę shortestPath(int i, int j), która zwróci samą ścieżkę (jako tablicę lub listę).

Do rozwiązania przyda się zapewne:
  - klasa ArrayList<T> --- rozszerzalna lista (znamy z poprzedniego labu);
  - interfejs Queue<T> i jego implementacja ArrayDeque<T> --- kolejka zaimplementowana na tablicy.

To zadanie to trzecia z pięciu drobnych prac domowych z labu. Proszę o nadesłanie rozwiązania do niedzieli 12 kwietnia (włącznie).