Estructura de Datos

Algoritmos de ruta Kruskal Construye el MST(árbol de expansión mínima) una arista a la vez, con la diferencia que este encuentra una arista que conecte dos MST que van creciendo dentro de un bosque de MST crecientes, formado de los nodos del grafo original.  El algoritmo comienza a partir de un conjunto de árboles degenerados formados por un solo nodo, que son los nodos del grafo, y se comienzan a combinar los árboles de dos en dos usando la arista menos costosa posible, hasta que solo quede un solo árbol. Pasos del algoritmo: Primeramente ordena las aristas del grafo por su peso de menor a mayor (usando un quicksort por ejemplo) intentando unir cada arista siempre y cuando no se forme un ciclo. Al haber ordenado las aristas por peso comienza con la arista de menor peso, si los vértices que contienen dicha arista no están en la misma componente conexa entonces los unimos para formar una sola componente, se revisa si están o no en la misma componente conexa, al hacer ...

En la entrada de esta semana se hablara un poco sobre le algoritmo de recorrido de grafos, de manera que nos diga cual es la ruta mas corta para llegar de un nodo a otro. Dijkstra Es un algoritmo eficiente, con una complejidad de O(n ^2), donde "n" es el numero de vértices. Sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. Fue diseñado por el holandes  Edsger Wybe Dijkstra en 1959. Resuelve los problemas en sucesivos pasos, seleccionando en cada paso la solución mas optima con el objeto de resolver el problema. Es fundamento sobre el que se basa este algoritmo es el principio de optimizar: si el camino mas corto entre los vértices "u" y "v" pasa por el vértice "w", entonces la parte del camino que va de "w" a "v" debe ser el camino mas corto entre todos los caminos que van de "w" a "v". Así de esta manera se va construyendo sucesivamente  los camin...

Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computación, ya que permiten resolver problemas muy complejos. Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad saldrán varias carreteras, por lo que para ir de una ciudad a otra se podrán tomar diversos caminos. Cada carretera tendrá un coste asociado (por ejemplo, la longitud de la misma). Gracias a la representación por grafos podremos elegir el camino más corto que conecta dos ciudades, determinar si es posible llegar de una ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier otra, etc. Consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende ...

Este blog trata sobre algunos puntos importantes recibidos en la charla impartida en el Tecnológico de Costa Rica, hablaremos de conceptos que resaltan del tema Existen varios tipos de rutas para recorrer un grafo Ruta en un grafo: Secuencia de nodos tales que cada nodo Tiene un arco al siguiente nodo  Ruta simple: Rutas sin nodos repetidos  Ciclo en un grado: Ruta donde el primer nodo es igual al último nodo  Ciclo simple: Ciclo donde ningún modo se repite efecto el primero y el último  Ruta Hamilton: Simple que visita todos los nodos del grafo  Ciclo hamiltodiano: Ciclo simple que visité todos los modos del grado, existe un jugué de los años 80 que utilizaba este ciclo  Secuencias en biología molecular Las proteínas y los ácidos nucleicos se pueden modelar como hileras Frederick Sanger Bioquímico inglés, demostró que las proteínas tienen estructuras específicas. Gano un premio nobel en química 1958 y 1980. Único ganador de Dos premios ...

¿Qué es telecomunicaciones? Son la trasmisión a distancia de datos de información por medios electrónicos y/o tecnológicos. Los datos de información son transportados a los circuitos de telecomunicaciones mediante señales eléctricas. Un circuito básico de telecomunicación consiste en dos estaciones, cada una equipada con un receptor y un transmisor, que se pueden combinar para crear un transceptor. Topología en árbol Es una topología de red en la que los nodos están colocados en forma de árbol. Es una caracterización física de un objeto y sus componentes, que por su configuración se asemeja o recuerda a un árbol, en el sentido que sus ramificaciones tienden a converger en un origen o raíz Enlaces en un árbol Por definición, una estructura en árbol está constituida por nodos, y también por definición, un árbol vacío es también una estructura en árbol. Un nodo de un árbol tiene un determinado valor o contenido, y desde el mismo (a veces llamado nodo-padre) pueden derivar uno o v...

Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1. La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskii y Landis). La propiedad de equilibrio que debe cumplir un árbol para ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. Como se verá, el tiempo de ejecución de las operaciones sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.  Consideraciones sobre la implementación del tipo de dato abstracto  La única diferencia de los nodos de un árbol AVL con los de un árbol binario común es la variable altura en la estructura nodo.   Los nodos de un árbol pueden almacenar cualquier tipo de dato, arbitrariamente complejo. En est...