Алгоритм флуда

Алгоритм лавинной рассылки — это алгоритм распределения материала по каждой части графа . Название происходит от концепции затопления в результате наводнения .

Алгоритмы флуда используются в компьютерных сетях и графике . Алгоритмы затопления также полезны для решения многих математических задач, включая задачи лабиринта и многих задач теории графов .

Различные алгоритмы лавинной рассылки могут применяться для разных задач и выполняться с разной временной сложностью . Например, алгоритм заливки — это простой, но относительно надежный алгоритм, который работает со сложной геометрией и может определить, какая часть (целевой) области соединена с данным (исходным) узлом в многомерном массиве , и тривиально обобщено на произвольные графовые структуры. Если вместо этого имеется несколько исходных узлов, в геометрии, представленной в многомерном массиве, нет препятствий, и необходимо сегментировать область на основе того, к какому из исходных узлов ближе всего целевые узлы, в то время как алгоритм заливки может все еще может использоваться, алгоритм скачкообразной заливки потенциально намного быстрее, поскольку имеет меньшую временную сложность. Однако, в отличие от алгоритма заливки, алгоритм скачкообразной заливки нельзя тривиально обобщить на неструктурированные графы.

См. также

• Наводнение (компьютерные сети)
• Удержание воды на математических поверхностях
• Наводнение
• Обход графа
• Связующее дерево
• Протокол связующего дерева
• Амнезиальное наводнение

Внешние ссылки

• Графы, взвешенные по ребрам или узлам, Фернан Мейер
• Утилита удержания воды