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:

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ę.

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.

Podobnie będzie również w przypadku wierzchołka C. Przechodzimy do 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.

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!

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. class Wezel:
2.   def __init__(self):
3.     self.odwiedzony = False
4.     self.czas = -1
5.     self.najnizszy = -1
6.     self.rodzic = -1

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. def SzukajMostu(macierz):
2.   n = len(macierz);
3.   wezly = [Wezel() for x in range(n)]
5.   nr_trasy = 0
6.   wynik = []
8.   for i in range(n):
9.     if not wezly[i].odwiedzony:
10.       nr_trasy, wezly, wynik = SzukajMostuWezel(macierz, i, nr_trasy, wezly, wynik)
11.   return wynik

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. def SzukajMostuWezel(macierz, v, nr_trasy, wezly, wynik):
2.   wezly[v].odwiedzony = True
3.   nr_trasy += 1
4.   wezly[v].czas = wezly[v].najnizszy = nr_trasy
5.   for w in range(len(macierz)):
6.     if macierz[v][w] == 0:
7.       continue;
9.     if not wezly[w].odwiedzony:
10.       wezly[w].rodzic = v
11.       nr_trasy, wezly, wynik = SzukajMostuWezel(macierz, w, nr_trasy, wezly, wynik)
12.       wezly[v].najnizszy = min(wezly[v].najnizszy, wezly[w].najnizszy)
13.       if (wezly[w].najnizszy > wezly[v].czas):
14.         wynik.append((v, w))
15.     elif w != wezly[v].rodzic:
16.       wezly[v].najnizszy = min(wezly[v].najnizszy, wezly[w].czas)
17.   return nr_trasy, wezly, wynik

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. n = int(input("Podaj ile węzłów ma graf\n n = "))
2. print("Podaj elementy macierzy:")
3. macierz = []
4. for i in range(0, n):
5.   tab = [int(x) for x in input().split()]
6.   macierz.append(tab)
7.  
8. wynik = SzukajMostu(macierz)
9. for krawedz in wynik:
10.   print(krawedz[0], krawedz[1])

• Kod źródłowy Implementacja