Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:arbol-generador [2017/12/26 19:14]
sebach ↷ Page moved from algoritmos-oia:arbol-generador to algoritmos-oia:grafos:arbol-generador
+++ algoritmos-oia:grafos:arbol-generador [2020/05/26 17:10] (actual)
ariel [Árbol generador]
@@ Línea 1: / Línea 1: @@
 ===== Á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:
@@ Línea 38: / Línea 38: @@
 <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>
@@ Línea 44: / Línea 94: @@
 === Complejidad ===
-$\large O(E*log(V)$ ??
+$\large O(E*log(V)$ ? Por qué? FIXME
@@ Línea 52: / Línea 102: @@
 ==== 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.
@@ Línea 66: / Línea 116: @@
 <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>
+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 ===
-$\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))$

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página