ESTRUCTURAS DE DATOS 2

Tabla de contenido

Tabla de contenido.

3.1 Archivos.

3.1.1 ¿Que es un archivo?

3.1.2 ¿Para qué sirve un archivo?

3.1.3 ¿Cómo crear un archivo?

3.1.4 Funciones de un archivo.

3.1.5 Ejemplos de la creación de un archivo.

3.2 Arboles b y b+.

3.2.1 ¿Que es un árbol B?

3.2.2 Función insertar un nodo.

3.2.3 Función borrar un nodo.

3.2.4 ¿Que es un árbol B+?

3.2.5 ¿Cómo insertar una clave en un árbol B+?

3.2.6 ¿Cómo borrar o eliminar en un árbol B+?

3.3 Grafos.

3.3.1 ¿Que es un grafo?

3.3.2 Ejemplos de un grafo y un dígrafo.

3.3.3 ¿Para qué sirve los grafos?

3.3.4 Adyacencia.

3.3.5 Clases de grafos.

3.3.5.1 Grafos y dígrafos fuertemente conectados.

3.3.5.2 Grafo de camino simple.

3.3.5.2 Grafo euclidiano.

3.3.5.3 Grafo ha miltoniano.

3.3.5.4 Grados de un vértice.

3.3.5.5 Grafo regular.

3.3.5.6 Grafo con arco cíclico.

3.3.5.7 Multígrafo.

3.3.6 Matriz de adyacencia.

3.3.7 Lista de adyacencia.

3.3.8 Algoritmos.

3.3.8.1 Algoritmo de Prim

3.3.8.2 Algoritmo de washarll.

3.3.8.3 Algoritmo de Kruskal

3.3.8.4 Algoritmo de Dijkstra.

¿Que es un archivo?

algún medio y pueden ser usados por las aplicaciones. La forma en que una computadora organiza, da nombre, almacena y manipula los archivos se denomina sistema de archivos y suele depender del sistema operativo y del medio de almacenamiento .

¿Para que sirve un archivo?

Un archivo nos sirve para almacenar informacion para comunicar las aplicaciones y que ellas hagan uso de esa informacion o que neseciten ser almacenados para su uso en tiempo fututo, en un archivo se almacenan documentos de todo tipo.

¿Como crear un archivo?

Las principales funciones para crear un archivo son Fsacanf,Fopen,Fclose,stdout.

Ejemplo:

int main (void)

{

Fopen("mensaje.txt","w",stdout);

cout<<"hola mundo";

Fclose(stdout);

return ;

}

Funciones para crear un archivo.

fopen():Abre un archivo.

fclose():Cierra un archivo.

fgets():Lee una cadena de un archivo.

fputs():Escribe una cadena de un archivo.

fseek():Busca un byte especifico de un archivo.

fprintf():Escribe una salida con formato en el archivo.

fscanf():Lee una entrada con un formato en el archivo.

feof():Devuelve cierto si se llega al final del archivo.

ferror():Devuelve cierto si se produce un error.

fwrite():Escribe un bloque de datos a un archivo como “stream” (binario).

r: sólo lectura. El fichero debe existir.
w: se abre para escritura, se crea un fichero nuevo o se sobreescribe si ya existe.
a: añadir, se abre para escritura, el cursor se situa al final del fichero. Si el fichero no existe, se crea.
r+: lectura y escritura. El fichero debe existir.
w+: lectura y escritura, se crea un fichero nuevo o se sobreescribe si ya existe.
a+: añadir, lectura y escritura, el cursor se situa al final del fichero. Si el fichero no existe, se crea.
t: tipo texto, si no se especifica "t" ni "b", se asume por defecto que es "t"
b: tipo binario.

Hemos creado un archivo de texto con el nombre "mensaje" y en el escribimos "hola mundo" con la "w" que significa write, escribir.

int main

{

FILE* miarchivo;

char* nombredelarchivo="text1.txt";

Fscanf (miarchivo ,"%s",r)

printf ("lectura)

return 0;

}

con este pequeño codigo leemos un archivo y imprimimos por pantalla lo que hay en el.

Video explicativo

Bibliografia

http://c.conclase.net/ficheros/?cap=002
https://www.youtube.com/watch?v=ztEsa-dtn3E

ARBOLES AVL

¿Que es un árbol avl?

Desarrollado por Adelson-Velskii y Landis (1962). Los AVL son
árboles balanceados (equilibrados) con respecto a la altura de los subárboles:
Un árbol está equilibrado respecto a la altura si y solo si para cada uno de sus
nodos ocurre que las alturas de los dos subárboles difieren como mucho en 1

Es un árbol de búsqueda binario,en la cual la diferencia de las alturas de los subarboles de cada uno es uno.
Los arboles avl siempre están en equilibrio de tal modo de que si uno llegase a estar en desequilibrio realizamos rotaciones.

¿Para que sirve un arbol avl?

los podemos emplear en redes de mercadeo en seguridad informática seguridad de redes ya que nos daría un diagrama organizado y estructurados de los datos de la red

Características

*Cada nodo tiene signado un peso de acuerdo a las alturas de sus subarboles

*Un nodo tiene un peso de 1 si su subarbol derecho es mas alto , -1 si su subarbol izquierdo es mas alto y 0 si las alturas son las mismas

*La diferencia entre las alturas de los subarboles derecho e izquierdo no de exceder de 1

OPERACIONES BASICAS

*Insercion

*Rotacion Simple

*Rotacion Doble

*Eliminar

INSERCIÓN

En un árbol AVL tras realizar la insercion hay que comprobar que se sigue manteniendo la condición de equilibrio, o lo que es lo mismo , que la altura del subarbol izquierdo y la del subarbol derecho difieran en una unidad o sean iguales.Si se produce un desequilibrio hay que reestructurar el arbol para que siga siendo un arlbol AVL .El balanceo se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio, los mecanismos que usaremos para balancear el arbol son rotacion simple y doble rotacio a la derecha o al a izquierda segun el des balanceo del arbol.

Inserte las claves en el orden indicado a fin de incorporarlas a un árbol AVL

10,100,20,80,40,70.

Ingresamos el numero 10 después el 100 y así sucesivamente , y al ingresar el 20 como esta en medio de los dos pasa a ser la raiz del arbol

2) al insertar el 40 dividimos el subarbol izquierdo quedando de raiz el 80 y como hijos el 40 y el 100

