Część 2 Część 3 Część 4 Do napisania tego artykułu skłoniło mnie szkodliwe zadanie z zadania Java Multithreading, które nie bez dokuczania ze strony programistów zostało nazwane przez nich „zadaniem StringBuilder”. Istota jej warunku polegała na tym, że zbiór słów (w warunku, w którym podawane są nazwy miast, co przypomina dziecięcą grę słowną) miał być ułożony na zasadzie domina, ostatnia litera słowa „n” powinna być równe pierwszej literze słowa (n+1) go i wiadomo było, że wszystkie podane (pojedynczo) słowa zostały zsumowane w taki łańcuch. Jeśli możliwe było skomponowanie kilku opcji dla żądanego ciągu słów, jako rozwiązanie akceptowano dowolną. Pomimo pozornej prostoty i przejrzystości warunku rozwiązanie problemu nie było łatwe, a mistrzowskie wykorzystanie StringBuilder nie uratowało sytuacji. Twórcami problemu okazali się zamówieni izomorfowie z planety Linear Chaos, którzy nie raz przerażali kadetów JavaRush. Zgodnie z oczekiwaniami, powierzchowne rozwiązania nie odpowiadały walidatorowi, ponieważ zawsze istniały łańcuchy, które zmuszały naiwny algorytm do pomijania słów. Należało dołożyć dodatkowe „kule”, które choć komplikowały problem, w ogólnym przypadku nie przybliżały rozwiązania, a coraz bardziej utwierdzały poczucie, że prosty warunek powinien mieć równie proste rozwiązanie. Musiałem zmienić taktykę i zagłębić się nieco w bardziej podstawowe obszary. Od razu zastrzegam, że w żadnym wypadku nie uważam się za eksperta w dziedzinie teorii grafów; tematy, które poruszę, nie wykraczają prawie poza zakres rozwiązywania problemu słownego domina, z wyjątkiem może jedynie kilka dygresji o charakterze teoretycznym. Zatem wykresy. Co to jest graf: jest to zbiór (zbiór, zbiór, lista - cokolwiek) wierzchołków połączonych ze sobą . Połączenia są zwykle nazywane krawędziami , wierzchołki nazywane są również węzłami lub węzłami. To jest graf: To jest także graf: Jeśli o krawędzi możemy powiedzieć, że ma ona kierunek, to graf nazywamy zorientowanym : Wykresy na pierwszych dwóch obrazach są nieskierowane. Można o nich powiedzieć, że krawędź (u, v) jest identyczna z krawędzią (v, u), czyli np. krawędzie (0, 4) i (4, 0) są tą samą krawędzią. Strzałki na krawędziach grafu skierowanego oznaczają, że krawędź (u, v) jest ścieżką od wierzchołka u do wierzchołka v, a krawędź (v, u) nie istnieje. Na trzecim zdjęciu widać krawędź (E, A). Nie ma krawędzi (A, E). Przyjrzyjmy się bliżej ostatniemu rysunkowi. Można zauważyć, że wierzchołek F nie ma w ogóle krawędzi, jest to całkiem możliwe. Zauważamy również, że w pobliżu wierzchołka A pojawiła się krawędź - pętla, a pomiędzy wierzchołkami B i D znajdują się dwie krawędzie skierowane inaczej. Wykresy skierowane pozwalają na takie artefakty. Załóżmy, że wykres przedstawia grupę znajomych, którzy obdarowują się nawzajem prezentami. Widzimy, że chciwy F nikomu nic nie dał, B i D wymienili się prezentami (poza tym, że każdy z nich dał prezent komuś innemu), a A sam sobie podarował, prawdopodobnie z okazji pomyślnego rozwiązania zagadki. problem z planety Linear Chaos. Przy okazji zauważcie, że wierzchołki grafu nie muszą być liczbami ani zawierać liczb, są raczej kontenerami, czyli tzw. mogą przechowywać dowolny przedmiot. Wykres jest opisem połączeń. Ważny termin, który przyda nam się później - liczba krawędzi dołączonych do wierzchołka (lub, jak mówią też, incydentalnych z nim) nazywana jest stopniem danego wierzchołka. Przykładowo na pierwszym rysunku wierzchołek 0 ma stopień 2, 1 ma stopień 4, 3 ma stopień 3, wierzchołek 0 drugiej figury ma stopień 1. W tym artykule nie będziemy się zagłębiać w różnorodność różnych typów grafów, wspomnimy tylko, że istnieją również wykresy ważone, tj. te, w których do każdej krawędzi dołączona jest określona liczba, która wskazuje „cenę” jej przejścia. Grafy połączone mają wiele podtypów, różniących się właściwościami. Na przykład wykresy, których krawędzie nigdzie nie tworzą cyklu, nazywane są drzewami (mają ciekawe rodziny o niesamowitych nazwach, takich jak na przykład „czerwono-czarne drzewa”) i są szeroko stosowane w różnych ważnych algorytmach i strukturach danych. Używanie wykresu do rozwiązania problemu Wszystko to jest bardzo interesujące, mówisz, ale co to wszystko ma wspólnego z konstruowaniem łańcucha słów? Okazuje się, że najbardziej bezpośrednio. Spójrzmy na nasz przykład testowy z warunku: { Amsterdam Melbourne Nowy Jork Kijów Wiedeń }. Zapiszmy w dowolnej kolejności litery „węzłowe”, do których przylegają słowa: {A, M, N, K, B} i połączmy je słowami. Jak widzimy, mamy graf skierowany, w którym węzłami są litery a krawędzie to słowa, które je łączą. Jeśli znajdziemy sposób na przejście wszystkich krawędzi od wierzchołka do wierzchołka, tak aby każdą krawędź odwiedzić tylko raz, nasz problem zostanie rozwiązany. Spróbujmy nieco inaczej rozmieścić węzły na diagramie: Teraz możemy lepiej zobaczyć, że nasz wykres jest zamkniętą pętlą. Sekwencję możemy rozpocząć dowolnym słowem i będzie to słuszna decyzja. Jednakże stan problemu mówi nam, że dowolne rozwiązanie będzie wystarczające. Zamieńmy Venę na Vladimira: Widzimy dwie konsekwencje: po pierwsze musieliśmy dodać nowy wierzchołek, czyli literę P, a po drugie widzimy, że nie da się już zapętlić naszego wykresu. Podsumujmy to wszystko i wprowadźmy dwa nowe terminy: 1. Graf spójny, którego krawędzie można pokonać odwiedzając każdą tylko raz, nazywany jest grafem zawierającym „ścieżkę Eulera ” . Cechą takiego grafu (poza brakiem wierzchołków bez krawędzi) jest parzysty stopień wszystkich wierzchołków z wyjątkiem dwóch (i tylko dwóch). 2. Jeżeli powrót do pierwotnego węzła okaże się możliwy, mówimy, że w grafie występuje „cykl Eulera” . Cechą takiego grafu (z wyjątkiem braku wierzchołków bez krawędzi) jest parzysty stopień wszystkich wierzchołków. Wyobraźmy sobie naszą listę takich miast: {Moskwa Anapa Adler Rostów nad Donem Wuhan}. Zbudujmy wykres: Na diagramie widać, że ten graf ma ścieżkę Eulera. Istnieją tylko dwa wierzchołki o stopniu nieparzystym - są to M i L, pozostałe są parzyste: A ma stopień 4, ponieważ pętla jest liczona dwukrotnie, a P i Y mają stopień 2. Jeśli wymyślimy algorytm, który w oparciu o ten schemat zbuduje trasę Eulera, powiedzmy w postaci listy {M, A, A, P, Y , L}, to rozwiążemy problem , ponieważ wypisanie słów w podanej kolejności będzie jedynie kwestią techniki. Zatem rozwiązanie naszego problemu słownego domina sprowadza się do zaimplementowania algorytmu znajdowania ścieżki Eulera (cykl jest „dowolny”) w grafie skierowanym. Dalej ->
To jest także graf: 
Jeśli o krawędzi możemy powiedzieć, że ma ona kierunek, to graf nazywamy zorientowanym : 
Wykresy na pierwszych dwóch obrazach są nieskierowane. Można o nich powiedzieć, że krawędź (u, v) jest identyczna z krawędzią (v, u), czyli np. krawędzie (0, 4) i (4, 0) są tą samą krawędzią. Strzałki na krawędziach grafu skierowanego oznaczają, że krawędź (u, v) jest ścieżką od wierzchołka u do wierzchołka v, a krawędź (v, u) nie istnieje. Na trzecim zdjęciu widać krawędź (E, A). Nie ma krawędzi (A, E). Przyjrzyjmy się bliżej ostatniemu rysunkowi. Można zauważyć, że wierzchołek F nie ma w ogóle krawędzi, jest to całkiem możliwe. Zauważamy również, że w pobliżu wierzchołka A pojawiła się krawędź - pętla, a pomiędzy wierzchołkami B i D znajdują się dwie krawędzie skierowane inaczej. Wykresy skierowane pozwalają na takie artefakty. Załóżmy, że wykres przedstawia grupę znajomych, którzy obdarowują się nawzajem prezentami. Widzimy, że chciwy F nikomu nic nie dał, B i D wymienili się prezentami (poza tym, że każdy z nich dał prezent komuś innemu), a A sam sobie podarował, prawdopodobnie z okazji pomyślnego rozwiązania zagadki. problem z planety Linear Chaos. Przy okazji zauważcie, że wierzchołki grafu nie muszą być liczbami ani zawierać liczb, są raczej kontenerami, czyli tzw. mogą przechowywać dowolny przedmiot. Wykres jest opisem połączeń. Ważny termin, który przyda nam się później - liczba krawędzi dołączonych do wierzchołka (lub, jak mówią też, incydentalnych z nim) nazywana jest stopniem danego wierzchołka. Przykładowo na pierwszym rysunku wierzchołek 0 ma stopień 2, 1 ma stopień 4, 3 ma stopień 3, wierzchołek 0 drugiej figury ma stopień 1. W tym artykule nie będziemy się zagłębiać w różnorodność różnych typów grafów, wspomnimy tylko, że istnieją również wykresy ważone, tj. te, w których do każdej krawędzi dołączona jest określona liczba, która wskazuje „cenę” jej przejścia. Grafy połączone mają wiele podtypów, różniących się właściwościami. Na przykład wykresy, których krawędzie nigdzie nie tworzą cyklu, nazywane są drzewami (mają ciekawe rodziny o niesamowitych nazwach, takich jak na przykład „czerwono-czarne drzewa”) i są szeroko stosowane w różnych ważnych algorytmach i strukturach danych. Używanie wykresu do rozwiązania problemu Wszystko to jest bardzo interesujące, mówisz, ale co to wszystko ma wspólnego z konstruowaniem łańcucha słów? Okazuje się, że najbardziej bezpośrednio. Spójrzmy na nasz przykład testowy z warunku: { Amsterdam Melbourne Nowy Jork Kijów Wiedeń }. Zapiszmy w dowolnej kolejności litery „węzłowe”, do których przylegają słowa: {A, M, N, K, B} 
i połączmy je słowami. 
Jak widzimy, mamy graf skierowany, w którym węzłami są litery a krawędzie to słowa, które je łączą. Jeśli znajdziemy sposób na przejście wszystkich krawędzi od wierzchołka do wierzchołka, tak aby każdą krawędź odwiedzić tylko raz, nasz problem zostanie rozwiązany. Spróbujmy nieco inaczej rozmieścić węzły na diagramie: 
Teraz możemy lepiej zobaczyć, że nasz wykres jest zamkniętą pętlą. Sekwencję możemy rozpocząć dowolnym słowem i będzie to słuszna decyzja. Jednakże stan problemu mówi nam, że dowolne rozwiązanie będzie wystarczające. Zamieńmy Venę na Vladimira: 
Widzimy dwie konsekwencje: po pierwsze musieliśmy dodać nowy wierzchołek, czyli literę P, a po drugie widzimy, że nie da się już zapętlić naszego wykresu. Podsumujmy to wszystko i wprowadźmy dwa nowe terminy: 1. Graf spójny, którego krawędzie można pokonać odwiedzając każdą tylko raz, nazywany jest grafem zawierającym „ścieżkę Eulera ” . Cechą takiego grafu (poza brakiem wierzchołków bez krawędzi) jest parzysty stopień wszystkich wierzchołków z wyjątkiem dwóch (i tylko dwóch). 2. Jeżeli powrót do pierwotnego węzła okaże się możliwy, mówimy, że w grafie występuje „cykl Eulera” . Cechą takiego grafu (z wyjątkiem braku wierzchołków bez krawędzi) jest parzysty stopień wszystkich wierzchołków. Wyobraźmy sobie naszą listę takich miast: {Moskwa Anapa Adler Rostów nad Donem Wuhan}. Zbudujmy wykres: 
Na diagramie widać, że ten graf ma ścieżkę Eulera. Istnieją tylko dwa wierzchołki o stopniu nieparzystym - są to M i L, pozostałe są parzyste: A ma stopień 4, ponieważ pętla jest liczona dwukrotnie, a P i Y mają stopień 2. Jeśli wymyślimy algorytm, który w oparciu o ten schemat zbuduje trasę Eulera, powiedzmy w postaci listy {M, A, A, P, Y , L}, to rozwiążemy problem , ponieważ wypisanie słów w podanej kolejności będzie jedynie kwestią techniki. Zatem rozwiązanie naszego problemu słownego domina sprowadza się do zaimplementowania algorytmu znajdowania ścieżki Eulera (cykl jest „dowolny”) w grafie skierowanym. Dalej ->
GO TO FULL VERSION