Grafos 02 - Flood Fill

"A Guerra de Troia pode ter sido um grande conflito bélico entre gregos e troianos, possivelmente ocorrido entre 1300 a.C. e 1200 a.C. (fim da Idade do Bronze no Mediterrâneo). Recentemente foram encontradas inscrições numa caverna a respeito de sobreviventes. Após um trabalho árduo, arqueólogos descobritam que as incrições descreviam relações de parentesco numa certa população. Cada item da inscrição indicavam duas pessoas que pertenciam a uma mesma família. Seu problema é determinar quantas famílias distintas existem."

Primeiro, vamos analisar como será o grafo do problema.

Vértices: Cada pessoa que existe em Troia.

Arestas: Cada inscrição dizendo que duas pessoas pertenciam a mesma família.

O problema quer o número de famílias distintas, ou seja, quer o número de componentes conexas do grafo. Vamos olhar um exemplo da entrada:

É fácil ver que as três componentes são $\{1, 2, 3, 4, 5, 6\}$, $\{7, 8\}$ e $\{9\}$.

Um algoritmo para resolver estes tipos de problema se chama Flood Fill.

O Algoritmo

Flood Fill se trata da ideia de ir preenchendo um grafo como se fosse um fluxo (como o próprio nome, em inglês, sugere). Vamos abordar duas maneiras muito conhecidas para se resolver este tipo de problema: busca em profundidade (DFS) e busca em largura (BFS).

DFS (depth-first search) se trata de, em cada passo, olhar os vizinhos do nó $v$ que se está avaliando e, para cada um deles cuja componente ainda não foi determinada, fazer sua componente ser a mesma de $v$ e chamar a função recursivamente nele.

BFS (breadth-first-search) se trata de fazer o mesmo procedimento da DFS. Porém, em vez de chamar a função recursivamente em um vizinho, este é adicionado a uma fila.

A DFS é mais fácil de se implementar e de se debugar. A BFS também tem suas vantagens, que veremos em breve. Ambas rodam em tempo $O(V+E)$, onde $V$ é o número de vértices e $E$ o número de arestas.

Vamos começar estudando a DFS. O código, como dito anteriormente, se trata de uma função recursiva e é algo bem simples. Olhe o seguinte pseudocódigo:

Na hora de procurar os vizinhos do vértice $X$, isso pode ser feito tanto pela matriz de adjacência, checando-se se existe uma aresta para todo vértice (complexidade $O(V)$), quanto com lista de adjacência (complexidade $O(grau(X))$). Se você ainda não está acostumado ao uso de lista de adjacência, faça por matriz. A maior parte dos problemas iniciantes não tem problema com esse tempo.

Vamos agora simular a DFS partindo do vértice $1$ do exemplo acima. Vou mostrar, na tabela, apenas alguns nós (os valores omitidos são assumidos como sendo iguais a $-1$).

	Nó	Componente
	1	1

Então, olhamos para o primeiro vizinho do $1$, que é o vértice $2$.

	Nó	Componente
	1	1
	2	1

De $2$, vamos para $3$.

	Nó	Componente
	1	1
	2	1
	3	1

De $3$, vamos para $4$.

	Nó	Componente
	1	1
	2	1
	3	1
	4	1

O vértice $4$ não tem nenhum vizinho cuja componente seja $-1$, então, voltamos para o vértice $3$.

	Nó	Componente
	1	1
	2	1
	3	1
	4	1
	3	1

De $3$, vamos para $6$.

	Nó	Componente
	1	1
	2	1
	3	1
	4	1
	3	1
	6	1

De $6$, vamos para $5$.

	Nó	Componente
	1	1
	2	1
	3	1
	4	1
	3	1
	6	1
	5	1

Agora, não será encontrado nenhum vizinho cuja componente seja $-1$, então a recursão irá voltar até o vértice $6$, depois para o $3$, $2$ e $1$, encerrando a função. Assim, encontramos a componente conexa $\{1, 2, 3, 4, 5, 6\}$.

 

Para fazer a BFS, em vez de chamar a função recursivamente, adicionamos o vizinho numa fila para ele ser posteriormente processado.

Assim como na DFS, você escolhe que ferramenta usar na hora de procurar os vizinhos de um vértice. Podendo usar as duas ferramentas citadas (vão rodar na mesma complexidade).

Vamos agora simular a BFS partindo do vértice $1$:

	Fila
	1

Acrescentamos os vértices $2$ e $4$ a fila e continuamos o procedimento.

	Fila
	1
	2
	4

Em $2$, adicionamos os vértices $3$ e $6$ e continuamos o procedimento.

	Fila
	1
	2
	4
	3
	6

No vértice $4$, não podemos adicionar ninguém, pois todos seus vizinhos estão marcados. Continuamos então o procedimento.

	Fila
	1
	2
	4
	3
	6

No vértice $3$, ainda não podemos adicionar ninguém. Continuamos então o procedimento.

	Fila
	1
	2
	4
	3
	6

No vértice $6$, adicionamos o vértice $5$ à fila.

	Fila
	1
	2
	4
	3
	6
	5

No $5$, não podemos adicionar ninguém.

A fila chegou ao seu fim, assim como a BFS. Foi possível, como visto, encontrar a componente conexa $\{1, 2, 3, 4, 5, 6\}$.

 

Ok. Ainda não mostrei completamente a solução para o problema que iniciou a aula. Se você olhar o enunciado do problema, verá que $N = 5\times 10^4$, ou seja, uma solução usando Matriz de Adjacência (que ficaria $O(N^2)$) é inviável. Portanto, nossa solução será usando Lista de Adjacência.

Isto deve ter sido suficiente pra se ter uma noção desse dois algoritmos. Tente, agora, resolver algumas questões para colocar em prática o aprendido! Caso tenha dificuldade em algum problema ou alguma dúvida sobre a teoria apresentada, volte para a página inicial do curso para preencher o formulário e nos enviar sua dúvida!

Problema 1 - Gincana - Clique aqui para ver a solução desse problema com Union-Find (se não entender, não se preocupe, ele só será usado em aulas posteriores).

Problema 2 - Colorindo

Problema 3 - Tarzan

Problema 4 - Batalha Naval

Problema 5 - Oil Deposits

Problema 6 - The die is cast

Problema 7 - You want what filled?

Problema 8 - Dominos 2

---

As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.