Algorytm DFS

Witam

Mam do napisania algorytm DFS
Szukający najkrótszej drogi. Dane wejściowe maja strukture następujaca:

5 5 1 4 odpowiednio liczba wierzchołków, liczba połączeń, start i koniec
1 3 // dalej dane wyznaczające krawędź pomiędzy wierzchołkami
1 2
2 3
2 5
2 4

Często się spotyka informacje o macierzy sąsiedztwa. Czy w tym przypadku trzeba stworzyć taką macierz?
Może ktoś polecić prosty przykład DFS?
Od czego trzeba zacząć

Ale do szukania najkrótszej drogi to się nadaje BFS a nie DFS. Od ciebie zależy co chcesz używać, czy list sąsiedztwa czy macierzy sąsiedztwa. Macierze zajmują zwykle dużo więcej pamięci, tzn dla grafów rzadkich. Czyli dla grafów rzadkich lepiej zastosować listy, a dla grafów gęstych macierze.

Temat nie jest bezpośrednio związany z Javą. Powinien polecieć do innego działu.

Implementacji w Googlach jest pełno.