Strona główna » Algorytmy » Artykuły » Mosty w Grafie
 

Mosty w Grafie

Wstęp

Most to w grafie taka krawędź, której usunięcie powoduje, że graf staje się niespójny. Do tego zagadnienie istnieje prosty algorytm, który potrafi znaleźć wszystkie wrażliwe części grafu. W tym artykule zostanie opisana realizacja takiego algorytmu.

Most

Most to w teorii w grafów krawędź, której usunięcie z grafu spowoduje, że graf stanie się niespójny. Oznacza to, że jeśli most zniknie to będzie istnieć co najmniej jedna taka para wierzchołków, że nie będzie między nimi żadnej drogi. W drzewach każda krawędź jest mostem.

Przykład

Oto przykładowy graf z dwoma mostami pomiędzy C i D oraz F i G.

Graf z mostami

Pozostałe krawędzi nie są mostami, ponieważ zawsze istnieje alternatywna droga, która by mogła zostać użyta. Przykładowo usuwając bezpośrednie połączenie między A i B zawsze można przejsć od A do C, a potem do B. Jednak usunięcie C i D uniemożliwia przedostanie się z wierzchołków A, B, C do jakiegokolwiek innego.

Algorytm

W celu efektywnego znalezienia wszystkich mostów można skorzystać z algorytmu DFS. Dla każdego wierzchołka musimy wiedzieć następuje rzeczy: czy został odwiedzony, czas odwiedzenia, najniższy numer wierzchołka jaki można odwiedzić z niego oraz, który węzeł jest jego rodzicem. Przechodzimy po kolejnych węzłach. Podczas odwiedzenia węzła kolejno: odznaczamy go jako odwiedzonego i przypisujemy jego czasowi oraz najniższemu numeru wierzchołka aktualny numer trasy zwiększony o 1. Następnie dla każdego jego sąsiada, który nie został odwiedzony: ustawiamy sąsiadowi rodzica na aktualny węzeł i rozpoczynamy w tym wierzchołki wyszukiwanie mostów. Po zakończeniu aktualizujemy aktualny najniższy, osiągalny węzeł na mniejszy czas odwiedzenia z tego wierzchołka i sąsiada. Następnie jeśli okaże się, że najniższy osiągalny wierzchołek sąsiada jest wyższy niż czas aktualnego wierzchołka to znaczy, że jest to most. Jeśli sąsiad był wcześniej odwiedzony to tylko wystarczy zaktualizować najniższą wartość o ile sąsiad nie jest rodzicem.

Prześledźmy działanie algorytmu dla podanego poniżej grafu:

Prosty graf z mostem

Początkowo tabelka przedstawia się następująco:

WęzełOdwiedzonyRodzicCzas odwiedzeniaNajniższy osiągalny
A---
B---
C---
D---

Wybieramy dowolny wierzchołek jako początkowy i w nim rozpoczynamy poszukiwanie mostów. Początkowo numer trasy wynosi 0, ale zwiększa się z każdym odwiedzonym wierzchołkiem. Z wierzchołka A przenosimy się do najbliższego sąsiada B uprzednio aktualizując tabelkę.

WęzełOdwiedzonyRodzicCzas odwiedzeniaNajniższy osiągalny
And.00
B---
C---
D---

Przypisujemy czas odwiedzenia i najniższy osiągalny w wierzchołku B na numer trasy 1 oraz odznaczamy, że został odwiedzony. Przechodzimy z niego przechodzimy do wierzchołka C.

WęzełOdwiedzonyRodzicCzas odwiedzeniaNajniższy osiągalny
And.00
BA11
C---
D---

Podobnie będzie również w przypadku wierzchołka C. Przechodzimy do D.

WęzełOdwiedzonyRodzicCzas odwiedzeniaNajniższy osiągalny
And.00
BA11
CB22
D---

Wierzchołek D ma tylko jednego sąsiada i jest nim odwiedzony rodzic C. Z tego powodu nie zostanie zmodyfikowany, ani czas ani najniższy osiągalny wierzchołek. To również jest koniec trasy DFS, więc wracamy do poprzedniego wierzchołka C.

WęzełOdwiedzonyRodzicCzas odwiedzeniaNajniższy osiągalny
And.00
BA11
CB22
DC33

Wierzchołek C po wyszukiwaniu mostów poprzez wierzchołek D stwierdza, że najniższy osiągalny wierzchołek D to 3, a czas aktualnego wierzchołka to 0, więc został znaleziony most pomiędzy C i D!

WęzełOdwiedzonyRodzicCzas odwiedzeniaNajniższy osiągalny
And.00
BA11
CB22
DC33

Następnie algorytm wraca do poprzednich wywołań. Jak się okazuje tabelka nie zmienia się już do końca działania funkcji.

Implementacja

Struktura

Dane dotyczącego pojedynczego wierzchołka będą przechowywane w obiekcie o następujących właściwościach.

  1. struct Wezel {
  2.   bool odwiedzony;
  3.   int czas;
  4.   int najnizszy;
  5.   int rodzic;
  6. };

