Caminho mais longo em uma árvore não direcionada com apenas um percurso

44

Existe esse algoritmo padrão para encontrar o caminho mais longo em árvores não direcionadas usando duas pesquisas profundas:

  • Inicie o DFS a partir de um vértice aleatório e encontre o vértice mais distante dele; diga que é .v vv
  • Agora inicie um DFS a partir de para encontrar o vértice mais distante dele. Esse caminho é o caminho mais longo do gráfico.v

A questão é: isso pode ser feito com mais eficiência? Podemos fazer isso com um único DFS ou BFS?

(Isso pode ser descrito de maneira equivalente como o problema de calcular o diâmetro de uma árvore não direcionada.)

emmy
fonte
2
O que você procura também é chamado de diâmetro da árvore. (On árvores "mais longo do caminho mais curto" e "caminho mais longo" são a mesma coisa uma vez que há apenas um caminho que liga dois nós.)
Raphael

Respostas:

22

Realizamos uma pesquisa profunda em ordem de pós e agregamos resultados no caminho, ou seja, resolvemos o problema recursivamente.

Para cada nó com filhos (na árvore de pesquisa), existem dois casos:u 1 , ... , u kvu1,,uk

  • O caminho mais longo em está em uma das subárvores .T u 1 , , T u kTvTu1,,Tuk
  • O caminho mais longo em contém . vTvv

No segundo caso, temos que combinar os um ou dois caminhos mais longos de em uma das subárvores; estes são certamente aqueles das folhas mais profundas. O comprimento do caminho é então se , ou se , com o conjunto múltiplo de alturas das subárvores¹.H ( k ) + H ( k - 1 ) + 2 k > 1 H ( k ) + 1 k = 1 H = { h ( T u i ) i = 1 , , k }vH(k)+H(k1)+2k>1H(k)+1k=1H={h(Tui)i=1,,k}

No pseudo-código, o algoritmo se parece com isso:

procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)        
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

  1. k AA(k) é o menor valor de em (estatística da ordem).kA
Rafael
fonte
@ Jeffff Quanto ao segundo comentário: De fato, e isso é tratado na última linha: height1 + height2é o comprimento desse caminho. Se é realmente o caminho mais longo, é escolhido por max. Também é explicado no texto acima, então não vejo seu problema? Certamente, você deve recuar para descobrir se esse é realmente o caminho mais longo e, mesmo que não, não dói (correção correta) recuar.
Raphael
@JeffE Em relação ao primeiro comentário, o cálculo para height2remove explicitamente height1da consideração, então como ele pode escolher o mesmo filho duas vezes? Isso também foi explicado no texto introdutório.
Raphael
1
Aparentemente, falamos diferentes dialetos de pseudocódigo, porque tenho dificuldade em entender o seu. Seria útil adicionar uma declaração explícita em inglês que longestPathHeight(T)retornasse um par (h,d), onde hé a altura Te do diâmetro de T. (Direito?)
JeffE
@JeffE Right; Eu pensei que isso estava claro no código, dada a explicação, mas aparentemente minha extrapolação de "clear" para outros paradigmas de pseudocódigo foi insuficiente (o meu é scalaesco, eu acho). Desculpe pela confusão, estou esclarecendo o código (espero).
Raphael
8

Isso pode ser resolvido de uma maneira melhor. Além disso, podemos reduzir a complexidade do tempo para O (n) com uma ligeira modificação na estrutura de dados e usando uma abordagem iterativa. Para uma análise detalhada e várias maneiras de resolver esse problema com várias estruturas de dados.

Aqui está um resumo do que eu quero explicar em uma postagem no meu blog :

Abordagem recursiva - diâmetro da árvore Outra maneira de abordar esse problema é a seguinte. Como mencionamos acima, o diâmetro pode

  1. completamente na sub-árvore esquerda ou
  2. completamente na sub-árvore direita ou
  3. pode atravessar a raiz

O que significa que o diâmetro pode ser idealmente derivado por

  1. o diâmetro da árvore esquerda ou
  2. o diâmetro da árvore certa ou
  3. a altura da subárvore esquerda + a altura da subárvore direita + 1 (1 para adicionar o nó raiz quando o diâmetro ultrapassar o nó raiz)

E sabemos que o diâmetro é o caminho mais longo, por isso tomamos o máximo de 1 e 2, caso esteja do lado ou de 3, se atravessarmos a raiz.

