Algoritmo de inundação
 | Este artigo não cita fontes confiáveis. (Maio de 2023) |
Um algoritmo de inundação é um algoritmo para distribuir informação para todos nós de um grafo. Cada nó age como um receptor e transmissor de mensagens, e cada mensagem recebida é retransmitida para todos os vizinhos do nó, exceto pelo nó do qual a mensagem foi originada. Algoritmos podem atuar de forma mais robusta, adicionando rotinas para evitar transmitir duas vezes para um mesmo nó e para evitar laços infinitos, permitindo que a mensagem eventualmente expire no sistema. Outra variação do algoritmo é responder uma mensagem indicando o recebimento para cada mensagem enviada. Desta forma, o emissor original da mensagem pode saber quando toda a rede recebeu a mensagem, e, alternativamente, quem recebeu a mensagem.
Aplicação
[editar | editar código-fonte]Na área de rede de computadores, o algoritmo é usado para distribuir informação para todos os nós de uma rede conectada, em sistemas tais como a Usenet ou programas de compartilhamento de arquivos, e como parte de alguns protocolos de roteamento. Em termos de banda de rede há uma desvantagem, já que a mensagem pode ter somente um destinatário, mas mesmo assim será distribuída para cada nó.
Na matemática, o algoritmo de inundação é usado para resolver vários problemas, inclusive problemas de labirinto e os envolvidos com a teoria de grafos. Em um labirinto representado por um grafo, no qual cada corredor é uma aresta e cada esquina é um vértice, o algoritmo de inundação eventualmente encontra o final a partir de qualquer ponto, desde que haja um caminho válido para tal.
Na computação gráfica, o algoritmo de preenchimento por inundação (popularmente conhecido pelo termo inglês floodfill) é uma aplicação do algoritmo de inundação. Ele determina a área conectada a um nó dado em um vetor multi-dimensional de nós. Considerando-se uma imagem bitmap como sendo o vetor multi-dimensional (no caso, duas dimensões), e um pixel como sendo o nó, é possível usar o algoritmo para preencher toda uma área delimitada por uma cor com uma outra cor, a partir de um ponto inicial. Essa ferramenta é conhecida em programas de edição de imagem como a lata de tinta.