g

SEGUNDO EJEMPLO

2)Inserte las claves en el orden indicado a fin de incorporarlas a un árbol AVL

5,10,20,30,40,50,60

Al igual que el arbol anterior pasa el 30 a ser la raiz ya que se encuentra en medio de los dos números creando mas ramas.

ELIMINACION

Cuando queremos eliminar un nodo del arbol debemos de tener siempre encuenta el balanceo del arbol ya que si esta desbalanceado deja de ser AVL , si se desbalancea debemos hacer rotaciones simples o dobles.Para eliminar el nodo lo hacemos como en un arbol binario ordenado, al localizar el nodo que queremos eliminar haremos los siguientes pasos:
*Si el nodo es un nodo hoja, simplemete lo eliminamos.
*Si el nodo solo tiene un hijo, lo sustituimos por su hijo
*Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el hijo izquierdo en el subarbol izquierdo del hijo derecho.

eliminar la siguente secuencia del arbol:
100,29,71,82,48,39,101,22,46, 17,3,20,25,10.

Se elimina el 100 y a continuación el 29.Al suprimir el 29 es necesario efectuar una restauración del tipo rotación simple y el árbol queda con la siguiente estructura:

NOTA: Despues de realizar la eliminacion concideraremos los siguentes aspectos para evaluar el balanceo del arbol

*Si el balanceo del padre del nodo eliminado cambia de 0 A + O - 1,el arbol quedo balanceado.
*Si el padre del nodo eliminado cambio de + o - 1 a 0, la altura del arbol ha cambiado y se afecta el e balanceo de su nodo antecesor
*Si el balanceo del padre del nodo eliminado cambia de + o - 1
a + o - 2 hay que hacer una rotacion. Despues de concluirla, el balanceo del padre podria cambiar, lo que as u vez podria forzarnos a hacer otrs rotacines en toda la ruta hacia arriba a medida que ascendemos hacia la raiz. Si encontramos en la ruta un nodo que cambie de 0 a + o - 1 entonces terminamos

ROTACIONES
Esta rotacion se usara cuando el subarbole izquierdo de un nodo sea 2 unidades mas alto que el derecho es decir su peso sea igual a -2.
Existen dos tipos de rotaciones
*Rotacion simple a la derecha.
*Rotacion simple a la izquierda.
*Rotacion doble a la derecha.
*Rotacion doble a la izquierda.

ROTACION SIMPLE A LA DERECHA
Una rotacion simple a la derecha se cumple si :
*El nodo indicado por P tiene valor de balance mayor a 1
*El nodo indicado por P tiene valor de balance mayor a 1

ROTACION SIMPLE A LA DERECHA

Es necesario realizar una rotación simple a la derecha cuando el suarbol izquierdo de un nodo sea 2 unidades mas alto que el derecho cuando su o cuando la sumatoria de sus nodos sea igual a 2. y ademas , la raiz del suarbol izquierdo tenga un balanceo de 1, es decir que este cargado ala izquierda

Procederemos del siguiente modo:

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una sumatoria de -2. Y llamaremos Q al nodo raíz del subárbol izquierdo de P. Además, llamaremos A al subárbol izquierdo de Q, B al subárbol derecho de Q y C al subárbol derecho de P.

Pasamos el subárbol derecho del nodo Q como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de Q siguen estando a la izquierda de P.
El árbol P pasa a ser el subárbol derecho del nodo Q.
Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.

En el árbol resultante se puede ver que tanto P como Q quedan equilibrados en cuanto altura. En el caso de P porque sus dos subárboles tienen la misma altura (n), en el caso de Q, porque su subárbol izquierdo A tiene una altura (n+1) y su subárbol derecho también, ya que a P se añade la altura de cualquiera de sus subárboles.

En el caso de que el subárbol izquierdo esté equilibrado, el procedimiento es similar, pero los FE de los nodos P y Q en el árbol resultante son diferentes.

En principio, parece poco probable que nos encontremos un árbol con esta estructura, pero es posible encontrarlos cuando se borran nodos.

1) Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo (+) hacemos rotación sencilla izquierda.

ROTACION SIMPLE A LA IZQUIERDA

