Inicio

La información aquí contenida es una compilación de distintas fuentes que comprenden la parte teórica, código fuente, imágenes y presentaciones que tienen el papel de servir al lector como material didáctico, el cual busca la comprensión de los temas propiamente dichos, pertenecientes a la Estructura de Datos II, y ademas, considerando los conocimiento previos como pilas, colas, búsquedas, recorridos, entre otros, que se recomiendan tener para la comprensión del material acá almacenado.

Se proyecta principalmente como fuente de consulta para los estudiantes de Ingeniería de Sistemas, ya que esta materia es parte fundamental de la carrera.

Encontrara la siguiente estructura en la mayoría las publicaciones:

-Explicación
-Presentacion
-Video complementario
-Código C++ suministrado

Recorrido Anchura - Altura de un grafo

Algoritmo Warshall

Algoritmo Warshall

Algoritmo de Dijkstra

Folleto Digital

Algoritmo de Kruskal

Arboles Enearios

Loa arboles  enearios pueden definirse como una estructura de datos donde cada nodo posee un numero indeterminado de hijos. Es una estructura recursiva,  y corresponden a la generalización de un árbol binario de cuyos nodos pueden desprenderse múltiples arboles binarios.  Las reglas que aplican a los arboles binarios pueden ser fácilmente transpoladas a los árboles enearios así como los conceptos base.

Un árbol n-ario  puede tomarse como un  un árbol de n elementos  con arboles de n elementos asociados a cada uno de sus componentes.  

Se pueden encontrar tres clases de recorridos para este tipo de árboles:  preorden, inorder y postorden. 

Posee los mismos conceptos  que un árbol binario:  nodos, raíz hoja, camino,  rama altura y peso. 

Las tres operaciones que se pueden llevar a cabo sobre este  tipo de arboles son sustracción, adición y búsqueda.

Existen algoritmos para cada uno de estos procedimientos, de  la manera que se presenta a continuación: 

Algoritmica:

Es muy Similar a la de un árbol binario

Primer nivel: 

•trata el caso de un árbol vacío

•crea estructuras de datos como iteradores

Segundo nivel:

•planteamiento recursivo

•Se tienen n avances posibles en la recursión

•Se requiere un ciclo para iterar sobre cada avance

Usos:

Árbol de Búsqueda binario - que se Utiliza en muchas aplicaciones de búsqueda donde los datos es constantemente entrada/salida, tales como el map y set objetos en muchos idiomas, bibliotecas.

Binary Space Partition - que se Utiliza en casi todos los de vídeo 3D juego para determinar qué objetos deben ser prestados.

Binario Trata - se Utiliza en casi todos los de alto ancho de banda del router para almacenar router-tablas.

Hash Árboles - se usa en los programas p2p y especializado imagen de la firma en la que un hash debe ser verificado, pero todo el archivo no está disponible.

Grafos Particulares

Grafo nulo:

En este grafo los vértices que lo componen no estás conectados, esto es, que son vértices aislados, se puede decir también, que es un grafo trivial que no tiene vértices ni aristas.

Grafo vacío:

Es aquel grafo que no tienen aristas.

Grafo trivial:

Es un grafo trivial es un grafo con 0 aristas, y 0 ó 1 vértices. Los grafo triviales son grafos completos: a aquel que no posee vértices se le llama grafo nulo, mientras que al que posee un vértice, se le conoce como grafo singleton.

Grafo simple:

Es aquel grafo que no posee bucles o lazos.

Grafo completo:

Un grafo completo es un grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas. Se puede hacer referencia que un grafo completo de n vértices tiene  aristas, y se nota . Es un grafo regular con todos sus vértices de grado . La única forma de hacer que un grafo completo se torne disconexo a través de la eliminación de vértices, sería eliminándolos todos. 

Grafo bipartito:

Es aquel grafo bipartito en el que todos los vértices de la partición  están conectados a todos los vértices de la partición  y viceversa. 

Grafo rueda:

Es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1). Se puede decir también, que un grafo rueda (Wn), o simplemente rueda, es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).

Grafo plano:

Es aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas. Todo grafo plano puede ser dibujado sobre la esfera, y viceversa.

Grafo perfecto:

Es aquel que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.