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
- Desde cualquier vértice
s, haz BFS y elige un vérticeade distancia máxima. - 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 — 5Partiendo 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:
aestá en el subárbol det. Podemos escoger entreuyvun extremobtal que el camino deaabpase port: elegimos la otra rama, o el propiotsi es un extremo. Sices el extremo restante,dist(a,b) = h(a)+h(b)−2h(t) >= h(c)+h(b)−2h(t) = D.aestá fuera de ese subárbol. El camino deaause junta con el camino desde la raíz en un ancestrowsituado por encima det. Entoncesdist(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.