Es necesario realizar una simple rotacion a la izquierda cuando el balanceo del subarbol derecho de un nodo sea 2 unidades mas alto que el izquierdo, es decir cuando el balance del suarbol izquierdo sea -2. y ademas , la raiz del suarbol derecho tenga como balanceo -1, es decir que este este cargado a a la derecha

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Y llamaremos Q al nodo raíz del subárbol derecho de P. Además, llamaremos A al subárbol izquierdo de P, B al subárbol izquierdo de Q y C al subárbol derecho de Q.

Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.
El árbol P pasa a ser el subárbol izquierdo del nodo Q.
Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.

ROTACION SIMPLE A LA IZQUIERDA

Es necesario realizar una simple rotacion a la izquierda cuando el balanceo del subarbol derecho de un nodo sea 2 unidades mas alto que el izquierdo, es decir cuando el balance del suarbol izquierdo sea -2. y ademas , la raiz del suarbol derecho tenga como balanceo -1, es decir que este este cargado a a la derecha

Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.
El árbol P pasa a ser el subárbol izquierdo del nodo Q.
Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.

4) Pasamos el subárbol derecho del nodo R como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de P.

5) Ahora, el nodo R pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo R, en lugar del nodo P. Como en los casos anteriores, previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.

6) El árbol P pasa a ser el subárbol derecho del nodo R.

Doble rotacion a la izquierda

Esta rotación se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de -1, es decir, que esté cargado a la izquierda.

En este caso también tendremos que realizar dos rotaciones.

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Llamaremos Q al nodo raíz del subárbol derecho de P, y R al nodo raíz del subárbol izquierdo de Q.

1) Haremos una rotación simple de Q a la derecha
2) Después, haremos una rotación simple de P a la izquierda.

Con más detalle, procederemos del siguiente modo

1) Pasamos el subárbol derecho del nodo R como subárbol izquierdo de Q. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de R siguen estando a la izquierda de Q.

2) Ahora, el nodo R pasa a tomar la posición del nodo Q, es decir, hacemos que la raíz del subárbol derecho de P sea el nodo R en lugar de Q.

3)El árbol Q pasa a ser el subárbol derecho del nodo R

4) Pasamos el subárbol izquierdo del nodo R como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de R siguen estando a la derecha de P.

5) Ahora, el nodo R pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo R, en lugar del nodo P. Como en los casos anteriores, previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.El árbol P pasa a ser el subárbol izquierdo del nodo R.

Si está desequilibrado a la izquierda (FE < –1), y su hijo derecho tiene distinto signo (+) hacemos rotación doble izquierda-derecha.

Video explicativo

https://www.youtube.com/watch?v=sAOeP9K-bEE

http://ingsistemas.ufps.edu.co/SEED/arbolavl.html

ARBOLES B Y B+

¿Que es un árbol B?

Son arboles multicamino con una construcción especial en forma ascendente que permite mantener un árbol balanceado
*Los arboles B son arboles cuyos nodos pueden tener un numero minimo multiple de hijos
*Tiene por objetivo agrupar en cada nodo mas de un elemento de manera que el acceso a un elemento cualquiera tenga lugar visitando un numero de nodos inferior a l caso de ABB
*La ventaja de los arboles B reside en los métodos para insertar y borrar registros, que dejan siempre el árbol balanceado

Los árboles B deben cumplir las siguientes características en cuanto a estructura:

Toda página tiene como máximo 2n nodos.
Toda página distinta de la raíz tiene como mínimo n nodos. La raíz tiene como mínimo 1 nodo.
Toda página que no sea una hoja tiene m+1 páginas hijas, siendo m el número de nodos de la página.
Todas las páginas hoja están en el último nivel.

Insertar

La operación de inserción en un árbol B es relativamente sencilla, sólo hay un caso en el que este procedimiento se complica ligeramente.

La primera acción a realizar en la operación de inserción es localizar el lugar adecuado en el árbol donde se insertará el nuevo elemento. De esta forma aseguraremos que la propiedad de orden se mantiene.

Una vez localizado el lugar adecuado, hay que tener en cuenta el número de nodos que tiene la página destino del nuevo elemento. Si tiene menos de 2n, entonces se inserta el nuevo nodo y se da por finalizada la operación de inserción.

La complejidad se produce cuando la página destino está al cmopleto de su capacidad, es decir, tiene 2n nodos. En estos casos el procedimiento a seguir es el siguiente:

Insertar el nodo como si realmente tuviese sitio libre.
Extraer el nodo que ocupa la posición del medio e insertarlo en la página padre. Si no hubiese página padre se crearía una nueva página con ese nodo.
Dividir la página original en dos nuevas páginas, cada una de ellas con n elementos. Estas páginas serán los hijos derechos e izquierdo del nodo que promocionó a la página superior.
Si la página a la que promociona el nodo mediano también se encuentra completa, se repetiría la misma operación de división y promoción.

Como consecuencia de que todas las hojas deben estar en el último nivel, los árboles B crecen hacia arriba, característica que también los diferencia del resto de árboles estudiados hasta ahora. Este crecimiento se produce cuando la inserción de un nodo en una página completa provoca su división.

Vamos a ver un ejemplo de inserción en árboles B.

Sobre este árbol se inserta el elemento 18. La página que le corresponde es la que contiene los elementos 10,15,17,19. Al estar completa se produce el ascenso del nodo mediano (el 17) y la división en dos páginas de la página original.

Borrar .

El proceso de borrado puede llegar a ser algo más complejo que la inserción.

La eliminación de elementos siempre se hace en una hoja, si el nodo a borrar no estuviese en un nodo hoja, se sustituiría el nodo a borrar por el inmediatamente inferior o superior, que sí que debe estar en undo hoja.

