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.   public bool odwiedzony;
3.   public int poprzednik;
4.   public 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. static dane[] DFS(int[,] macierz, int start) {
2.   dane[] tab = new dane[macierz.GetLength(0)];
3.   for (int i = 0; i < macierz.GetLength(0); i++) {
4.     tab[i].odwiedzony = false;
5.     tab[i].poprzednik = -1;
6.   }
7.   odwiedzWezel(macierz, ref tab, start, 0);
8.   for (int i = 0; i < macierz.GetLength(0); i++)
9.     if (!tab[i].odwiedzony)
10.       odwiedzWezel(macierz, ref 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. static void odwiedzWezel(int[,] macierz, ref dane[] tab, int u, int odl) {
2.   tab[u].odwiedzony = true;
3.   tab[u].odl = odl;
4.   for (int i = 0; i < macierz.GetLength(0); i++) {
5.     if (macierz[u, i] > 0 && !tab[i].odwiedzony) {
6.       tab[i].poprzednik = u;
7.       odwiedzWezel(macierz, ref 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. static int najdluzszaSciezka(int[,] macierz) {
2.   int maks = 0;
3.   for (int i = 0; i < macierz.GetLength(0); i++) {
4.     dane[] podsumowanie = DFS(macierz, i);
5.     for (int j = 0; j < macierz.GetLength(0); j++) {
6.       if (podsumowanie[j].odl > maks) {
7.         maks = podsumowanie[j].odl;
8.       }
9.     }
10.   }
11.   return maks;
12. }

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. static void Main(string[] args) {
2.   Console.Write("Podaj ile jest wierzchołków w grafie\n n = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   int[,] macierz = new int[n, n];
5.   for (int i = 0; i < n; i++) {
6.     string[] str = Console.ReadLine().Split(' ');
7.     for (int j = 0; j < n; j++) {
8.       macierz[i, j] = Convert.ToInt32(str[j]);
9.     }
10.   }
11.   int maks = najdluzszaSciezka(macierz);
12.   Console.WriteLine("Najdłuższa ściezka ma długość {0}", maks);
13.   Console.ReadKey();
14. }

• 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