OIA-Wiki

En un árbol, ¿cuál es la longitud del camino más largo entre un par de nodos?

Lo que pide el enunciado se conoce como el diámetro del árbol.

Pensemos primero un poco qué pasa si tenemos un árbol que tiene una raíz. Cómo será el camino más largo del árbol? Bueno, una característica es que los extremos de este camino van a ser hojas. Ya que si alguno no lo fuera, podríamos seguir extendiendo el camino y obtener uno más largo.

El tema entonces está en ver qué dos hojas serán los extremos del camino.

Veamos que el camino entre dos hojas tiene como longitud la suma de las distancia desde las hojas en cuestión hasta el padre común de las hojas.

Ahora, supongamos que el camino más largo se tiene entre las hojas $h_1$ y $h_2$, cuyo padre común es $p$.

Qué pasa si hay una hoja $H$ que tiene mayor altura que $h_1$ y $h_2$? El camino desde esta hoja $H$ hasta $h_1$ tendrá como longitud la suma de las distancias desde $H$ y $h_1$ hasta su padre común. Lo mismo para el camino de $H$ a $h_2$. Si el $H$ no está en el subárbol de $p$, entonces el padre común entre $H$ y cualquiera de $h_1$ y $h_2$ estará más arriba que $p$, y el camino desde $H$ hasta $h_1$ será la distancia entre $h_1$ y $p$, más la distancia de $p$ al padre común de $H$ y $h_1$, más la distancia desde este padre común hasta $H$. Pero este último sumando será mayor a la distancia entre $p$ y $h_2$, por lo que el camino entre $H$ y $h_1$ será mayor al de $h_1$ y $h_2$, absurdo porque este último camino es el más largo.

Ahora, veamos qué pasa si $H$ está en el subárbol de $p$. $H$ no puede ser $p$ porque tendría altura menor a $h_1$ y $h_2$. Ahora, veamos que $h_1$ y $h_2$ están en subárboles de hijos distintos de $p$. Si no, el ancestro común más bajo sería el un hijo de $p$. Luego, si $H$ está en el subárbol de $p$, o bien está en el subárbol del hijo de $p$ en el que está $h_1$, o bien en el que está $h_2$. Si está en el mismo que $h_1$, luego el camino hasta $h_2$ va de $H$ a $p$, y de $p$ a $h_2$. Pero desde $H$ hasta $p$ hay una distancia mayor que desde $h_1$ hasta $p$, porque $H$ está más abajo. Es análogo si está en el mismo subárbol que $h_2$.

Entonces, llegamos a un absurdo por suponer que existe un nodo $H$ de mayor altura que ambas $h_1$ y $h_2$.

Conclusión: Uno de los extremos del diámetro del árbol es una de las hojas de mayor altura.

Como en principio no tenemos una raíz, pero para esto no nos importaba cuál fuera la raíz, basta con setear una raíz cualquier y encontrar el nodo más alejado. Éste nodo que encontremos será seguro un extremo del diámetro.

¿Y una vez que tenemos uno de los extremos? Fácil, simplemente buscamos el nodo que esté a mayor distancia de éste, con por ejemplo un BFS que ya conocemos.

Entonces el algoritmo que nos encuentra el diámetro (y sus extremos) del árbol es solamente poner un nodo cualquiera como raíz, buscar el más alejado. Y luego buscar el más alejado a este.

El código queda así:

<code cpp>

Tenemos el grafo en un “vector< vector<int> > grafo” vector<bool> visitado(grafo.size(), false); queue<pair<int,int> > q; q.push(make_pair(0,0)); empiezo como si el 0 fuera raíz, con una distancia 0 hasta la misma visitado[0]=true; while(!q.empty()){

  pair<int,int> parActual = q.front();
  q.pop();
  int nodo
  for(int i=0; i<grafo[nodoActual].size(); i++){
      if(!visitado[