El caso más sencillo se produce cuando al eliminar un nodo de una página hoja, bien porque sea el nodo a eliminar, bien porque sea un elemento que sustituyó al nodo a eliminar, el tamaño de la página sigue siendo al menos n. De esta forma, la estructura del árbol se sigue cumpliendo y no hay que realizar ninguna reestructuración.

Aún resta un caso más. Este caso es idéntico al anterior, pero ahora la página vecina tiene el número mínimo de nodos. En esta situación se produce el efecto inverso a la división, las dos páginas se agrupan en una sola, formando una nueva página de 2n-1 nodos. A esta página se le añade el nodo central que estaba situado en la página padre.

Vamos a ver gráficamente los efectos de una eliminación.

Si sobre el árbol representado arriba se elimina el elemento 18, el árbol resultante sería el siguiente:

Para llegar a esta situación se fusionaron la primera y la segunda hoja con su nodo mediano situado en la página padre.

Además de estas características, los árboles B tienen que cumplir un cierto orden:

Los nodos dentro de una página mantienen un orden ascendente de izquierda a derecha.
Cada nodo es mayor que los nodos situados a su izquierda.
Cada nodo es mayor que los nodos situados a su derecha.

¿Que es un arbol B+?

un árbol B+ es un tipo de estructura de datos de árbol, representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Un árbol B+ es una variación de un árbol B.

Es la técnica mas utilizada para la organización de archivos

Todas las claves se encuentran en las hojas

Cualquier camino desde la raiz hasta la clave tiene la misma longitud

Ocupan mas espacio que los arboles B por que hay que duplicar las claves

Todas las hojas se encuentran en el mismo nivel.

¿Como construir un arbol B+?

Para crear un arbol B+ vamos ingresando los nodos en el orden de izquierda a derecha, si el nodo a insertar es mayo lo insertamos a la derecha y si es menor a la izquierda y así sucesivamente hasta insertar todos los nodos,pero a diferencia de los arboles b en este tipo de nodos, debemos crear una copia del nodo antecesor y lo ponemos en la hoja de primeras de izquierda a derecha
En un árbol B+, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo nivel, que corresponde al más bajo. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.

¿Como insertar una clave en un arbol B+?

La inserción es similar a la del arbol B, cuando se inserta y la pagina esta llena se divide endos ala izquierda , y ala derecha una copia de la clave del tejido sube a a la pagina antecesora

Ejemplo 2

¿Como borrar o eliminar en un árbol B+?

Para eliminar una clave debemos de considerar los siguientes aspectos:

*Si al eliminar la clave (siempre en una hoja) el número de claves es mayor o igual a m/2 el proceso ha terminado. Las claves de las páginas raíz o internas no se modifican aunque sean una copia de la eliminada,pues siguen constituyendo un separador válido entre las claves de las páginas descendientes.

*Si al eliminar la clave el número de ellas en la página es menor que m/2 será necesaria una fusión y redistribución de las mismas tanto en las páginas hojas como en el índice.

clave=nodo.

Ejemplo:

Ejemplo 2.

Si al eliminar una clave, m queda menor a d entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas. ( Hay dos ejemplos que ilustran como funciona este caso en la figura 8.10 ).

Bibliografia

http://www.virtual.unal.edu.co/cursos/ingenieria/2001412/capitulos/cap8/85.html

GRAFOS

¿Que es un grafo?

Los grafos son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas líneas. Si estas líneas son flechas, hablaremos de grafo dirigido (digrafo), mientras que si son simples líneas estamos ante un grafo no dirigido.

Más formalmente se pueden definir como un conjunto de vértices y un conjunto de aristas. Cada arista es un par (u,v), donde u y v pertenecen al conjunto de vértices. Si este par es ordenado el grafo es dirigido.

Vamos a ver un par de ejemplos:

Grafo no dirigido

Grafo dirigido.

¿Para que sirve los grafos?

