Herramientas de usuario
algoritmos-oia:grafos:arboles:diametro
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:grafos:arboles:diametro [2017/12/10 04:40] sebach |
algoritmos-oia:grafos:arboles:diametro [2017/12/28 23:35] (actual) ariel |
||
|---|---|---|---|
| Línea 41: | Línea 41: | ||
| <code cpp> | <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); | + | vector<bool> visitado(grafo.size(), false); |
| - | + | ||
| - | queue<pair<int,int> > q; | + | 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 | + | q.push(make_pair(0,0)); // empiezo como si el 0 fuera raíz, con una distancia 0 hasta la misma |
| - | visitado[0]=true; | + | visitado[0]=true; |
| - | + | ||
| - | int maxDistancia=0; | + | int maxDistancia=0; |
| - | int nodoMasAlejado; | + | int nodoMasAlejado; |
| - | + | ||
| - | while(!q.empty()){ | + | while(!q.empty()){ |
| - | pair<int,int> parActual = q.front(); | + | pair<int,int> parActual = q.front(); |
| - | int nodoActual=parActual.first; | + | int nodoActual=parActual.first; |
| - | int distancia=parActual.second; | + | int distancia=parActual.second; |
| - | q.pop(); | + | q.pop(); |
| - | if(distancia>maxDistancia){ | + | if(distancia>maxDistancia){ |
| - | maxDistancia=distancia; | + | maxDistancia=distancia; |
| - | nodoMasAlejado=nodoActual; | + | nodoMasAlejado=nodoActual; |
| - | } | + | } |
| - | for(int i=0; i<grafo[nodoActual].size(); i++){ | + | for(int i=0; i<grafo[nodoActual].size(); i++){ |
| - | if(!visitado[grafo[nodoActual][i]]){ | + | if(!visitado[grafo[nodoActual][i]]){ |
| - | visitado[grafo[nodoActual][i]]=true; | + | visitado[grafo[nodoActual][i]]=true; |
| - | q.push(make_pair(grafo[nodoActual][i], distancia+1)); | + | q.push(make_pair(grafo[nodoActual][i], distancia+1)); |
| + | } | ||
| } | } | ||
| } | } | ||
| - | } | + | //Ahora q esta empty, repetimos lo mismo empezando desde el nodo mas alejado |
| - | //Ahora q esta empty, repetimos lo mismo empezando desde el nodo mas alejado | + | |
| - | + | forn(i, visitado.size()){ | |
| - | forn(i, visitado.size()){ | + | visitado[i]=false; |
| - | 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++){ | + | q.push(make_pair(nodoMasAlejado, 0)); |
| - | if(!visitado[grafo[nodoActual][i]]){ | + | visitado[nodoMasAlejado]=true; |
| - | visitado[grafo[nodoActual][i]]=true; | + | |
| - | q.push(make_pair(grafo[nodoActual][i], distancia+1)); | + | 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> | </code> | ||
| Línea 103: | Línea 103: | ||
| ===== Otra manera ===== | ===== Otra manera ===== | ||
| - | El problema de encontrar el diámetro, también lo podemos resolver con [[algoritmos-oia:programacion-dinamica-en-arboles|programación dinámica en el árbol]]. | + | 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]]. |
| ¿Cómo? | ¿Cómo? | ||
| Línea 152: | Línea 152: | ||
| ==== Problemas ==== | ==== Problemas ==== | ||
| - | FIXME | + | [[http://codeforces.com/contest/911/problem/F]] |
| + | |||
| + | Agregar problemas! | ||
algoritmos-oia/grafos/arboles/diametro.1512880839.txt.gz · Última modificación: 2017/12/10 04:40 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
