Herramientas de usuario
algoritmos-oia:grafos:arbol-generador
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:arbol-generador [2017/12/31 22:30] sebach [Prim] |
algoritmos-oia:grafos:arbol-generador [2020/05/26 17:10] ariel [Árbol generador] |
||
|---|---|---|---|
| Línea 1: | Línea 1: | ||
| ===== Árbol generador ===== | ===== Árbol generador ===== | ||
| - | Un árbol generador de un grafo, es un subgrafo conexo del mismo, que contiene a todos los vértices y no es un árbol. Estas propiedades son equivalente a decir que es un árbol que contiene todos los nodos del grafo en cuestión, y a partir del cual se puede llegar al grafo agregando aristas. | + | Un árbol generador de un grafo, es un subgrafo conexo del mismo, que contiene a todos los vértices y es un árbol. Estas propiedades son equivalente a decir que es un árbol que contiene todos los nodos del grafo en cuestión, y a partir del cual se puede llegar al grafo agregando aristas. |
| Por ejemplo: | Por ejemplo: | ||
| Línea 82: | Línea 82: | ||
| int tamanioAGM = 0; | int tamanioAGM = 0; | ||
| forn(i, n){ | forn(i, n){ | ||
| - | if(i!=src){ // El parent del src queda en -1 porque nunca lo actualizamos, enAGM[src] vale true desde el principio | + | if(i!=src){ // El parent del src queda en -1 porque nunca lo actualizamos, enAGM[src] vale true desde el principio |
| - | cout<<i<<" "<<parent[i]<<endl; | + | cout<<i<<" "<<parent[i]<<endl; |
| - | tamanioAGM+=longitudArista[make_pair(i, parent[i])]; // Para esto guardamos la información en el mapa | + | tamanioAGM+=longitudArista[make_pair(i, parent[i])]; // Para esto guardamos la información en el mapa |
| - | } | + | |
| } | } | ||
| - | cout<<"Tamanio minimo = "<<tamanioAGM<<endl; | + | } |
| + | cout<<"Tamanio minimo = "<<tamanioAGM<<endl; | ||
| } | } | ||
algoritmos-oia/grafos/arbol-generador.txt · Última modificación: 2020/05/26 17:10 por ariel
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
