# TDA | Practica 4 Ejercicio 10
## Enunciado
- $10.\star$Se define la distancia entre dos secuencias de naturales $X=x_1,\ldots,x_k$ e $Y=y_1,\ldots,y_k$ como $d(X,Y)=\sum_{i=1}^k|x_i-y_i|.$ Dado un conjunto de secuencias $X_1, \ldots , X_n$ cada una de tamaño $k$, su grafo asociado $G$ tiene un vértice $v_i$ por cada $1\leq i\leq n$ y una arista $v_iv_j$ de peso $d(X_i,X_j)$ para cada $1\leq i<j\leq n.$ Proponer un algoritmo de complejidad $O(kn^2)$ que dado un conjunto de secuencias encuentre el árbol generador mínimo de su grafo asociado.
## Resolución
- Cada $X_i$ es una lista de $k \in \mathbb{N}$.
- $\therefore \ X_1, \dots, X_n$ es una colección de $n$ secuencias.
- Cada $X$ tiene $k$ elementos.
- Pensando un rato y leyendo la teorica, decidí optar por utilizar el algoritmo de kruskal.
- Tengo que definir un struct `tupla:<peso,i,j>`
- Defino una secuencia $X_i, \dots, X_j$.
- Ahora $\forall (X_i,X_j), i<j \Rightarrow$ Calcular: $d(X_j,X_j) = \sum_{k=1}^k |x_{ik} - x_{jk}|$
- Y añadimos este resuletado a la lista de aristas <$d(X_i,X_j),i,j$>
- Las ordeno por peso
- Armo un conjunto disjunto
- Proceso las aristas y formo el AGM
- $\forall$Tupla <$peso,i,j$> en la lista ordenada:
- Si $i \land j$ no estan conectados (chequear conjunto disjunto):
- Añadir $(i,j)$ a AGM
- Unir los conjuntos i,j
- Devolver AGM
```pseudocodigo
struct Arista {
int inicio;
int fin;
int peso;
}
funcion calcularAristas(secuencias,n,k):
listaAristas = [] // inicializo lista vacía
para i 1...n-1: // O(n)
para j i+1...n: // O(n)
peso = 0
para t 1...k: // O(k)
peso += |secuencias[i][t] - secuencias[j][t]|
listaAristas.agregar(Arista(i,j,peso))
return listaAristas
funcion ordenarAristas(listaAristas):
return sorted(listaAristas) // basado en su campo peso
// Tengo entendido que una lista de aristas puede tener hasta n² elementos en un grafo completo.
// Considerando esto sería O(n² log n), habria que consultar.
funcion inicializarConjuntos(n):
padre = []
rango = []
para i 1...n: // O(n)
padre.agregar(i)
rango.agregar(0)
return padre,rango
funcion kruskal(secuencias,n,k):
listaAristas = calcularAristas(secuencias,n,k) // O(kn²)
oredenarAristas(listaAristas) // O(n² log n)
(padre,rango) = inicializarConjuntos(n) // O(n)
agm = []
para cada arista en listaAristas: // O(n²) <=== Preguntar
si find(padre, arista.inicio) != find(padre, arista.fin):
agm.agregar(arista)
union (padre,rango,arista.inicio,arista.fin)
return
```
- El calculo inicial de las aristas tiene una complejidad de $O(kn^2)$, el paso de ordenar las aristas tiene una complejidad $O(n^2 log \ n)$ (preguntar esto)
- Confirmar complejidad del de sorting para hacer un analisis mas riguroso