Los campos de utilización de los grafos son muy varidos, ya que los vértices pueden representar cualquier elemento (ciudades, aeropuertos, pc's...), y las aristas serían la conexión entre esos elementos (carreteras, pasillos aéreos, redes...). Por lo tanto los grafos son muy usados en la modelización de sistemas reales.

Adyacencia.

Existe adyacencia entre 2 vertices si estan unidos por un arco.

Incidencia.

Los arcos inciden en los vertices, si uno de sus puntos llega a ese vertice

EL ARCO INCIDE ENTRE A Y B

EN GRAFO DIRIGIDO

EL ARCO INCIDE EN EL VERTICE B

Clases de grafos

Grafos y digrafos fuertemente conectados

Un grafo o digrafo esta fuertemente conectado si desde cualquier vertice se puede llegar a los demas

Grafo de camino simple

un grafo es de camino simple si partiendo de cualquer vertice podemos recorrer toda la estructura sin repetir arcos ni vertices

Grafo euleriano

Un grafo es euleriano si partiendo de cualquier vértice podemos recorrer todos los arcos llegando de nuevo al vertice origen, se pueden visitar los vértices cuantas veces sea necesario los arcos se pueden recorrer una sola vez.

Grafo hamiltoniano

Un grafo es hamiltoniano si partiendon de cualquier vertive podemos recorrer todos los vertices sin repetir ninguno, y finalmente llegar al vertice origen

Grados de un vertice

El grado de un vertice es igual al numero de arcos que inciden en ese vertice

Tabla.

Grado de un dígrafo.

Tabla.

Grafo regular

Un grafo es regular si todos los vertices tienen el mismo grado

Grafo con arco ciclico

Los arcos de un grafo son ciclicos si el arco parte de un vertice y llega al mismo.

Multigrafo

Un grafo es multigrafo cuando se acepta más de un arco uniendo dos vértices. En términos formales, no son grafos. Un multígrafo es un grafo que consta de segmentos múltiples y lazos.

Matriz de adyasencia

Un grafo se puede representar mediante una matriz. Es la forma más sencilla de representar un grafo. A esta matriz se le denomina matriz de adyacencia. la matriz de adyacensi se trabaja con 0 y 1 osea que es binaria si ponemos un 1 es por que existe un camino o un arco que incide en esos vertices si es 0 es por que lo lo hay, generalmente la diagonal principal de la matriz son 0 por que no hay ningún camino que salga de un vertice y llegue al mismo a excepción de los grafos ciclicos

Lista de adyacensia.
Es una representación de todas las aristas o arcos de un grafo mediante una lista.
si el grafo es no dirigido, cada entrada es un conjunto o multiconjunto de dos vertices conteniendo los dos extremos de la arista correspondiente. si el grafo es dirigido, cada entrada es un a tupla de dos nodos, uno denotando el nodo fuerte y el otro denotando el nodo destino del arco correspondiente

Lista de adyacencia del grafo anterio

"El siguiente articulo fue elaborado por un estudiante de Ingeniería de Sistemas de la Universidad Incca de Colombia"

Algoritmo de Prim

El algoritmo de Prim consiste en recorrer todos los vértices de un grafo en el menor peso posible, esto genera un árbol recubridor de menor peso, para que esto se cumpla el grafo debe ser conexo, estar etiquetado y sus arcos deben de tener un peso. Es decir:

Si observamos el arco que hay entre el vértice 0 y 2 tiene un numero en rojo, eso es lo que llamamos “peso” luego también es un grafo conexo y esta etiquetado.

En el algoritmo de Prim podemos comenzar por cualquier vértice luego para recorrerlo hay que tener los vértices adyacentes al que hemos escogido como punto de partida es decir, si empezamos con el vértice “0” este tiene dos vértices adyacentes que son el “2” y el “3”.

Entonces para saber a cuál de los dos escoger, entre el vértice “2” o “3” miramos el peso que tiene cada arco. Así el peso del vértice “0” al vértice “2” es de 5, y del vértice “0” al vértice “3” es de 8 entonces simplemente escogemos el de menor peso que es del vértice “0” al vértice “2” y ya tenemos trazado un arco. Así tenemos que hacer el mismo proceso para los demás vértices hasta completar todo el grafo, hay que tener en cuenta que al hacer el árbol recubridor, este no puede quedar cerrado por que quedaría como un ciclo y no queremos eso. Aquí tendremos un ejemplo…

El código para el algoritmo de Prim seria:

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

#define MAXIMO 20

#define PR(x) printf ("%s",x)

#define SALTO printf ("\n")

int main() {

int M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];

int suma, marcas[MAXIMO],padres[MAXIMO],minimo [MAXIMO];

int nv,i;

int PRIM (int M[][MAXIMO],

int N,int minimo[],int padres[],int marcas[]);

int lea_grafo (int grafo[][MAXIMO]);

void listar_g (int g[][MAXIMO], int nv);

void listar_r (int a[],int nv);

nv = lea_grafo (M);

listar_g (M ,nv);

SALTO;

getch();

suma = PRIM (M,nv,minimo,padres,marcas);

printf ("\n suma=%d\n",suma);

SALTO;

listar_r (minimo,nv);

SALTO;

listar_r (padres,nv);

SALTO;

listar_r (marcas,nv);

SALTO;

getch();

}

int PRIM (int M[][MAXIMO],int N,int minimo[],int padres[],int marcas[])

