#10. Algorytm DFS

Dziś temat dotyczący algorytmu DFS (przechodzenie grafów w głąb). Można powiedzieć, że premierowo, pierwszy post sygnowany okrągłą dwucyfrową liczbą. Temat, z którym zetknąłem się dopiero niedawno podczas opracowywania pewnego zagadnienia związanego z rekurencją. DFS jest bardzo ciekawym zagadnieniem dotyczącym grafów i jednym z łatwiejszych w zrozumieniu. Nie oznacza to jednak, że jest prosty w implementacji.

Postaram się w niniejszym artykule odpowiedzieć na następujące pytania:

• Czym jest graf?
• Gdzie stosowany jest DFS?
• Jak wygląda implementacja rekurencyjna algorytmu?
• Jak wygląda implementacja algorytmu oparta na stosie?

Przechodzenie grafu możemy podzielić na przechodzenie w głąb oraz wszerz. Dziś skupię się tylko na pierwszym sposobie. Przechodzenie wszerz będzie omówione w przyszłości w osobnym artykule.

Wprowadzenie do DFS

Po pierwsze warto odpowiedzieć na pytanie, czym w ogóle jest graf. Graf to pewnego rodzaju struktura złożona z wierzchołków i połączeń między nimi zwanymi krawędziami. Przede wszystkim tematem grafów zajmują się specjaliści od kryptografii czy topologii. 

Depth-first search, czyli DFS lub po prostu przejście grafu w głąb to algorytm, którego zadaniem jest „wędrowanie” przez wszystkie krawędzie z jednego, początkowego wierzchołka. DFS jest podstawą do wielu skomplikowanych algorytmów dotyczących grafów i powoduje to, że tematyka grafów jest jednym z kanonów algorytmiki, przez co pojawia się na wielu rozmowach o pracę, między innymi w Google, Amazon czy Microsoft.

Przykładowy graf

Idea jest bardzo prosta i polega na tym, że wybieramy startowy wierzchołek grafu i sprawdzamy każdego z sąsiadów danego wierzchołka, następnie sąsiadów kolejnych wierzchołków i tak coraz głębiej. Innymi słowy, proces ten powtarza się aż do momentu odwiedzenia każdego z wierzchołków, gdzie do oznaczania odwiedzonych wierzchołków zazwyczaj stosuje się tablicę, która przechowuje nazwę węzła oraz flagę z wartościami prawda/fałsz, która mówi nam, czy odwiedziliśmy już dane miejsce w grafie. Przede wszystkim przechodzenie w głąb wymusza cofanie i rozpoczynanie przechodzenia od początku i postaram się to poniżej zobrazować. 

Algorytm DFS — rekurencyjnie

1. W1 -> W2
2. W2 -> W3
3. W3 -> W4
4. W4 -> W3
5. W3 -> W5
6. W5 -> W6
7. W6 -> W5
8. W5 -> W3
9. W3 -> W2
10. W2 -> W1
11. W1 -> W7
12. W7 -> W8
13. W8 -> W7
14. W7 ->W9

Sekwencja wydaje się skomplikowana, ale w rzeczywistości polega to na przejściu w dół aż do najdalej oddalonych wierzchołków W od wierzchołka startowego. Niewątpliwie widać tu sporo powrotów (zaznaczone kolorem czerwonym), gzie kolorem zielonym oznaczone są wierzchołki odwiedzone za pierwszym razem. 

Algorytm DFS — stos

Algorytm DFS z użyciem stosu będzie działać w trochę inny sposób, ponieważ zacznie od prawej strony grafu, a nie od lewej tak jak w przypadku rekurencji. 

1. W1 -> W7
2. W7 -> W9
3. W9 -> W7
4. W7 -> W8
5. W8 -> W7
6. W7 -> W1
7. W1 -> W5
8. W5 -> W6
9. W6 -> W5
10. W5 -> W1
11. W1 -> W2
12. W2 -> W3
13. W3 -> W4

Z tego powodu w powyższych przypadkach lepiej zadziałał algorytm na bazie stosu, robiąc mniej powrotów oraz o jedną mniej operację.

Implementacja DFS

Poniżej kod, którego zbudowanie zajęło mi kilka chwil i sprawiło frajdę, ponieważ wymagało to ode mnie przypomnienia zagadnień matematycznych. Składa się on z dwóch klas. Standardowej Program oraz klasy Graph zawierającej wszystkie operacje potrzebne do DFS.

