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/26 19:14] sebach ↷ Links adapted because of a move operation |
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 52: | Línea 102: | ||
==== Kruskal ==== | ==== Kruskal ==== | ||
- | **Prerrequisitos**: Estructura [[algoritmos-oia/union-find|Union Find]] | + | **Prerrequisitos**: Estructura [[algoritmos-oia:estructuras:union-find|Union Find]] |
**Idea**: La idea es, ordenar las aristas de menor valor a mayor, e ir agregando desde las más chicas, las que pueda sin que se genere un ciclo. La diferencia con Prim es que en Prim tenés siempre un árbol, y agregás de a un nodo al árbol. Acá, podés tener varios arbolitos separados, que de repente agregás una arista y unís dos árboles en uno. Esta oración es copada para entender el uso de Union Find. Empezamos con todos nodos separados, y vamos agregando aristas que conecten dos árboles diferentes, es decir que pertenezcan a distintos grupitos de nodos. | **Idea**: La idea es, ordenar las aristas de menor valor a mayor, e ir agregando desde las más chicas, las que pueda sin que se genere un ciclo. La diferencia con Prim es que en Prim tenés siempre un árbol, y agregás de a un nodo al árbol. Acá, podés tener varios arbolitos separados, que de repente agregás una arista y unís dos árboles en uno. Esta oración es copada para entender el uso de Union Find. Empezamos con todos nodos separados, y vamos agregando aristas que conecten dos árboles diferentes, es decir que pertenezcan a distintos grupitos de nodos. | ||
Línea 66: | Línea 116: | ||
<code cpp> | <code cpp> | ||
- | // CODIGO, usando lo que haya en la wiki de union find | + | #include<bits/stdc++.h> |
+ | |||
+ | using namespace std; | ||
+ | |||
+ | #define forn(i,n) for(int i=0; i<(int)(n); i++) | ||
+ | |||
+ | vector<int> padre, altura; | ||
+ | |||
+ | void init(int n){ | ||
+ | forn(i, n){ | ||
+ | padre.push_back(i); | ||
+ | altura.push_back(1); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | int find(int x){ | ||
+ | if(padre[x]!=x){ | ||
+ | padre[x]=find(padre[x]); | ||
+ | } | ||
+ | return padre[x]; | ||
+ | } | ||
+ | |||
+ | void merge(int x, int y){ | ||
+ | int px=find(x), py=find(y); | ||
+ | if(altura[px]<altura[py]){ | ||
+ | padre[px]=py; | ||
+ | }else{ | ||
+ | padre[py]=px; | ||
+ | if(altura[px]==altura[py]){ | ||
+ | altura[px]++; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | bool connected(int u, int v){ | ||
+ | return find(u)==find(v); | ||
+ | } | ||
+ | |||
+ | struct arista{ | ||
+ | int u, v, longitud; | ||
+ | }; | ||
+ | |||
+ | bool compareAristas(arista a, arista b){ | ||
+ | return a.longitud<b.longitud; | ||
+ | } | ||
+ | |||
+ | int main(){ | ||
+ | int n, m; // ingreso cantidad de nodos y de aristas | ||
+ | cin>>n>>m; | ||
+ | // inicializo los n Disjoin-Sets que tienen como padre a sí mismos y tamanio 1. | ||
+ | init(n); | ||
+ | vector< arista > aristas; | ||
+ | forn(i, m){ | ||
+ | arista a; | ||
+ | cin>>a.u>>a.v>>a.longitud; | ||
+ | aristas.push_back(a); | ||
+ | } | ||
+ | sort(aristas.begin(), aristas.end(), compareAristas); | ||
+ | vector<arista> elegidas; | ||
+ | int pesoMinimo=0; | ||
+ | forn(i, m){ | ||
+ | arista a = aristas[i]; | ||
+ | if(!connected(a.u, a.v)){ | ||
+ | merge(a.u, a.v); | ||
+ | elegidas.push_back(a); | ||
+ | pesoMinimo+=a.longitud; | ||
+ | } | ||
+ | } | ||
+ | cout<<"Peso minimo: "<<pesoMinimo<<endl; | ||
+ | forn(i, n-1){ | ||
+ | cout<<elegidas[i].u<<" "<<elegidas[i].v<<endl; | ||
+ | } | ||
+ | } | ||
</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 (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 === | ||
- | $\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))$ |