18

Em Teoria dos Grafos, existe um conceito chamado LCA (Lower Common Ancestor - Ancestral comum mais próximo), onde dado um par de nós de uma árvore, deve-se encontrar o "pai" (ancestral) mais próximo desses dois nós.

Um exemplo de árvore é:

Árvore

Fiz uma implementação recursiva em Java baseada no algoritmo encontrado neste link. É possível editar e executar o código que implementei no ideone.

A pergunta é: existe uma versão iterativa desse algoritmo?

Note que não estou procurando necessariamente uma implementação em Java, mas pelo menos um pseudo-código.

Update: Em geral os enunciados deste tipo de problema não incluem informação do "pai" de cada nó, nem a informação no nível de "profundidade". A base para a implementação é a seguinte classe:

class Node {
    List<Node> children;
    Integer id;
}
2
  • 1
    Os seus nós têm referências para o pai? Isso não está claro na pergunta (não li a referência no SO em inglês). Se não tem, minha resposta abaixo não se aplica...
    – mgibsonbr
    27/12/2013 às 18:43
  • 1
    Infelizmente o problema em questão geralmente não tem essa informação. Obviamente o algoritmo poderia ter um passo adicional para percorrer a árvore e armazenar essa informação. Na verdade eu já resolvi dessa forma, isto é, dividindo em passos, mas estou buscando um algoritmo mais refinado.
    – utluiz
    27/12/2013 às 18:52

4 Respostas 4

8

Se cada nó da sua árvore possui informação sobre a "profundidade" (i.e. o número de nós entre ele e a raiz) então você pode substituir cada nó pelo seu pai até que ambos sejam o mesmo nó:

entradas a, b
profundidade_minima <- min(profundidade(a), profundidade(b))
enquanto profundidade(a) > profundidade_minima:
    a <- pai(a)
fim
enquanto profundidade(b) > profundidade_minima:
    b <- pai(b)
fim
enquanto a != b:
    a <- pai(a)
    b <- pai(b)
fim
saída a

Se você não conhece a profundidade a priori, é fácil obtê-la de forma iterativa:

entradas a, raiz
profundidade <- 0
enquanto a != raiz:
    profundidade <- profundidade + 1
    a <- pai(a)
fim
saída profundidade

Nota: essa resposta partiu do pressuposto que cada nó possui referência para seu pai (pressuposto já retificado pela edição na pergunta).


Atualização: posso estar enganado, mas acredito não haver solução iterativa para o caso em que um nó não possui referência para seu pai (exceto, é claro, a técnica geral de simular recursão por meio de uma pilha explícita). O motivo é que os nós a serem comparados podem estar em qualquer lugar na árvore, e sem nenhuma indicação de onde acaba sendo necessário buscar na árvore inteira. Uma árvore binária (a mais simples) terá potencialmente 2^n nós, onde n é sua profundidade máxima.

Não importa por que caminho você realize uma busca, se o nó x foi visitado e ele tem 2 ou mais filhos, você vai ter que se "lembrar" que ainda falta visitar seus outros filhos antes de iniciar a busca por um deles. Ou seja, os filhos ainda não visitados terão de ser colocados numa pilha, fila ou similar. O método pode variar, mas ainda seria equivalente a uma solução recursiva (em termos de performance e uso de memória).

A partir daí você tem várias opções: mapear cada nó para seu pai (e usar uma solução como a que propus acima) e sua profundidade, mapear cada nó para seu caminho até a raiz, fazer a busca por ancestral comum simultaneamente à busca por ambos os nós, etc.

1
  • É uma boa resposta, dado que eu não coloquei mais restrições para o problema. Entretanto, conforme meu código, em geral os enunciados desse tipo de problema não incluem nem a informação de profundidade nem do nó "pai".
    – utluiz
    27/12/2013 às 18:54
5

Muito boa resposta utluiz! Mas se me permite, na minha opinião um algoritmo é caracterizado pela sua eficiência, consumo de memória e precisão para cada caso do problema a ser resolvido. Como o seu algoritmo tem exatamente as mesmas características da implementação com recursão eu diria que em essência são o mesmo algoritmo!

Se você imprimir cada nó visitado repare que o algoritmo vai visitar os nós nesta ordem:

inserir a descrição da imagem aqui

Essa é exatamente a mesma ordem em que um algoritmo recursivo iria visitar cada nó. Além disso por usar uma pilha ele gasta proporcionalmente a mesma quantidade de memória! Os dois algoritmos tem O(n) para o pior caso, e vão visitar exatamente o mesmo número de nós para cada caso!

Vou propor um algoritmo verdadeiramente não recursivo:

