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 20:11] sebach [Kruskal] |
algoritmos-oia:grafos:arbol-generador [2020/05/26 17:10] (actual) 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 38: | Línea 38: | ||
| <code cpp> | <code cpp> | ||
| - | // CODIGO | + | #include<bits/stdc++.h> |
| + | |||
| + | using namespace std; | ||
| + | |||
| + | #define forn(i,n) for(int i=0; i<(int)(n); i++) | ||
| + | |||
| + | int main(){ | ||
| + | int n, m; // ingreso cantidad de nodos y de aristas | ||
| + | cin>>n>>m; | ||
| + | vector< vector< pair<int,int> > > grafo(n); | ||
| + | map< pair<int,int>, int> longitudArista; | ||
| + | forn(i, m){ | ||
| + | int u, v, longitud; | ||
| + | cin>>u>>v>>longitud; | ||
| + | grafo[u].push_back(make_pair(longitud, v)); | ||
| + | grafo[v].push_back(make_pair(longitud, u)); | ||
| + | longitudArista[make_pair(u,v)] = longitud; | ||
| + | longitudArista[make_pair(v,u)] = longitud; // Guardamos esto para poder obtener la longitud dados los vértices | ||
| + | } | ||
| + | priority_queue< pair<int,int>, vector < pair<int,int> > , greater< pair<int,int> > > pq; | ||
| + | int INF=1e9; | ||
| + | |||
| + | int src = 0; // Tomo el nodo 0 como source, puede ser cualquiera | ||
| + | vector<int> key(n, INF); | ||
| + | vector<int> parent(n, -1); | ||
| + | vector<bool> enAGM(n, false); | ||
| + | pq.push(make_pair(0, src)); | ||
| + | key[src] = 0; | ||
| + | while (!pq.empty()){ | ||
| + | int u = pq.top().second; | ||
| + | pq.pop(); | ||
| + | enAGM[u] = true; // Así como marcábamos el visitado en Dijkstra, ahora lo marcamos como que ya está en el AGM, para no generar ciclos | ||
| + | forn(i, grafo[u].size()){ | ||
| + | int v = grafo[u][i].second; | ||
| + | int weight = grafo[u][i].first; | ||
| + | if (enAGM[v] == false && key[v] > weight){ // Si ahora el nodo v está más cerca que lo que teníamos antes, actualizamos el valor en la priority_queue | ||
| + | key[v] = weight; | ||
| + | pq.push(make_pair(key[v], v)); | ||
| + | parent[v] = u; // Al actualizar, también marcamos que el mejor camino para llegar a v es desde u | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int tamanioAGM = 0; | ||
| + | forn(i, n){ | ||
| + | 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; | ||
| + | tamanioAGM+=longitudArista[make_pair(i, parent[i])]; // Para esto guardamos la información en el mapa | ||
| + | } | ||
| + | } | ||
| + | cout<<"Tamanio minimo = "<<tamanioAGM<<endl; | ||
| + | } | ||
| </code> | </code> | ||
| Línea 44: | Línea 94: | ||
| === Complejidad === | === Complejidad === | ||
| - | $\large O(E*log(V)$ ?? | + | $\large O(E*log(V)$ ? Por qué? FIXME |
algoritmos-oia/grafos/arbol-generador.1514751102.txt.gz · Última modificación: 2017/12/31 20:11 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