Inicjalizacja

Przed przystąpieniem do wyszukiwania mostów należy przeprowadzić wstępne czynności, które polegają na przygotowaniu listy do zapisywania wartości węzłów i jej ustawienia na domyślne wartości, utworzenie licznika numeru trasy oraz zmiennej do której zostanie zapisany wynik.

  1. vector<pair<int, int>> SzukajMostu(int ** macierz, int n)
  2. {
  3.   Wezel * wezly = new Wezel[n];
  4.   for (int i = 0; i < n; i++)
  5.   {
  6.     wezly[i].odwiedzony = false;
  7.     wezly[i].rodzic = -1;
  8.   }
  9.   int nr_trasy = 0;
  10.   vector<pair<int, int>> wynik;
  11.   for (int i = 0; i < n; i++) {
  12.     if (!wezly[i].odwiedzony) {
  13.       SzukajMostu(macierz, n, i, nr_trasy, wezly, wynik);
  14.     }
  15.   }
  16.   return wynik;
  17. }

Na koniec rozpoczynamy przeszukiwanie DFS przekazanego grafu. Bardzo ważne, aby pamiętać, że pomiędzy kolejnymi wywołaniami algorytmu musimy znać wyniki poprzednich poszukiwań mostów w innej części grafu!

Wyszukiwanie mostów

Funkcja SzukajMostuWezel() rekurencyjnie wyszukuje wszystkie mosty w grafie dla podanej macierzy poprzez odwiedzenie wierzchołka v. Dodatkowo należy podać aktualny numer trasy nr_trasy, aktualne parametry węzłów wezly oraz miejsce, gdzie zapisywać znalezione mosty, tutaj wynik.

  1. void SzukajMostu(int ** macierz, int n, int v, int & nr_trasy,
  2.   Wezel * wezly, vector<pair<int, int>> & wynik) {
  3.   wezly[v].odwiedzony = true;
  4.   wezly[v].czas = wezly[v].najnizszy = ++nr_trasy;
  5.   for (int w = 0; w < n; w++)
  6.   {
  7.     if (macierz[v][w] == 0)
  8.       continue;
  9.    
  10.     if (!wezly[w].odwiedzony)
  11.     {
  12.       wezly[w].rodzic = v;
  13.       SzukajMostu(macierz, n, w, nr_trasy, wezly, wynik);
  14.       wezly[v].najnizszy = min(wezly[v].najnizszy, wezly[w].najnizszy);
  15.       if (wezly[w].najnizszy > wezly[v].czas) {
  16.         wynik.push_back(make_pair(v, w));
  17.       }
  18.     }
  19.     else if (w != wezly[v].rodzic)
  20.     {
  21.       wezly[v].najnizszy = min(wezly[v].najnizszy, wezly[w].czas);
  22.     }
  23.   }
  24. }

Odwiedzając wierzchołek aktualizujemy jego właściwości i rozpoczynamy odwiedzanie sąsiadów. Wśród sąsiadów wyróżniamy dwa przypadki. Dla nieodwiedzonego sąsiada przechodzimy do niego i wywołujemy wyszukiwanie mostów, a następnie na podstawie zdobytych infomacji aktualizujemy najniższy osiągalny wierzchołek, a następnie sprawdzamy czy krawędź prowadząca do sąsiada nie jest mostem. Dla odwiedzonego sąsiada sprawdzamy tylko czy nie trzeba zaktualizować najniższego osiągalnego wierzchołka.

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższego fragmentu programu, który wczyta od użytkownika macierz, a następnie wypisze wszystkie pary numerów wierzchołków, który identyfikują krawędź, która jest mostem. Przykładowo poniższy graf:

Graf z mostami

należy podać jako następując macierz:

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

Program po obliczeniach zwróci (wierzchołki są indeksowane od 0):

  1. 5 6
  2. 2 3

Uwaga: gdyby obrano jako początkowy wierzchołek inny niż o indeksie 0 to kolejność krawędzi może się różnić!

  1. int main() {
  2.   int n;
  3.   cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
  4.   cin >> n;
  5.   int** macierz = new int*[n];
  6.   for (int i = 0; i < n; i++) {
  7.     macierz[i] = new int[n];
  8.     for (int j = 0; j < n; j++) {
  9.       cin >> macierz[i][j];
  10.     }
  11.   }
  12.   vector<pair<int, int>> wynik = SzukajMostu(macierz, n);
  13.   if (wynik.size() == 0) {
  14.     cout << "Graf nie ma mostow!";
  15.   } else {
  16.     cout << "Kolejne mosty to:" << endl;
  17.     for each(pair<int, int> krawedz in wynik) {
  18.       cout << krawedz.first << "\t" << krawedz.second << endl;
  19.     }
  20.   }
  21.   system("pause");
  22.   return 0;
  23. }