static Node findClosestCommonAncestor(Node ancestralComum, Node p, Node q) {
    Queue<Node> fila = new ArrayBlockingQueue<Node>(100);
    while(true){
        // Adicionar todos os filhos do ancestral comum obtido ate agora na fila
        fila.clear();
        for( Node e: ancestralComum.children ){
            fila.add(e);
            fila.add(e);
        }
        // Vai passando os ancestrais ate descobrir os nodes e seus ancestrais
        Node p_ancestral=null, q_ancestral=null;
        while(p_ancestral == null || q_ancestral == null){
            Node e = fila.remove();
            Node a = fila.remove();
            for( Node filho : e.children ){
                fila.add(filho);
                fila.add(a);
            }
            if(e == p)
                p_ancestral = a;
            if(e == q)
                q_ancestral = a;    
        }
        // Condicoes para termino ou continuacao do algoritmo
        if(p_ancestral == q_ancestral)
            ancestralComum = p_ancestral;
        else
            break;
        if(p == ancestralComum || q == ancestralComum)
            break;
    }
    return ancestralComum;
}

O código completo pode ser visto e executado no Ideone.

Repare que ele visita os nós de uma forma completamente diferente:

inserir a descrição da imagem aqui

Ele utiliza uma fila ao invés de uma pilha, e é implementado de maneira muito mais eficiente com iterações do que com recursão!

A sua versão utiliza busca em profundidade e os métodos recursivos são muito bem eficientes nesse tipo de algoritmo. Esta versão utiliza busca em largura que é muito melhor implementada com métodos iterativos.

Sendo n o número de nós da árvore:

Busca em profundidade (seu algoritmo)

  • Complexidade O(n), no pior caso visita todos os nós da árvore
  • O pior caso de memória gasta é proporcional à profundidade da árvore
  • Se os dois nós estiverem bem profundos na árvore será bem eficiente
  • Se eles estiverem bem perto da raiz pode ser bem ineficiente

Busca em largura (meu)

  • Complexidade O(n^2), no pior caso visita n^2 nós (visita os mesmos repetidamente)
  • O pior caso de memória gasta é proporcional à largura máxima da árvore
  • Se os dois nós estiverem bem profundos na árvore será bem ruim
  • Se eles estiverem bem perto da raiz será bem eficiente

Existe uma versão deste algoritmo usando busca binária que tem complexidade O(n*logn) e gasta a mesma quantidade de memória, o que é bem melhor do que O(n^2). Existe também uma versão usando programação dinâmica que é O(n), mas gasta muuuito mais memória. Em ocasiões em que a árvore é muito profunda e a largura máxima é pequena, um método recursivo ou usando pilha pode gastar muita memória enquanto um iterativo não vai. E se o grafo tiver uma profundidade grande e os nós desejados estiverem na superfície a busca em largura será muito mais eficiente!

1
  • 3
    +1 pela boa análise de complexidade.
    – utluiz
    12/05/2016 às 0:57
4

A Wikipedia contém uma página sobre Tree Traversal que inclui pseudo-códigos para iterar sobre árvore binárias usando pilhas. Por exemplo, este é do Pre-order Traversal:

iterativePreorder(node)
  parentStack = empty stack
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      visit(node) #1
      parentStack.push(node) #2
      node = node.left
    else
      node = parentStack.pop() #3
      node = node.right

Anotei três pontos (#1, #2, #3), os quais irei comentar adiante.

Entretanto, para a resolução do problema em questão (LCA), não limitando-se a dois descendentes por nó (árvore binária), são necessários alguns ajustes:

  1. Uma pilha auxiliar para armazenar o filho atual sendo visitado a cada nível que o algoritmo desce na árvore. Diferente de uma árvore binária, onde basta percorrer o nó da esquerda e depois o da direita, para percorrer um nó com n filhos precisamos de um contador. E como cada filho pode ter m filhos, então deve haver um contador para cada nível da árvore.
  2. Uma segunda pilha auxiliar para armazenar o caminho até o primeiro nó encontrado. Como um dos objetivos do algoritmo é encontrar dois nós, devemos armazenar o caminho até o primeiro e continuar até encontrar o segundo.

Um pseudo-código para encontrar o ancestral mais próximo dos nós p e q, dada a raiz node, ficou assim:

findClosestCommonAncestor(node, p, q)
  parentStack = empty stack
  childIndexStack = empty stack
  firstNodePath = null
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)

      #1
      if (node == p || node == q)
        if (firstNodePath ≠ null)
          parentStack.add(node)
          int n = min(parentStack.length, firstNodePath.length)
          for i = (n - 1)..0
            if (parentStack(i) == firstNodePath(i))
              return parentStack(i)
          return null
        else
          firstNodePath = copy parentStack
          firstNodePath.push(node)

      #2
      if (not empty node.children)
        parentStack.push(node)
        childIndexStack.push(0)
        node = node.children(0)
      else
        node = null

    else

      #3
      node = parentStack.peek()
      i = childIndexStack.pop() + 1
      if (i >= node.children.length)
        node = null
        parentStack.pop()
      else
        node = node.children(i)
        childIndexStack.push(i)

