Quantos caminhos simples existem?

URL: https://www.thehuxley.com/problem/448

Nesse problema, o objetivo é encontrar quantos caminhos

simples existem entre 2 nós de um grafo.

Um caminho simples é um caminho onde o mesmo nó não aparece mais de uma vez.

A ideia foi adicionar um campo inteiro, "contador", ao vértice para contar quantas vezes chegamos

no nó destino.

Inicialmente, todos os vértices estarão com esse campo com o valor 0, menos o nó destino que terá

o valor 1.

Então, iniciamos a busca em profundidade, começando no lugar de origem.

Quando o nó destino for descoberto, devemos pintá-lo imediatamente de preto e não expandiremos mais a partir dele.

Depois que cada nó tiver visitado todos os seus nós adjacentes, o contador dele deve ser a soma

dos contadores de todos os seus adjacentes.

Quando terminarmos, esse contador terá contado a quantidade de caminhos simples até o destino.

Por exemplo, vamos analisar a como essa ideia ocore para o grafo abaixo. Suponha que a origem é p e o destino é v.

Vamos fazer uma busca em profundidade, começando pelo p. Expandiremos o, r, u e t. Então retornaremos o valor do "contador" do nó t, que será 0. O contador do nó u assumirá o valor da soma dos contadores seus nós filhos, nesse caso apenas o nó t e portanto, também será 0.

Agora estamos no nó r e falta ainda expandir em profundidade o nó y. Então expandimos y e v. Ao chegar em v, paramos de expandir, pois ele é o nó que buscamos. O valor do "contador" do nó v é 1. O contador do nó y receberá a soma dos contadores de seus filhos, portanto o nó y será 1.

Isso significa que a partir do nó y, existe um caminho até v.

Ao desempilharmos a chamada de y, voltamos para o nó r, que receberá a soma dos contadores de seus filhos, nesse caso, o contador de r será 0 + 1, que é igual a 1. Mais uma vez, é importante ficar atento à intepretação. Esse 1, significa que a partir do nó r existe 1 caminho até v.

Continuando, estamos agora desempilhando a chamada à r e voltando para o. Vamos expandir o próximo filho que é v. Mas como v é o destino, retornamos e não expandimos. Então expandiremos o nó s que tem um filho que é o r. Mas o r já foi visitado antes e portanto não será mais expandido. Agora é que vem a "pulo do gato" dessa questão. Perceba que nesse ramo, estamos fazendo o caminho posr . Se você continuasse expandindo a partir de r, você iria chegar em v, pois bastava fazer yv, fazendo com que o caminho fosse posryv. Mas como você já fez esse trecho antes, não precisa fazer de novo. O valor de contador de r está guardando justamente a quantidade de caminhos existentes de r até v. Perceba que o valor de r é 1, por causa da expansão do primeiro ramo. Logo, voltando para o s, s receberá a soma de seus filhos, que no caso é só o r e portanto, o contador de s será 1.

Ao desempilhar mais uma vez, voltando ao o, o contador será 1 + 1 + 1 = 3. Ou seja, a partir de o existem 3 caminhos até v. Dois que a gente descobriu explicitamente: poryv e pov; e mais 1 que a gente não expandiu: posryv.

A próxima figura contém o raciocínio para o grafo inteiro.