Abordagem Iterativa - Diâmetro da Árvore

Temos uma árvore, precisamos de uma meta informação com cada nó para que cada nó saiba o seguinte:

  1. A altura do filho esquerdo,
  2. A altura do filho certo e
  3. A maior distância entre os nós das folhas.

Uma vez que cada nó tem essas informações, precisamos de uma variável temporária para acompanhar o caminho máximo. Quando o algoritmo termina, temos o valor do diâmetro na variável temp.

Agora, precisamos resolver esse problema em uma abordagem de baixo para cima, porque não temos idéia dos três valores para a raiz. Mas conhecemos esses valores para as folhas.

Passos para resolver

  1. Inicialize todas as folhas com leftHeight e rightHeight como 1.
  2. Inicialize todas as folhas com maxDistance como 0, enfatizamos que, se leftHeight ou rightHeight for 1, criamos maxDistance = 0
  3. Mova para cima, um de cada vez, e calcule os valores para o pai imediato. Seria fácil, porque agora conhecemos esses valores para as crianças.
  4. Em um determinado nó,

    • atribua leftHeight como máximo de (leftHeight ou rightHeight de seu filho esquerdo).
    • atribua o rightHeight no máximo (leftHeight ou rightHeight de seu filho direito).
    • se algum desses valores (leftHeight ou rightHeight) for 1, faça maxDistance como zero.
    • se ambos os valores forem maiores que zero, crie maxDistance como leftHeight + rightHeight - 1
  5. Mantenha o maxDistance em uma variável temp e se na etapa 4 o maxDistance for maior que o valor atual da variável, substitua-o pelo novo valor maxDistance.
  6. No final do algoritmo, o valor em maxDistance é o diâmetro.
dharam
fonte
1
O que isso acrescenta à minha resposta mais antiga, além de ser menos geral (você lida apenas com árvores binárias)?
Raphael
9
Esta resposta é mais legível e mais fácil de entender na minha opinião (seu pseudocódigo é muito confuso).
reggaeguitar
-3

Abaixo está o código que retorna um caminho de diâmetro usando apenas uma única passagem DFS. Requer espaço extra para acompanhar o melhor diâmetro visto até o momento e o caminho mais longo, começando em um nó específico da árvore. Essa é uma abordagem de programação dinâmica baseada no fato de que um caminho de diâmetro mais longo não inclui raiz ou é a combinação dos dois caminhos mais longos dos vizinhos da raiz. Portanto, precisamos de dois vetores para acompanhar essas informações.

 int getDiam(int root, vector<vector<int>>& adj_list, int& height, vector<int>& path, vector<int>& diam) {
    visited[root] = true;
    int m1 = -1;
    int m2 = -1;
    int max_diam = -1;
    vector<int> best1 = vector<int>();
    vector<int> best2 = vector<int>();
    vector<int> diam_path = vector<int>();
    for(auto n : adj_list[root]) {
        if(!visited[n]) {
            visited[n] = true;
            int _height = 0;
            vector<int> path1;
            vector<int> path2;
            int _diam = getDiam(n, adj_list, _height, path1, path2);
            if(_diam > max_diam) {
                max_diam = _diam;
                diam_path = path2;
            }
            if(_height > m1) {
                m2 = m1;
                m1 = _height;
                best2 = best1;
                best1 = path1;
            }
            else if(_height > m2) {
                m2 = _height;
                best2 = path1;
            }
        }
    }

    height = m1 + 1;

    path.insert( path.end(), best1.begin(), best1.end() );
    path.push_back(root);

    if(m1 + m2 + 2 > max_diam) {
        diam = path;
        std::reverse(best2.begin(), best2.end());
        diam.insert( diam.end(), best2.begin(), best2.end() );
    }
    else{
        diam = diam_path;
    }


    return max(m1 + m2 + 2, max_diam);
}
Trevor Van Loon
fonte
2
Este não é um site de codificação. Nós desencorajamos respostas que consistem principalmente em um bloco de código. Em vez disso, queremos respostas que expliquem as idéias por trás do algoritmo e forneçam pseudocódigo conciso (que não exija conhecimento de nenhuma linguagem de programação específica para entender). Como você calcula o caminho mais longo, começando em um nó específico da árvore? (especialmente porque o caminho mais longo pode começar subindo a árvore DFS, ou seja, de volta à raiz)
DW