Certamente ficou mais complexo, mas o conceito é basicamente o mesmo do anterior. Note que também marquei neste algoritmo três pontos, pois são análogos ao anterior. Vejamos:

  • #1 Este é o bloco onde o valor do nó atual é processado. O visit(node) do primeiro algoritmo foi substituído por um bloco que verifica se um dos nós foi encontrado. Caso tenha encontrado o primeiro nó ele salva a pilha atual. Caso tenha encontrado os dois ele compara as pilhas, item a item, procurando pelo pai mais próximo.
  • #2 O algoritmo inicial adiciona o nó atual na pilha e avança para o filho da esquerda. O segundo algoritmo generaliza para n filhos avançando para o primeiro filho (0).
  • #3 O algoritmo inicial desempilha um nó e avança para o filho da direita. O segundo algoritmo generaliza avançando para o próximo filho (anterior + 1).

O código em Java ficou assim:

class Node {
    List<Node> children = new ArrayList<Node>();
    Integer id;
    Node(Integer id) {
        this.id = id;
    }
}
Node findClosestCommonAncestor(Node node, Node p, Node q) {

    Stack<Node> parentStack = new Stack<Node>();
    Stack<Integer> childIndexStack = new Stack<Integer>();
    Stack<Node> firstNodePath = null;
    while (!parentStack.empty() || node != null) {

        if (node != null) {

            if (node == p || node == q) {

                if (firstNodePath != null) {
                    parentStack.add(node);
                    int n = Math.min(parentStack.size(), firstNodePath.size());
                    for (int i = n - 1; i >= 0; i--) {
                        if (parentStack.get(i) == firstNodePath.get(i)) {
                            return parentStack.get(i); 
                        }
                    }
                    return null;

                } else {
                    firstNodePath = new Stack<Node>();
                    firstNodePath.setSize(parentStack.size());
                    Collections.copy(firstNodePath, parentStack);
                    firstNodePath.push(node);
                }

            }

            if (!node.children.isEmpty()) {
                parentStack.push(node);
                childIndexStack.push(0);
                node = node.children.get(0);
            } else {
                node = null;
            }

        } else {

            node = parentStack.peek();
            Integer i = childIndexStack.pop() + 1;
            if (i >= node.children.size()) {
                node = null;
                parentStack.pop();
            } else {
                node = node.children.get(i);
                childIndexStack.push(i);
            }

        }

    }
    return null;

}

A versão completa do código Java está disponível para edição e teste no ideone.com.


Atualização

Ao contrário do enunciado proposto na pergunta, se houvesse a informação do nó pai e não dos filhos, um algoritmo bem mais eficiente poderia ser proposta.

Suponha que são dados dois nós P e Q. Esse algoritmo precisa apenas:

  1. Armazenar P e seus pais os nós num conjunto C
  2. Percorrer os pais de Q, começando do próprio elemento e retornar o primeiro elemento Q(i) que esteja no conjunto C.

Código em Java:

static class Node {
    Node parent;
    Integer id;
    Node(Integer id, Node parent) {
        this.id = id;
        this.parent = parent;
    }
    public String toString() {
        return id.toString();
    }
}

static Node findClosestCommonAncestor(Node p, Node q) {
    if (p == null || q == null) return null;

    //guarda os pais do nó P, incluindo o próprio
    Set<Node> parentsOfP = new HashSet<Node>();
    while (p != null) {
        parentsOfP.add(p);
        p = p.parent;
    }

    //procura o primeiro pai de Q que está entre os pais de P
    while (q != null) {
        if (parentsOfP.contains(q)) {
            return q;
        }
        q = q.parent;
    }
    return null;// not in the same tree
}

Código no IdeOne

1
  • Coloquei a minha resposta como certa pois consegui chegar ao resultado esperado conforme os parâmetros da pergunta.
    – utluiz
    2/01/2014 às 13:08
1

Usando o conceito de Pilha, nesse link você pode encontrar um exemplo de algorítimo e implementação.

No exemplo, vemos como atravessar a árvore sem usar recursão, então a menor distância pode ser obtida adicionando um passo no algorítimo

2
  • Percorrer uma árvore é "fácil". O problema em questão é um tanto mais complexo.
    – utluiz
    27/12/2013 às 18:59
  • +1 pelo link interessante.
    – utluiz
    2/01/2014 às 10:00

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .