Algorytm zalewania
Algorytm zalewania to algorytm dystrybucji materiału do każdej części grafu . Nazwa wywodzi się od pojęcia zalania przez powódź .
Algorytmy zalewania są wykorzystywane w sieciach komputerowych i grafice . Algorytmy zalewania są również przydatne do rozwiązywania wielu problemów matematycznych, w tym z labiryntami i wielu problemów z teorii grafów .
Różne algorytmy zalewania mogą być stosowane do różnych problemów i działać z różnymi złożonościami czasowymi . Na przykład zalewania jest prostym, ale stosunkowo solidnym algorytmem, który działa w przypadku skomplikowanych geometrii i może określić, która część obszaru (docelowego) jest połączona z danym (źródłowym) węzłem w wielowymiarowej tablicy i jest trywialnie uogólnione do dowolnych struktur grafowych. Jeśli zamiast tego istnieje kilka węzłów źródłowych, nie ma żadnych przeszkód w geometrii reprezentowanej w wielowymiarowej tablicy i chce się podzielić obszar na podstawie tego, do którego z węzłów źródłowych znajdują się węzły docelowe, podczas gdy algorytm zalewania może nadal używany, algorytm jump flooding jest potencjalnie znacznie szybszy, ponieważ ma niższą złożoność czasową. Jednak w przeciwieństwie do algorytmu zalewania, algorytm zalewania skokowego nie może być w trywialny sposób uogólniony na grafy nieustrukturyzowane.
Zobacz też
- Powódź (sieci komputerowe)
- Retencja wody na powierzchniach matematycznych
- Wypełnienie
- Przechodzenie wykresu
- Drzewo rozpinające
- protokół drzewa opinającego