Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:arboles:diametro [2017/12/09 20:07]
sebach Falta terminar codigo
+++ algoritmos-oia:grafos:arboles:diametro [2017/12/28 23:35] (actual)
ariel
@@ Línea 16: / Línea 16: @@
 Ahora, supongamos que el camino más largo se tiene entre las hojas $h_1$ y $h_2$, cuyo padre común es $p$.
-{{ :algoritmos-oia:arbol-diametro.png?400 |}}
+{{ :algoritmos-oia:arbol-diametro.png?200 |}}
 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$.
@@ Línea 35: / Línea 35: @@
 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.
+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 (con un bfs por ejemplo). Y luego buscar el más alejado a este (con otro bfs).
 El código queda así:
@@ Línea 41: / Línea 41: @@
 <code cpp>
-// Tenemos el grafo en un "vector< vector<int> > grafo"
+int main(){
+    // 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;
+    int maxDistancia=0;
+    int nodoMasAlejado;
+    while(!q.empty()){
+        pair<int,int> parActual = q.front();
+        int nodoActual=parActual.first;
+        int distancia=parActual.second;
+        q.pop();
+        if(distancia>maxDistancia){
+            maxDistancia=distancia;
+            nodoMasAlejado=nodoActual;
+        }
+        for(int i=0; i<grafo[nodoActual].size(); i++){
+            if(!visitado[grafo[nodoActual][i]]){
+                visitado[grafo[nodoActual][i]]=true;
+                q.push(make_pair(grafo[nodoActual][i], distancia+1));
+            }
+        }
+    }
+    //Ahora q esta empty, repetimos lo mismo empezando desde el nodo mas alejado
+    forn(i, visitado.size()){
+        visitado[i]=false;
+    }
+    q.push(make_pair(nodoMasAlejado, 0));
+    visitado[nodoMasAlejado]=true;
+    int diametro=0;
+    int otroExtremo;
+    while(!q.empty()){
+        pair<int,int> parActual = q.front();
+        int nodoActual=parActual.first;
+        int distancia=parActual.second;
+        q.pop();
+        if(distancia>diametro){
+            diametro=distancia;
+            otroExtremo=nodoActual;
+        }
+        for(int i=0; i<grafo[nodoActual].size(); i++){
+            if(!visitado[grafo[nodoActual][i]]){
+                visitado[grafo[nodoActual][i]]=true;
+                q.push(make_pair(grafo[nodoActual][i], distancia+1));
+            }
+        }
+    }
+}
+</code>
-vector<bool> visitado(grafo.size(), false);
+Lo que podríamos hacer también es una función que dado un nodo, nos devuelva un par ordenado con el nodo más alejado al dado, y la distancia entre ellos.
+Entonces simplemente llamamos a la función con el nodo $0$ (por ejemplo, cualquier raíz que seteemos al principio), y después de vuelta con el nodo obtenido como el más alejado al $0$.
-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
+===== Otra manera =====
-visitado[0]=true;
-while(!q.empty()){
+El problema de encontrar el diámetro, también lo podemos resolver con [[algoritmos-oia:grafos:arboles:programacion-dinamica-en-arboles|programación dinámica en el árbol]].
-    pair<int,int> parActual = q.front();
-    q.pop();
+¿Cómo?
-    int nodo
-    for(int i=0; i<grafo[nodoActual].size(); i++){
+Pensemos que para cada nodo $u$, definimos $haciaAbajo(u)$ como la mayor distancia desde $u$ hacia abajo, es decir, entre $u$ y el nodo de mayor altura del subárbol $u$; y definimos $masLargo(u)$ como el camino más largo contenido en el subárbol de $u$ que pasa $u$, que en general va a venir desde uno de sus hijos y continuar hacia otro de ellos.
-        if(!visitado[
+Para calcular $haciaAbajo(u)$, simplemente hacemos $1$ más la mayor distancia desde uno de sus hijos hacia abajo, recursivamente. Con caso base en una hoja, donde vale $0$.
+Y para calcular $masLargo(u)$, lo que haremos será pensar, qué dos hijos me conviene que estén en el camino, para que lo más largo posible? Y, los hijos $v_1$ y $v_2$ que maximizen sus valores de $haciaAbajo$.
+El siguiente código ilustra esta idea:
+<code cpp>
+const int MAXN=1e5;
+vector<int> haciaAbajo(MAXN), masLargo(MAXN);
+int diametro=0;
+void recorroSubarbol(int nodo, int padre){
+    vector<int> hijosHaciaAbajo;
+    for(int i=0; i<grafo[nodo].size(); i++){
+        if(grafo[nodo][i]!=padre){
+            int hijo=grafo[nodo][i];
+            recorroSubarbol(hijo, nodo);
+            hijosHaciaAbajo.push_back(haciaAbajo[hijo]);
+        }
+    }
+    sort(hijosHaciaAbajo.begin(), hijosHaciaAbajo.end());
+    int cantHijos=hijosHaciaAbajo.size();
+    int miHaciaAbajo=1;
+    if(cantHijos){
+        miHaciaAbajo+=hijosHaciaAbajo[cantHijos-1];
+    }
+    int masLargoPasandoPorMi=0;
+    if(cantHijos>=2){
+        masLargoPasandoPorMi=2+hijosHaciaAbajo[cantHijos-1]+hijosHaciaAbajo[cantHijos-2];
+    }
+    haciaAbajo[nodo]=miHaciaAbajo;
+    masLargo[nodo]=masLargoPasandoPorMi;
+    diametro=max(diametro, max(masLargo[nodo], haciaAbajo[nodo]));
+}
+//Llamamos a recorroSubarbol(0, -1), seteando al 0 como raiz. En diametro queda el valor
+</code>
+==== Problemas ====
+[[http://codeforces.com/contest/911/problem/F]]
+Agregar problemas!

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página