{

int min;

int j,k,escogido,suma;

for (j=1; j<=N; j++ ) {

minimo[j] = M[1][j];

marcas [j] = 0;

padres [j] = 1;

}

minimo [1] = 0;

padres [1]= 0;

marcas [1] = 1;

suma = 0;

for (k = 2; k <= N; k++) {

min = 32767;

for (j=1; j <= N; j++)

if (marcas [j] == 0 && minimo [j] < min) {

min = minimo [j];

escogido = j;

}

marcas [escogido] = 1;

suma = suma + min;

for (j=1; j <= N; j++)

if (marcas [j] == 0 &&

M[escogido][j] < minimo[j] ) {

minimo [j] = M[escogido][j];

padres [j] = escogido;

}

return (suma);

}

int lea_grafo (int grafo[][MAXIMO])

{

int v,ad,i,j,n,costo,lea();

PR("De numero de vertices...");

SALTO;

n = lea();

for (i=1; i <= n; i++)

for (j=1; j <=n; j++)

grafo[i][j] = 32767;

PR ("Vertice ... ");

v = 1;

printf ("%d",v);

SALTO;

while (v <= n) {

PR ("Lea el primer adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

while (ad != 99) {

PR("Lea costo del arco");SALTO;

costo = lea();

grafo [v][ad] = costo;

PR ("Lea otro adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

}

PR ("Vertice ...");

v++;

printf ("%d ",v);

SALTO;

}

return (n);

}

int lea() {

char L[10];

gets (L);

return (atoi (L));

}

void listar_g (int g[][MAXIMO], int nv) {

int i,j;

for (i=1; i <= nv; i++) {

for (j = 1; j <= nv; j++)

if (g[i][j] == 32767)

printf ("%s"," * ");

else printf ("%2d ",g[i][j]);

SALTO;

}

void listar_r (int a[],int nv) {

int k;

for (k=1; k<=nv; k++)

printf ("%d ",a[k]);

}

http://arantxa.ii.uam.es/~aa/practicas/P1/ejemploPrim.png

http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/xfig/coelho-2011/aula20-mst.png

ALGORITMO DE WARSHALL

Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo entre un par de vertices, como resultado nos da la mejor ruta para poder llegar al vértice destino en grafos dirigidos Como resultado nos dara una matriz de clausura transitiva.

PASOS

1) Hallamos la matriz de adyacencia.

2) Tomamos cada vértice como pivote llenando su respectiva matriz dependiendo si hay

camino o no

3) Como resultado nos da una matriz de adyacencia transitiva con la cual podemos saber si hay un camino de un vértice cualquiera a otro vértice elegido al azar

PIVOTE=cuando se dice tomamos el vértice como pivote quiere decir que podemos formar una conexión directa entre un vértice y un tercero, como si el vértice tomado como pivote no estuviera

· Matriz de adyacencia.

	a	b	c	D
a	0	1	0	0
b	0	0	1	0
c	1	0	0	1
d	0	0	0	0

· Tomamos como pivote a (a)

M1 (a)

	a	b	c	D
a	0	1	0	0
b	0	0	1	0
c	1	1	0	1
d	0	0	0	0

· Tomamos como pivote a (b) sin olvidar que (a) sigue siendo pivote

M2 (b)

	a	b	c	D
a	0	1	1	0
b	0	0	1	0
c	1	1	1	1
d	0	0	0	0

· Tomamos como pivote a (c) sin olvidar que los anteriores vértices siguen siendo pivotes en este caso (a) y (b)

M3 (c)

	a	b	c	D
a	1	1	1	1
b	1	1	1	1
c	1	1	1	1
d	0	0	0	0

· No realizamos la matriz con el pivote (d) ya que no tiene ningún arco de adyacencia

por lo tanto la matriz serian ceros ( 0 )

· Matriz de clausura transitiva.

	a	b	c	D
a	1	1	1	1
b	1	1	1	1
c	1	1	1	1
d	0	0	0	0

CODIGO

#include "stdio.h"

#include "stdlib.h"

#include "conio.h"

#include "alloc.h"

#define MAXIMO 20

#define PR(x) printf ("%s",x)

#define SALTO printf ("\n")

void main() {

int M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];

int nv,i;

void listar_g (int g[][MAXIMO], int nv);

int lea_grafo (int grafo[][MAXIMO]);

void WARSHALL (int M[][MAXIMO], int T[][MAXIMO], int nv);

nv = lea_grafo (M);

listar_g (M ,nv);

SALTO;

getch();

WARSHALL (M,T,nv);

listar_g (T,nv);

SALTO;

getch();

}

void WARSHALL (int M[][MAXIMO], int T[][MAXIMO], int nv)

