Diámetro de un árbol

Tema: Árboles · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 21 de la Ruta de Aprendizaje.

Qué problema resuelve

El diámetro de un árbol es la mayor distancia entre dos de sus vértices. Aquí la distancia cuenta aristas: un árbol de un solo vértice tiene diámetro 0. Suponemos un árbol no vacío, conectado, no dirigido y sin pesos, representado con listas de adyacencia.

No es necesariamente la mayor distancia desde el vértice 0. En una estrella, el centro está a distancia 1 de cualquier hoja, pero dos hojas están a distancia 2.

Dos recorridos bastan

  1. Desde cualquier vértice s, haz BFS y elige un vértice a de distancia máxima.
  2. Desde a, haz otro BFS. La mayor distancia encontrada es el diámetro.

En este árbol, cada guion representa una arista:

0 — 1 — 2 — 3
    |
    4 — 5

Partiendo de 1, los vértices más lejanos son 3 y 5, ambos a distancia 2. Cualquiera sirve. Desde 3, el más lejano es 5, a distancia 4: el camino es 3–2–1–4–5.

BFS devuelve distancias correctas porque cada arista cuesta uno. Lo especial del árbol es que cualquier elección de un vértice más lejano en el primer recorrido sirve como extremo de un diámetro.

Por qué ese primer extremo sirve

Enraíza mentalmente el árbol en s y llama h(v) a su profundidad, es decir, su distancia a s. Sea u–v cualquier diámetro de longitud D. Llama t al último vértice común de los caminos desde s hacia u y hacia v. Entonces:

D = h(u) + h(v) − 2h(t).

El vértice a elegido por BFS tiene profundidad máxima, así que h(a) >= h(u) y h(a) >= h(v). Hay dos posibilidades:

  • a está en el subárbol de t. Podemos escoger entre u y v un extremo b tal que el camino de a a b pase por t: elegimos la otra rama, o el propio t si es un extremo. Si c es el extremo restante, dist(a,b) = h(a)+h(b)−2h(t) >= h(c)+h(b)−2h(t) = D.
  • a está fuera de ese subárbol. El camino de a a u se junta con el camino desde la raíz en un ancestro w situado por encima de t. Entonces dist(a,u) = h(a)+h(u)−2h(w) >= h(v)+h(u)−2h(t) = D.

Ninguna distancia puede superar D, por definición de diámetro. En ambos casos encontramos desde a una distancia igual a D. Por eso a es extremo de algún diámetro y el segundo BFS lo encuentra. La prueba admite empates en el primer BFS.

La propiedad usa los caminos únicos del árbol. En un grafo general, dos BFS no garantizan el diámetro, aunque cada BFS siga calculando correctamente las distancias desde su origen.

Otra forma: combinar alturas

Enraíza el árbol. Define altura[u] como la mayor distancia desde u hacia un descendiente. Una hoja tiene altura 0.

Para cada hijo v, la rama que pasa por él mide 1 + altura[v]. Conserva las dos mayores longitudes, completando con ceros si hay menos de dos hijos. Su suma es el camino más largo que une dos ramas en u, o que empieza en u.

Todo camino tiene un único vértice de menor profundidad. Allí usa a lo más dos ramas de hijos. Por tanto, tomar el máximo de estas sumas sobre todos los vértices considera un camino al menos tan largo como cada candidato al diámetro, y cada suma corresponde a un camino real.

En el dibujo, con raíz 1, las ramas hacia 2, 4 y 0 miden 2, 2 y 1. Las dos mayores suman 4.

La implementación procesa primero los hijos y después el padre usando un orden invertido. Así evita una recursión de profundidad n en un árbol que tenga forma de camino.

Implementación recomendada (C++)

// devuelve (el nodo más lejano desde s, su distancia)
pair<int,int> mas_lejano(int s, const vector<vector<int>>& g) {
    vector<int> d(g.size(), -1);
    queue<int> q;
    d[s] = 0; q.push(s);
    int lejano = s;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (d[u] > d[lejano]) lejano = u;
        for (int v : g[u]) if (d[v] == -1) { d[v] = d[u] + 1; q.push(v); }
    }
    return {lejano, d[lejano]};
}
 
// pásale cualquier nodo del árbol (0 si numeras desde 0; 1 si numeras desde 1)
int diametro(const vector<vector<int>>& g, int cualquier_nodo) {
    int a = mas_lejano(cualquier_nodo, g).first;   // un extremo del diámetro
    return mas_lejano(a, g).second;                // desde él, el más lejano
}
 
// Alternativa: dos mayores alturas por nodo, sin recursión.
// Contrato: árbol no vacío, no dirigido, sin pesos; raíz válida.
int diametro_por_alturas(const vector<vector<int>>& g, int raiz) {
    int n = g.size();
    vector<int> padre(n, -1), orden{raiz}, altura(n, 0);
    padre[raiz] = raiz;
    for (size_t i = 0; i < orden.size(); i++) {
        int u = orden[i];
        for (int v : g[u]) if (padre[v] == -1) {
            padre[v] = u;
            orden.push_back(v);
        }
    }
    int respuesta = 0;
    for (int i = (int)orden.size() - 1; i >= 0; i--) {
        int u = orden[i], primera = 0, segunda = 0;
        for (int v : g[u]) if (padre[v] == u && v != u) {
            int candidata = altura[v] + 1;
            if (candidata > primera) { segunda = primera; primera = candidata; }
            else if (candidata > segunda) segunda = candidata;
        }
        altura[u] = primera;
        respuesta = max(respuesta, primera + segunda);
    }
    return respuesta;
}

Ambas variantes usan O(n) tiempo y O(n) memoria adicional. cualquier_nodo y raiz deben identificar un vértice existente. La lista debe contener ambas direcciones de cada arista. Si tienes un bosque, aplica el razonamiento por componente; eso requiere decidir si deseas un diámetro por componente o el máximo de todos.

Para recuperar los vértices del camino con dos BFS, guarda también el padre de cada vértice en el segundo recorrido y retrocede desde el más lejano hasta a.

Para comprobarlo

Prueba un vértice aislado, un camino de 5 vértices y una estrella con 4 hojas. Los diámetros son 0, 4 y 2. En la estrella, explica por qué tomar solo la mayor altura desde el centro daría 1 y perdería una de las dos ramas.