Drogi Krawędziowo Rozłączne

Wstęp

Problem dróg krawędziowo rozłącznych pozwala odpowiedzieć na pytanie ile jest możliwych dróg dojazdu z punktu A do B nigdy nie używając drugi raz tej samej krawędzi grafu w każdej kolejnej trasie. W tym artykule zostanie wyjaśnione jak napisać algorytm rozwiązujacy podany problem.

Problem

Zakładamy, że graf jest skierowany i ma n wierzchołków. Pomiędzy wierzchołkami może przebiegać więcej niż jedna krawędź. Poszukiwane drogi nie mogą korzystać dwa razy z tej samej krawędzi. Innymi słowy krawędź między wierzchołkami v i w może zostać wykorzystana maksymalnie tyle teraz ile z v jest krawędzi do w.

Oto przykładowy graf oraz rozwiązanie tego problemu dla przejścia z wierzchołka 0 do wierzchołka 2:

Graf

Drogi z 0 do 2

Pomiędzy wierzchołkiem 0 i 2 istnieją dokładnie dwie ścieżki. Ze względu na to, że graf jest skierowany to z wierzchołka 2 do 0 istnieje tylko jedna droga.

Algorytm

W celu rozwiązania podanego problemu należy skorzystać z algorytmu BFS, który pomoże znaleźć najkrótszą ścieżkę pomiędzy dwoma wierzchołkami. Następnie algorytm musi zaktualizować macierz usuwając wykorzystane do tej pory krawędzie. Następnie program ponownie powinien wywoływać BFS, aż nie zostanie znaleziona ścieżka. Wynikiem powinna być łączna ilość pozytywnych wywołań funkcji BFS.

Implementacja

Część prywatna

Program przechowuje graf jako macierz. Na pozycjach (i, j) znajduje się informacja ile jest krawędzi z wierzchołka i do wierzchołka j. Oto przykładowy graf i podana jego reprezentacja jako macierz:

Graf

1. 0 1 0 2
2. 0 0 1 0
3. 1 0 0 0
4. 0 0 1 0

BFS

Przedstawiona funkcja BFS() jest rozszerzoną wersją algorytmu BFS. Przyjmuje ona kolejno: macierz - macierz danych według założeń powyżej, rodzice - tablica do przechowania na i-tej pozycji numer wierzchołka z którego nastąpiło przejście na i-ty, start i koniec - odpowiednio wierzchołke początkowy i końcowy.

1. bool BFS(int ** macierz, int * rodzice, int n, int start, int koniec) {
2.   bool * odwiedzone = new bool[n] {false};
3.   queue<int> queue;
4.   queue.push(start);
5.   odwiedzone[start] = true;
7.   while (queue.size() > 0) {
8.     int u = queue.front();
9.     queue.pop();
10.     for (int i = 0; i < n; i++) {
11.       if (!odwiedzone[i] && macierz[u][i] > 0) {
12.         queue.push(i);
13.         odwiedzone[i] = true;
14.         rodzice[i] = u;
15.       }
16.     }
17.   }
18.   return odwiedzone[koniec];
19. }

W wyniku działania tego algorytmu zwraca jest wartość czy wierzchołek końcowy został osiągnięty. Dodatkowo aktualizowana jest tablica rodziców wierzchołków, która zostanie następnie użyta do aktualizacji macierzy tj. usunięcie zużytych już krawędzi grafu.

Funkcja Główna

Funkcja DrogiRozłaczne() dla podanej macierzy oraz wierzchołka początkowego i końcowego zwraca ilość dróg krawędziowo rozłącznych.

1. int RozlaczneDrogi(int ** macierz, int n, int start, int koniec) {
2.   int * rodzice = new int[n];
3.   int drog = 0;
4.   while (BFS(macierz, rodzice, n, start, koniec)) {
5.     drog++;
7.     int koniec_tmp = koniec;
8.     do {
9.       macierz[rodzice[koniec_tmp]][koniec_tmp] -= 1;
10.       koniec_tmp = rodzice[koniec_tmp];
11.     } while (koniec_tmp != start);
12.   }
13.   return drog;
14. }

Funkcja na początku deklaruje tablicę w której będą przechowywane informacje o drodze w funkcji BFS() oraz nowy licznik. Algorytm powtarza wywołanie algorytmu BFS dopóki zostanie znaleziona droga. Na podstawie znalezionej drogi aktualizowana jest macierz oraz licznik. Po przerwaniu pętli zwracany jest licznik drog.

Testowanie funkcji

Funkcje można przetestować przy pomocy poniższego kodu, który wczyta potrzebne dane, a następnie wypisze wynik.

1. int main () {
2.   int n, s, k;
3.   cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
4.   cin >> n;
5.   cout << "Podaj wezel poczatkowy\n s = ";
6.   cin >> s;
7.   cout << "Podaj wezel koncowy\n k = ";
8.   cin >> k;
9.   int** macierz = new int*[n];
10.   for (int i = 0; i < n; i++) {
11.     macierz[i] = new int[n];
12.     for (int j = 0; j < n; j++) {
13.       cin >> macierz[i][j];
14.     }
15.   }
16.   int drog = RozlaczneDrogi(macierz, n, s, k);
17.   cout << "Rozlacznych drog: " << drog << endl;
18.   system("pause");
19.   return 0;
20. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz algorytm PodajRozlaczneDrogi(), który zwróci listę wszystkich dróg krawędziowo rozłącznych z wierzchołka v do w. Opis drogi powienien składać się z numerów kolejno odwiedzanych wierzchołków. Przykładowo dla podanego grafu:

Graf

Program powinien przykładowo wypisać na ekran (kolejność opisów dróg jest dowolna):

1. 0 3 2
2. 0 1 2

• Kod źródłowy Zadanie 1