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:06] 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 |
Línea 134: | Línea 184: | ||
} | } | ||
} | } | ||
+ | cout<<"Peso minimo: "<<pesoMinimo<<endl; | ||
forn(i, n-1){ | forn(i, n-1){ | ||
cout<<elegidas[i].u<<" "<<elegidas[i].v<<endl; | cout<<elegidas[i].u<<" "<<elegidas[i].v<<endl; | ||
Línea 141: | Línea 192: | ||
</code> | </code> | ||
- | Se puede probar con el grafo del ejemplo, y se puede cambiar la función "compareAristas" para que si tienen misma longitud priorize la de menor $u$, o la de mayor $u$, para ver qué árbol elige y que el peso sigue siendo el mismo. | + | Se puede probar con el grafo del ejemplo, y se puede cambiar la función "compareAristas" para que si tienen misma longitud priorize la de menor $u$, o la de mayor $u$, para ver qué árbol elige (en un grafo con más de un AGM, por ejemplo se puede cambiar la longitud de la arista $(4, 5)$ de $5$ a $4$) y ver que el peso sigue siendo el mismo. |
=== Complejidad === | === Complejidad === | ||
El algoritmo ordena las aristas, y luego las recorre y hace un par de finds y quizás un merge, que tienen complejidad muy baja, por lo que la complejidad del algoritmo termina siendo de $\large O(E*log(E))$ | El algoritmo ordena las aristas, y luego las recorre y hace un par de finds y quizás un merge, que tienen complejidad muy baja, por lo que la complejidad del algoritmo termina siendo de $\large O(E*log(E))$ |