Zacznę od omówienia klasy Graph. Znajduje się w niej przede wszystkim konstruktor, który w ciele zawiera utworzenie nowego obiektu Dictionary, który będzie przechowywał wartość typu int oraz HashSet (na temat kolekcji w .NET napisze osobny artykuł). Następnie publiczna metoda typu void o nazwie AddEdge. Dzięki niej będziemy dodawać krawędzie między dwoma wierzchołkami — pierwszy przekazany parametr to wierzchołek, z którego krawędź wychodzi a drugi parametr to wierzchołek, do którego dana krawędź prowadzi. Idea metody jest prosta. Jeżeli wierzchołek, z którego startujemy, jest już dodany, to dodajemy mu kolejną krawędź (czyli wierzchołek, do którego ta krawędź prowadzi). W przypadku, gdy takiego wierzchołka jeszcze nie ma, wtedy dodajemy nowy punkt startowy z wierzchołkiem końcowym. Element docelowy przechowujemy zawsze w HashSet.

Metody DFS

Metoda typu void nazwana DFS, która na wejście przyjmuje startowy wierzchołek startNode. Zaczniemy przeszukiwanie na podstawie stosu. Na początku metody tworzymy obiekt visited, gdzie będą przechowywane odwiedzone wierzchołki. Wierzchołek startowy musi zostać dodany od razu do HashSet oraz do stosu, ponieważ dzięki temu funkcja może wpaść w pętle while, gdzie dzieją się najważniejsze operacje. Po pierwsze zrzucamy ze stosu pierwszy element i wypisujemy go na ekran. Po drugie sprawdzane jest, czy obiekt visited posiada w swoim zbiorze pobrany ze stosu element. Jeżeli nie, to zostaje on dodany. Po trzecie, jeżeli nasz słownik obj zawiera wierzchołek, na którym aktualnie się zatrzymaliśmy, to przechodzimy dalej i w pętli foreach pobieramy wszystkie krawędzie dołączone do aktualnego wierzchołka, a następnie dodajemy te krawędzie (wierzchołki końcowe, do których prowadzi krawędź) do stosu oraz do obiektu z elementami odwiedzonymi. Kończy się po tym obieg pętli i zaczynamy kolejną iterację do momentu, aż nie wyzerujemy stosu.

Metody DFSRecursion

Drugim sposobem przejścia grafu w głąb jest metoda rekurencyjna o nazwie DFSRecursion, gdzie tak samo jak w poprzedniej metodzie deklarujemy obiekt visited dla wierzchołków już odwiedzonych i wywołujemy metodę rekurencyjną Traverse z dwoma parametrami — wierzchołkiem startowym oraz obiekt visited. Na wejściu metody Traverse dodajemy do obiektu visited wierzchołek, w którym aktualnie się znajdujemy i wypisujemy go na ekran. Następnie metoda zachowuje się tak samo jak ta powyżej, czyli sprawdzamy, czy w słowniku znajduje się wierzchołek, na którym jesteśmy i uruchamiamy pętlę foreach, która tym razem nie zdejmuje nic ze stosu, tylko wywołuje samą siebie z aktualnym wierzchołkiem i tym samym obiektem visited.

using System;
using System.Collections.Generic;
using System.Linq;

namespace DFSNamespace
{
    public class Program
    {
        public static void Main(string[] args)
        {
            Graph graph = new Graph();

            graph.AddEdge(1, 2);
            graph.AddEdge(1, 5);
            graph.AddEdge(1, 7);

            graph.AddEdge(2, 3);
            graph.AddEdge(2, 5);

            graph.AddEdge(3, 4);
            graph.AddEdge(3, 5);

            graph.AddEdge(5, 6);

            graph.AddEdge(7, 8);
            graph.AddEdge(7, 9);
            
            Console.WriteLine("DFS w oparciu o stos. Start z wierzchołka numer 1.");
            graph.DFS(1);

            Console.WriteLine("DFS w oparciu o rekurencję. Start z wierzchołka numer 1");
            graph.DFSRecursion(1);

            Console.ReadLine();
        }

        public class Graph
        {
            public Dictionary<int, HashSet<int>> obj { get; set; }

            public Graph()
            {
                obj = new Dictionary<int, HashSet<int>>();
            }

            public void AddEdge(int source, int target)
            {
                if (obj.ContainsKey(source))
                {
                    obj[source].Add(target);
                }
                else
                {
                    var hashset = new HashSet<int>();
                    hashset.Add(target);
                    obj.Add(source, hashset);
                }
            }

            public void DFS(int startNode)
            {
                var visited = new HashSet<int>();
                visited.Add(startNode);

                var s = new Stack<int>();
                s.Push(startNode);
                
                while (s.Count > 0)
                {
                    var current = s.Pop();
                    Console.WriteLine(current);

                    if (!visited.Contains(current))
                    {
                        visited.Add(current);
                    }

                    if (obj.ContainsKey(current))
                    {
                        foreach (int n in obj[current].Where(a => !visited.Contains(a)))
                        {
                            visited.Add(n);
                            s.Push(n);
                        }
                    }
                }
            }

