Najdłuższa Ścieżka w Grafie

Wstęp

Do wyszukiwania najdłuższej ścieżki w grafie pomiędzy dwoma dowolnymi wierzchołkami najwygodniej zastosować odpowiednio dostosowany algorytm DFS, który będzie przechodził po węzłach i nadawał odległości. Algorytm ten zostanie wykonany dla każdego kolejnego wierzchołka w grafie. Za każdym razem algorytm DFS tworzy nową tablicę informacji z której następnie należy odczytać maksymalną odległość i porównać ją z aktualną i odpowiednio zaktualizować.

Przykład

Przypuśćmy, że dany jest następujący graf:

Przykładowy graf

Pierwszy etap polega na wykonaniu algorytmu DFS dla każdego wierzchołka w grafie. Poniższe wyniki prezentują kolejno otrzymywane wyniki:

Podczas działania algorytmu nie trzeba tworzyć takiej tabeli wyników. Wystarczy dla każdego kolejnego wierzchołka znaleźć maksimum i zachować jeśli jest większy od dotychczas znalezionego. W powyższym przykładzie widać, że najdłuższy odcinek jest pomiędzy wierzchołkiem G i E.

Implementacja

Przechowywanie danych

Algorytm DFS zwykle przechowuje tylko informację o wierzchołku dotyczące poprzednika oraz czy dany wierzchołek został odwiedzony. Tutaj potrzebne jest dodatkowe pole do zapamiętania odległości.

1. struct dane {
2.   bool odwiedzony;
3.   int poprzednik;
4.   int odl;
5. };

DFS

Główna część algorytmu DFS tworzy tablicę danych, która zostanie uzupełniona przez algorytm. Działa on w pętli odwiedzając najpierw wybrany wierzchołek, a potem wszystkie pozostałe. Na koniec zwracana jest uzupełniona tablica informacji.

1. dane* DFS(int** macierz, int n, int start) {
2.   dane* tab = new dane[n];
3.   for (int i = 0; i < n; i++) {
4.     tab[i].odwiedzony = false;
5.     tab[i].poprzednik = -1;
6.   }
7.   odwiedzWezel(macierz, n, tab, start, 0);
8.   for (int i = 0; i < n; i++)
9.     if (!tab[i].odwiedzony)
10.       odwiedzWezel(macierz, n, tab, i, 0);
11.   return tab;
12. }

Do odwiedzania wierzchołków w sposób rekurencyjny została dopisana metoda odwiedzWezel(), która w momencie odwiedzenia wierzchołka przypisuje mu przekazaną odległość oraz aktualizuje, że został odwiedzony. Następnie odwiedza wszystkich jego nieodwiedzonych sąsiadów. Tu należy pamiętać, że podczas odwiedzania sąsiada odległość należy zwiększyć o 1.

1. void odwiedzWezel(int** macierz, int n, dane* tab, int u, int odl) {
2.   tab[u].odwiedzony = true;
3.   tab[u].odl = odl;
4.   for (int i = 0; i < n; i++) {
5.     if (macierz[u][i] > 0 && !tab[i].odwiedzony) {
6.       tab[i].poprzednik = u;
7.       odwiedzWezel(macierz, n, tab, i, odl + 1);
8.     }
9.   }
10. }

Najdłuższa ścieżka

Algorytm DFS jest gotowy do użycia, więc można teraz przejść do napisania głównej funkcji najdluzszaSciezka(), która dla danej macierzy zwróci maksymalną odległość pomiędzy wierzchołkami.

1. int najdluzszaSciezka(int** macierz, int n) {
2.   int maks = 0;
3.   for (int i = 0; i < n; i++) {
4.     dane* podsumowanie = DFS(macierz, n, i);
5.     for (int j = 0; j < n; j++) {
6.       if (podsumowanie[j].odl > maks) {
7.         maks = podsumowanie[j].odl;
8.       }
9.     }
10.     delete podsumowanie;
11.   }
12.   return maks;
13. }

Algorytm w pętli wywołuje algorytm DFS na każdym kolejnym wierzchołku. Zwrócona tablica jest następnie analizowana w celu znalezienia większego elementu niż aktualnie znalezione maksimum. Na koniec zwracana jest znaleziona wartość.

Testowanie funkcji

Do przetestowania napisanego kodu można skorzystać z poniższego fragmentu, który wczytuje ile wierzchołków ma graf, a następnie odpowiednią macierz. Grafowi pokazywanemu wcześniej w artykule odpowiada następująca macierz:

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

1. int main() {
2.   int n;
3.   cout << "Ile wierzcholkow ma graf?\n n = ";
4.   cin >> n;
5.   cout << "Podaj macierz:" << endl;
6.   int** macierz = new int*[n];
7.   for (int i = 0; i < n; i++) {
8.     macierz[i] = new int[n];
9.     for (int j = 0; j < n; j++)
10.       cin >> macierz[i][j];
11.   }
12.   int maks = najdluzszaSciezka(macierz, n);
13.   cout << "Najdlusza sciezka ma dlugosc " << maks;
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program, który dla danej macierzy znajdzie wszystkie pary wierzchołków pomiędzy, którymi odległość w grafie jest maksymalna. Przetestuj napisany program. Przykładowo dla poniższego grafu:

Przykładowy graf

algorytm powinien wypisać:

1. Najdłuższa ściezka ma długość 5
2. Taką długość mają ścieżki:
3. z 4 do 6
4. z 6 do 4

• Kod źródłowy Zadanie 1