Como verificar se há um círculo em uma árvore?

Question

Aqui está uma árvore:

1. Haverá uma raiz.

2. Cada nó da árvore tem zero ou mais filhos.

3. É permitido que dois nós apontem para a mesma criança. Digamos, tanto o nó A quanto o nó B têm filho C.

No entanto, é proibido que,

O nó A é uma prole do nó B, e o nó B é uma prole de nó A.

Um caso proibido é

Nó A tem um nó filho C e nó D,

O nó C e D tem um nó filho E,

Nó E tem um filho de A.

A questão é: como determinar esse círculo de uma maneira mais rápida?

ATUALIZAR: Sei que isso é para encontrar qualquer ciclo em um gráfico direcionado. Agora eu consegui pensar em uma solução semelhante ao algoritmo de Tarjan.

Obrigado pelos comentários.

Answer 1

Faça um Primeira pesquisa em profundidade através da árvore. Se, em algum momento, você encontrar um nó que já está na sua pilha de retrocesso, há um círculo.

Answer 2

Os círculos podem ser encontrados usando 2 ponteiros e avançando em diferentes intervalos. Eventualmente, os ponteiros corresponderão, indicando um loop, ou o "mais rápido" chegará e terminará. A pergunta geralmente é feita de listas vinculadas, não por árvores.