            public void DFSRecursion(int startNode)
            {
                var visited = new HashSet<int>();
                Traverse(startNode, visited);
            }

            private void Traverse(int v, HashSet<int> visited)
            {
                visited.Add(v);
                Console.WriteLine(v);

                if (obj.ContainsKey(v))
                {
                    foreach (int n in obj[v].Where(a => !visited.Contains(a)))
                    {
                        Traverse(n, visited);
                    }
                }
            }
        }
    }
}

Czy wiesz, że

Jest pewien znany problem nazywany często problemem siedmiu mostów lub też zagadnieniem mostów królewskich. Jest on ściśle powiązany z teorią grafów i był pierwszym poruszanym tematów tego działu matematyki.

Przez miejscowość Królewiec przepływała rzeka, na której znajdowały się dwie wyspy. Wyspy były połączone ze sobą jednym mostem i każda z wysp była połączona z brzegami. Wyspa numer jeden była połączona czterema mostami a wyspa numer dwa dwoma. Euler, wybitny matematyk postawił pytanie. Czy można przejść kolejno przez wszystkie mosty w taki sposób, by przez każdy z mostów przejść tylko jeden raz? Następnie udowodnił, że nie ma takiej możliwości, ponieważ wyloty mostów na wyspę (dokładnie 5 i 3 połączenia) oraz na każdą ze stron rzeki (po trzy połączenia) są nieparzyste. Później uogólnił teorię i grafy, gdzie wszystkie krawędzie można przejść tylko raz, odwiedzając przy tym każdy wierzchołek, nazywamy grafami Eulera.

Poniżej rysunek poglądowy.

Podsumowanie

Właśnie dla tego typu tematów między innymi powstał ten blog, ponieważ bardzo się cieszę, że mogłem zmierzyć się z grafami i jednym z algorytmów, które są pomocne w obliczeniach opartych na tego typu strukturach. Oczywiście to tylko fragment tematu i zapewne już niedługo powrócę do niego. Został mi na pewno do omówienia temat przechodzenia grafów wszerz. Miałem nawet w planach dodać go w tym poście razem z DFS jednak stwierdziłem po dokładniejszej analizie, że lepiej zagadnienia rozdzielić.

Pierwsze tematy na blogu staram się maksymalnie upraszczać i nie stosować zbyt skomplikowanej matematyki. Nie ukrywam jednak, że już niedługo opracuję co najmniej dwa zagadnienia związane z bardzo zaawansowanymi matematycznymi operacjami.

Drobne ogłoszenia

Po pierwsze. W związku z dużym zainteresowaniem tematem programowania w języku Python postanowiłem przygotować projekt darmowego szkolenia z Python 3, które wystartuje z początkiem 2020 roku. Z pewnością będzie to szkolenie w formie wpisów na blogu dla początkujących. Z tego też powodu wpisy na blogu będą się przeplatać. Nieparzyste będą dotyczyć Pythona, parzyste tematów pozostałych — i tak aż do omówienia w sposób satysfakcjonujący zagadnień dotyczących tego języka programowania. 

Po drugie. Przygotowuję się też do pierwszego blogowego podsumowania. Pojawi się ono w ostatni dzień listopada i omówię w nim statystyki bloga za listopad 2019, proces budowy, zbierania materiałów i ilość wydatków, które poczyniłem, by w ogóle to miejsce swoje w sieci stworzyć.

Kolejny, 11 wpis będzie na temat klas abstrakcyjnych i interfejsów.

Źródła

https://ksiegarnia.pwn.pl/Wprowadzenie-do-algorytmow,68706413,p.html 
https://eduinf.waw.pl/inf/alg/001_search/0125.php 
http://informatyka.wroc.pl/node/709 
http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html 
http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Przeszukiwanie_graf%C3%B3w 
http://home.agh.edu.pl/~zobmat/2017/2_tarkowskijakub/teoria/algorytmy.php 
http://users.uj.edu.pl/~ufkapano/algorytmy/lekcja14/search.html 
http://www-users.mat.uni.torun.pl/~piersaj/www/contents/teaching/rki2010/dfs.pdf 
http://www.imio.polsl.pl/Dopobrania/Lab%20MH%2001%20(Grafy%20cz1).pdf 

Newsletter

Nie przegap i dołącz już dziś do 838 osób będących w tym Newsletter! Otrzymuj co niedzielę o godzinie 20 listę kilku ciekawych tematów, które miałem okazję obserwować w mijającym tygodniu.

Tematy będą głównie techniczne, ale czasami pojawi się coś, co może wprowadzi Cię w stan zadumy i zmusi do dyskusji w szerszym gronie. Zero spamu!