{

int i,j,k;

void listar_g (int g[][MAXIMO], int nv);

void copiar (int a[][MAXIMO], int b[][MAXIMO],int nv);

copiar (T, M, nv);

for (k=1; k<=nv; k++) {

for (i=1; i<=nv; i++) {

if (i!=k) {

if (T[i][k] == 1) {

for (j=1; j<=nv; j++) {

if (T[i][j] == 0)

T[i][j] = T[k][j];

}

SALTO;

listar_g (T,nv);getch();

SALTO;

}

int lea_grafo (int grafo[][MAXIMO])

{

int v,ad,i,j,n;

int lea();

PR("De numero de vertices...");

SALTO;

n = lea();

for (i=1; i <= n; i++)

for (j=1; j <=n; j++)

grafo[i][j] = 0;

PR ("Lea el primer vertice. 99 para terminar...");

SALTO;

v = lea();

while (v != 99) {

PR ("Lea el primer adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

while (ad != 99) {

grafo [v][ad] = 1;

PR ("Lea otro adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

}

PR ("Lea otro vertice. 99 para terminar...");

SALTO;

v = lea();

}

return (n);

}

int lea() {

char L[10];

gets (L);

return (atoi (L));

}

void listar_g (int g[][MAXIMO], int nv) {

int i,j;

for (i=1; i <= nv; i++) {

for (j = 1; j <= nv; j++)

printf ("%d ",g[i][j]);

SALTO;

}

void copiar (int a[][MAXIMO], int b[][MAXIMO],int nv) {

int i,j;

for (i=1; i<=nv; i++)

for (j=1; j <= nv; j++)

a[i][j] = b[i][j];

}

"El siguiente articulo fue elaborado por un estudiante de Ingeniería de Sistemas de la Universidad Incca de Colombia"

Algoritmo de Kruskal

El algoritmo de kruskal es un algoritmo de recubrimiento mínimo conexo ponderado, o sea que va unir todos los nodos formando un árbol, tomando las aristas que tengan un peso que siempre sea menor.

Este árbol de un grafo es un sub-grafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles.

CARACTERÍSTICAS

· Algoritmo basado en las aristas

· Agregar las aristas , uno a la vez, en orden de peso creciente

· El objetivo del algoritmo de Kruskal es construir un árbol (sub-grafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
-Resuelve la misma clase de problemas que el de Prim, a diferencia que no se escoge un nodo al azar.

· Trabaja con grafos ponderados, y no dirigidos.

EJEMPLO:

CODIGO:

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <list>

#include<stdio.h>

#define REP(i,a) for(i=0;i<a;i++)

#define FOR(i,a,b) for(i=a;i<b;i++)

#define ii pair<int,int>

using namespace std;

vector<int> pset;

vector<pair<int,ii> >grafo;

void initSet(int size)

{

int i;

pset.resize(size);

REP(i,size+1)

pset[i]=i;

}

int findSet(int i)

{

return (pset[i]==i)? i:(pset[i]=findSet(pset[i]));

}

void unionSet(int i,int j)

{

pset[findSet(i)]=findSet(j);

}

bool isSameSet(int i,int j)

{

if(findSet(i) == findSet(j))

return true;

return false;

}

void kruskal(int N)

{int sum=0,i;

initSet(N);

sort(grafo.begin(),grafo.end());

for(i=0;i<grafo.size();i++)

{ pair<int,ii>aux=grafo[i];

if(!isSameSet(aux.second.first,aux.second.second))

{ cout<<"pasa en: "<<aux.second.first<<","<<aux.second.second<<endl;

sum=aux.first+sum;

unionSet(aux.second.first,aux.second.second);

}

cout<<"el peso"<<sum;

}

int main(){

int V,A,i,a,b,w;

cout<<"\t\tAlgoritmo de kruskal"<<endl;

cout<<"ingrese numero de aristas"<<endl;

cin>>A;

cout<<"ingrese numero de vertices"<<endl;

cin>>V;

cout<<"ingrese desde que vertice a que vertice: "<<endl;

for(i=0;i<A;i++){

cout<<"Del vertice: "; cin>>a; cout<<"al vertice: ";cin>>b;

cout<<"su peso: "; cin>>w;

grafo.push_back(pair<int,ii>(w,ii(a,b)));

}

kruskal(V);

system ("PAUSE");

return 0;

}

"El siguiente articulo fue elaborado por un estudiante de Ingeniería de Sistemas de la Universidad Incca de Colombia"

Algoritmo de Floyd

Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución. El algoritmo de Floyd es un ejemplo de programación dinámica.

El algoritmo de Floyd es más importante desde el punto de almacenamiento dado que puede ser implementado una vez se halla actualizado la distancia de la matriz.

EJEMPLO:

Lo siguiente es coger una columna con una fila y sumarla, si la suma de la fila y la columna es menor que el número que está en la posición evaluada se cambia pero si es mayor no se cambia. Si hay un infinito en la posición evaluada también se cambia por el número que haya dado la suma.

Teniendo en cuenta que no se puede sumar un infinito con otro número u otro infinito.

En la matriz de padres se coloca la letra que se está evaluando que es de donde proviene el número que se puso en la matriz de caminos.

Para saber cuál es el camino que tiene menor peso para llegar de la A a la E se mira en la última matriz de padres entonces para llegar a la E tiene que pasar por la C que es la letra que esta subrayada y si vemos es la que menor peso tiene para llegar a esta esto se ve en la matriz de camino. Otro ejemplo es para llegar de la E a la C tiene que pasar por la B que es la letra subrayada y también es el menor peso por el cual se puede ir lo podemos observar en la matriz de caminos.

CODIGO:

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

#define MAXIMO 20

#define PR(x) printf ("%s",x)

#define SALTO printf ("\n")

int main() {

int M[MAXIMO][MAXIMO];

int nv;

int lea_grafo (int grafo[][MAXIMO]);

void listar_g (int g[][MAXIMO], int nv);

void FLOYD (int M[][MAXIMO],int N);

nv = lea_grafo (M);

listar_g (M ,nv);

SALTO;

getch();

FLOYD (M,nv);

SALTO;

listar_g (M,nv);

getch();

}

void FLOYD (int M[][MAXIMO],int N)

{

int i,j,k;

void listar_g (int g[][MAXIMO], int nv);

for (k=1; k <= N; k++)

M [k][k] = 0;

for (k=1; k <= N; k++) {

for (i=1; i <= N; i++) {

if (i != k) {

if (M [i][k] != 32000) {

for (j=1; j <= N; j++) {

if (M[i][k] + M[k][j]

< M[i][j] )

M[i][j] =

M[i][k]+ M[k][j];}}}}

SALTO;

listar_g (M,N);

getch();}}

int lea_grafo (int grafo[][MAXIMO])

{

int lea(),v,ad,i,j,n,costo;

PR("De numero de vertices...");

SALTO;

n = lea();

for (i=1; i <= n; i++)

for (j=1; j <=n; j++)

grafo[i][j] = 32000;

PR ("Vertice ... ");

v = 1;

printf ("%d",v);

SALTO;

while (v <= n) {

PR ("Lea el primer adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

while (ad != 99) {

PR("Lea costo del arco");SALTO;

costo = lea();

grafo [v][ad] = costo;

PR ("Lea otro adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

}PR ("Vertice ...");

v++;

printf ("%d ",v);

SALTO;

}return (n);

}int lea() {

char L[10];

gets (L);

return (atoi (L));}

void listar_g (int g[][MAXIMO], int nv) {

int i,j;

for (i=1; i <= nv; i++) {

for (j = 1; j <= nv; j++)

if (g[i][j] == 32000)

printf ("%s"," * ");

else printf ("%2d ",g[i][j]);

SALTO;}}

"El siguiente articulo fue elaborado por un estudiante de Ingeniería de Sistemas de la Universidad Incca de Colombia"

Algoritmo de Dijkstra.

Se le atribuye el nombre al científico de computación Holandés Edsger Dijkstra, también llamado al algoritmo de caminos mínimos. Consiste en encontrar el camino más corto entre dos vértices, cada uno de los vértices debe tener una etiquete y los arcos un peso. El grafo no debe estar dirigido ya que si lo esta no sería de este tipo.

Primero tomamos un punto de partida x, este puede ser cualquier vértices y tomamos uno como el punto de llegada, se toman los vértices adyacentes al origen y se evalúa el de menor peso, es decir, el que tenga la etiqueta con el número menor, se toma ese camino y se hace el mismo proceso hasta llegar al vértice que se tomó como final.

Ejemplo

Calcular la longitud entre a y g.

Vértice	1	2	3	5	6
a	[0 , x]
b		[8 – a]		[6 – d]	[10 – e]
c		[5 – a]
d			[3 – c]
e				[2 – d]
f			[7 – c]	[5 – d]
g					[1 - e]

Camino más corto: a, c, d, e, g.

En el anterior cuadro se puede ver como se aplica el algoritmo de Dijkstra, se inicia en el primer vértice donde se pone el peso acumulado y el vértice de donde procede al ser el primero no tienen peso acumulado ni un vértice de procedencia, en la segunda casilla se toman los vértices adyacente al primero y se compara, el recuadro azul da la etiqueta definitiva que dice que este es el camino más corto entre los dos vértices comparados, se realiza hasta el final y obtenemos el camino más corto.

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

#define MAXIMO 20

#define PR(x) printf ("%s",x)

#define SALTO printf ("\n")

int main() {

int M[MAXIMO][MAXIMO],T[MAXIMO][MAXIMO];

int suma, marcas[MAXIMO],padres[MAXIMO],minimo [MAXIMO];

int nv,i;

void DIJKSTRA (int M[][MAXIMO],int N,int minimo[],int padres[],int marcas[]);

void listar_r (int a[],int nv);

int lea_grafo (int grafo[][MAXIMO]);

void listar_g (int g[][MAXIMO], int nv);

nv = lea_grafo (M);

listar_g (M ,nv);

SALTO;

getch();

DIJKSTRA (M,nv,minimo,padres,marcas);

listar_r (minimo,nv);

SALTO;

listar_r (padres,nv);

SALTO;

listar_r (marcas,nv);

SALTO;

getch();

}

void DIJKSTRA (int M[][MAXIMO],int N,int minimo[],

int padres[],int marcas[])

{

int min;

int j,k,escogido;

for (j=1; j<=N; j++ ) {

minimo[j] = M[1][j];

marcas [j] = 0;

padres [j] = 1;

}

minimo [1] = 0;

padres [1]= 0;

marcas [1] = 1;

for (k = 2; k <= N; k++) {

min = 32000; /* No puede ser 32767 para maquinas de 16 bits

para cada entero. ?Porque?.

Tambien en la lectura debe ser 32000 */

for (j=1; j <= N; j++)

if (marcas [j] == 0 && minimo [j] < min) {

min = minimo [j];

escogido = j;

}

marcas [escogido] = 1;

for (j=1; j <= N; j++)

if (marcas [j] == 0 &&

(min + M[escogido][j] < minimo[j]) ) {

minimo [j] = min + M[escogido][j];

padres [j] = escogido;

}

int lea_grafo (int grafo[][MAXIMO])

{

int lea(),v,ad,i,j,n,costo;

PR("De numero de vertices...");

SALTO;

n = lea();

for (i=1; i <= n; i++)

for (j=1; j <=n; j++)

grafo[i][j] = 32000;

PR ("Vertice ... ");

v = 1;

printf ("%d",v);

SALTO;

while (v <= n) {

PR ("Lea el primer adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

while (ad != 99) {

PR("Lea costo del arco");SALTO;

costo = lea();

grafo [v][ad] = costo;

PR ("Lea otro adjunto al vertice ");

printf ("%d ",v);

PR(". 99 para terminar");

SALTO;

ad = lea();

}

PR ("Vertice ...");

v++;

printf ("%d ",v);

SALTO;

}

return (n);

}

int lea() {

char L[10];

gets (L);

return (atoi (L));

}

void listar_g (int g[][MAXIMO], int nv) {

int i,j;

for (i=1; i <= nv; i++) {

for (j = 1; j <= nv; j++)

if (g[i][j] == 32000)

printf ("%s"," * ");

else printf ("%2d ",g[i][j]);

SALTO;

}

void listar_r (int a[],int nv) {

int k;

for (k=1; k<=nv; k++)

printf ("%d ",a[k]);

}

Bibliografia

http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/Ejer_Avl.htm

http://www.hci.uniovi.es/Products/DSTool/b/b-operaciones.html

http://c.conclase.net/edd/?cap=008

http://ingsistemas.ufps.edu.co/SEED/arbolavl.html

Tabla de contenido

ARCHIVOS

ARBOLES AVL

ARBOLES B Y B+

Insertar

GRAFOS

¿Que es un grafo?