En la mayoría de universidades los estudiantes de ingeniería de sistemas tienen que cursar estructuras de datos I y estructura de datos II, en estructura de datos II se ve una pequeña parte de arboles AVL, a veces archivos, arboles B, arboles B+ y grafos. El presente blog se hace con el fin de dar una herramienta para que así se les facilite estos temas en el transcurso del semestre. Al empezar la materia tal vez no conozcan nada de lo que van a ver, es por eso que se hace este blog porque les contribuirá en el desarrollo de la materia, para que así se les haga un poco mas fácil y puedan desempeñarse mucho mejor.
Objetivos:
Identificar cada uno de los temas para así tener una mejor comprensión de ellos.
Describir cada uno de los temas que se ven en la materia de estructura de datos II.
Contenido: 1. Arboles AVL 1.1 Factor de balance 1.2 Rotaciones 1.2.1 Rotación hacia la derecha. 1.2.2 Rotación hacia la izquierda. 1.2.3 Doble rotación hacia la derecha. 1.2.4 Doble rotación hacia la izquierda. 2. Manejo de archivos 2.1 Flujos 2.2Apuntador (puntero) FILE
2.3 Apertura de un archivo
2.4 Modos de apertura de un archivo 2.5 NULL y EOF 2.6 Cierre de archivos 3.Arboles B y B+ 3.1 Arboles B 3.2 Creación e inserción de un árbol B 3.3 Eliminación en un arbola B 3.4 Arboles B+ 3.5 Inserción en un árbol B+ 3.6 Eliminación en un árbol B+ 4. Grafos 4.1 ¿Que es un grafo y un grafo dirigido? 4.2 Adyacencia 4.2.1 Para el grafo 4.2.2 Para el dígrafo 4.3Incidencia 4.3.1 Para el grafo 4.3.2 Para el dígrafo 4.4 Grado de un vértice 4.5Tipos de grafos 4.6 Grafo conectado separadamente 4.7 Grafo y dígrafo fuertemente conectado 4.8 Dígrafo débilmente conectado 4.9 Camino simple 4.10 Grafo Euleriano 4.11 Grafo Hamiltoniano 4.12 Grafo regular 4.13 Grafo cíclico 4.14 Multígrafo 4.15 Grafo completo 5. Lista de Adyacencia 6. Matriz de Adyacencia 7. Matriz de caminos 8. Dígrafos fuertemente conectados 9. Algoritmos 9.1 Algoritmo de Warshall 9.2 Algoritmo de Dijkstra 9.3 Algoritmo de Prim 9.4 Algoritmo de Floyd 9.5 Algoritmo de Kruskal
Un árbol AVL es un árbol binario balanceado, es decir la altura de la rama izquierda no difiere de la rama derecha en más de una unidad. Ósea que está en un rango de (-1 > 0 > 1) si el dígito es mayor que 1 o menor que -1 quiere decir que el árbol esta des-balanceado por lo tanto se harán unas respectivas rotaciones a la derecha o hacia la izquierda. El árbol AVL fue ideado por los matemáticos rusosAdelson-VelskiiyLandis.
En la gráfica que observamos podemos ver un árbol AVL balanceado y vemos tres letras (A, B, C) donde A es el nodo padre, y B, C son los sub arboles.
Factor de balance:
Para saber el factor de balance empezamos de abajo hacia arriba es decir:
Como se muestra en la (grafica 2) empezamos desde abajo para hallar el FB; es decir desde donde está el nodo que contiene al “3”, Entonces el FB del nodo que contiene al “3” es 0 porque está apuntando a NULL. Ahora el FB del nodo que contiene al “6” es de 1; porque el nodo “1” tiene una raíz o hijo a su lado izquierdo que es el “3” y a la derecha no tiene nada, entonces al hacer una sencilla operación de resta se tiene que:
1-0=1
Ahora intentémoslo con el nodo que contiene al 10; según en la gráfica su FB es de 2 probémoslo:
4-2=2
Donde 4 es la cantidad de sub-arboles que tiene a su izquierda y 2 la cantidad de sub-arboles que tiene a su derecha.
Rotación hacia la derecha:
Para hacer una rotación a la derecha el árbol debe de estar des-balanceado hacia la izquierda es decir:
Ahora lo que debemos hacer es identificar quien es “p” y quien es “q”, para identificarlos se halla el FB del árbol. Entonces para hallar “p” miramos de abajo hacia arriba y apenas se encuentre un 2 le colocamos una flecha al frente indicando que este es “p” y al anterior nodo ósea el “6”, le colocamos “q”. Entonces quedaría de la siguiente manera:
Si recorremos el árbol en Inorden nos quedaría (3,6,7,8,9,10,12,15). Entonces al hacerle la rotación nos debería de quedar de igual manera, entonces para hacer la rotación tomamos el nodo que está indicando “p” y le damos un giro a la derecha y nos quedaría así:
Y ya tenemos el árbol balanceado porque al hacer el FB no nos da ningún número mayor a 1.
Rotación hacia la izquierda:
Para hacer una rotación a la izquierda el árbol debe de estar desbalanceado hacia la derecha es decir:
Ahora lo que debemos hacer es identificar quien es “p” y quien es “q”, para identificarlos se halla el FB del árbol. Entonces para hallar “p” miramos de abajo hacia arriba y apenas se encuentre un número mayor que 1 o un número menor que -1 le colocamos una flecha al frente indicando que este es “p” y al anterior nodo ósea el “20”, le colocamos “q”. Entonces quedaría de la siguiente manera:
Lo siguiente es rotar el nodo que está indicando “p” hacia la izquierda y quedaría de la siguiente forma:
De esta manera al hacer el FB nos damos cuenta que es un árbol balanceado por lo tanto es un árbol AVL.
Doble rotación hacia la derecha:
Para hacer la doble rotación a la derecha el árbol debe estar desbalanceado hacia la izquierda, el factor de balance del nodo indicado por “p” debe ser mayor a 1 y el FB del nodo indicado por “q” es igual a -1. Hay que tener en cuenta dos instrucciones las cuales son:
- -Una rotación a la izquierda desde “q”.
- -Una rotación a la derecha desde “p”.
Ejemplo:
Ya identificamos el FB ahora identificamos quien es “p” y quien es “q” al hacerlo nos debería quedar así:
Ahora bien vamos a empezar las rotaciones, dice que la primera rotación es del nodo que está apuntando “q” y es hacia la izquierda entonces quedaría de la siguiente manera:
Como ya rotamos el nodo que apunta “q”, ahora rotamos hacia la derecha el nodo que apunta “p” y nos quedaría así:
Y nos queda un árbol AVL balanceado, podemos verificarlo al hacer el FB.
Doble rotación hacia la izquierda:
Para hacer la doble rotación a la izquierda el árbol debe estar desbalanceado hacia la derecha, el factor de balance del nodo indicado por “p” debe ser menor a -1 y el FB del nodo indicado por “q” es igual a -1 ó a 1. Hay que tener en cuenta dos instrucciones las cuales son:
- -Una rotación a la derecha desde “q”.
- -Una rotación a la izquierda desde “p”.
Ejemplo:
Ya identificamos el FB ahora identificamos quien es “p” y quien es “q” al hacerlo nos debería quedar así:
Ahora vamos a empezar las rotaciones, dice que la primera rotación es del nodo que está apuntando “q” y es hacia la derecha entonces quedaría de la siguiente manera:
Como ya rotamos el nodo que apunta “q”, ahora rotamos hacia la izquierda el nodo que apunta “p” y nos quedaría así:
Y nos queda un árbol AVL balanceado, podemos verificarlo al hacer el FB. En este link se puede observar un ejemplo de cada una de las rotaciones que se vieron anteriormente http://www.youtube.com/watch?v=8ly4jg3TdSE
Un flujo (stream) es una abstracción que se refiere a una corriente de datos que fluyen entre un origen o fuente (productor) y un destino o sumidero (consumidor). Entre el origen y el destino debe existir una conexión o canal (pipe) por la que circulen los datos. La apertura de un archivo supone la conexión del programa con el dispositivo que contiene el archivo; por el canal que comunica el archivo con el programa van a fluir las secuencias de datos. Hay tres flujos o canales abiertos automáticamente:
- -Extern FILE *stdin;
- -Extern FILE *stdout;
- -Extern FILE *stderr;
Apuntador (puntero) FILE:
Los archivos se ubican en dispositivos externos como cintas, cartuchos, discos, discos compactos, etc., y tienen un nombre y unas características. En el programa el archivo tiene un nombre interno que es un puntero a una estructura predefinida (apuntador a archivo). Esta estructura contiene información sobre el archivo, tal como la dirección del buffer que utiliza, el modo de apertura del archivo, el ultimo carácter leído del buffer y otros detalles que generalmente el usuario no necesita saber. El identificador del tipo de la estructura es FILE y esta declarada en el archivo de cabecera stdio.h
Ejemplo: FILE* pf;
Apertura de un archivo:
Para procesar un archivo en C (y en todos los lenguajes de programación) la primera operación que hay que realizar es abrir el archivo. La apertura del archivo supone conectar el archivo externo con el programa, e indicar como va ser tratado el archivo: binario, de caracteres, etc. El programa accede a los archivos a través de un puntero a la estructura FILE, la función de apertura devuelve dicho puntero. La función para abrir un archivo es fopen( ) , el formato de llamada es:
fopen (nombre_archivo, modo);
Donde
nombre: Contiene el identificador externo del archivo.
modo: Contiene el modo en que se va a tratar el archivo.
Ejemplo:
FILE* pf;
pf = fopen (nombre_archivo, modo);
Modos de apertura de un archivo:
Al abrir el archivo, fopen( ) espera como segundo argumento el modo de tratar el archivo. Fundamentalmente se establece si el archivo es de lectura, escritura o añadido, y si es de texto o binario. Para no depender del entorno es mejor indicar si es de texto o binario. Se utiliza la letra b para modo binario como ultimo carácter de la cadena ”modo”. Algunos compiladores admiten la letra t para indicar archivo texto. Por consiguiente, los modos de abrir un archivo de texto son:
“rt”, “wt”, “at”, “r+t”, “w+t”, “a+t”.
Y los modos de abrir un archivo binario son:
“rb”, “wb”, “ab”, “r+b”, “w+b”, “a+b”.
“r+”: Abre para lectura
“w+”: Abre para crear nuevo archivo (si ya existen se pierden sus datos).
“a”: Abre para añadir al final.
“r+”: Abre archivo ya existente para modificar (leer/escribir).
“w+”: Crea un archivo para escribir / leer (si ya existe se pierden los datos).
“a+”: Abre el archivo para modificar (escribir/leer) al final. Si no existe es como w+.
NULL y EOF:
Las funciones de biblioteca de E/S de archivos, generalmente empiezan por f de file, tienen especificado que son de tipo entero de tal forma que si la operación falla devuelven EOF, también devuelven EOF para indicar que se ha leído el fin de archivo. Esta macro está definida en stdio.h.
Ejemplo:
int c:
while ((c=getchar( )) != EOF)
{
…..
}
Cierre de archivos:
Los archivos en C trabajan con una memoria intermedia, buffer. La entrada y salida de datos se almacena en ese buffer, volcándose cuando está lleno. Al terminar la ejecución del programa podrá ocurrir que haya datos en el buffer; si no se volcasen en el archivo este quedaría sin las ultimas actualizaciones. Siempre que se termina de procesar un archivo y termine la ejecución del programa hay que cerrar los archivos abiertos para que, entre otras acciones, se vuelque el buffer.
La función fclose (puntero_file) cierra el archivo asociado al puntero_file y devuelve EOF si ha habido un error al cerrar. El prototipo de la función se encuentra en stdio.h y es:
int fclose(FILE* pf);
Estos son dos vídeos que pueden ayudar a comprender mucho mejor el manejo de archivos.
martes, 25 de noviembre de 2014
Arboles B y B+
En este segmento hablaremos de los arboles B y B+, más que todo de sus operaciones básicas que son la creación la inserción y la eliminación de claves.
Arboles B:
Los arboles B son una generalización de los arboles balanceados, se utilizan como método de búsqueda externa, cada nodo (pagina) en un árbol B de orden d contiene 2d claves como máximo y d claves como mínimo.
Cada página tiene 2d+1 hijos como máximo y d+1 hijos como mínimo, excepto la página RAIZ que puede tener como mínimo una clave y por consiguiente 2 hijos. Ahora vamos a dar un ejemplo de la creación de un árbol B.
Creación e inserción de un árbol B:
Crear un árbol grado 2 insertando las siguientes claves:
10 – 27 – 29 -17 – 25.
El árbol B como es de orden 2 entonces tiene 4 espacios para guardar claves entonces lo tenemos de la siguiente manera.
Ahora vamos a insertar el 10 y quedaría de la siguiente manera.
Insertamos el 27 y quedaría
Ahora insertamos el 29
Y por último insertamos el 17 que quedaría de la siguiente manera.
Lo que buscamos es que quede ordenado de menor a mayor, ahora al ingresar el 25 tendría que quedar en la mitad del 17 y 27 pero como es de orden 2 no pueden haber más de 5 claves por pagina porque su máximo son 4 entonces lo que hacemos es partir el árbol y nos quedaría de la siguiente manera:
Como observamos partimos el árbol B y el 10 y el 17 quedaron a la izquierda del 25 porque son menor que este y el 27 y 29 quedaron a la derecha por ser mayores que el 25.
Ahora insertaremos en un árbol ya creado.
Insertaremos el 90 – 8 – 77.
Empecemos insertando el 90 nos quedaría a la derecha del 52 ya que el 90 es mayor que el 52.
Ahora insertemos el 8, el 8 quedaría a la izquierda del 22 porque el 8 es menor que 22.
Y por último insertemos el 77, al insertar el 77 observamos que tiene que ser entre el 52 y 90 pero ¿cuál es el problema? Que la pagina quedaría de 5 claves y solo se puede de 4 claves porque es de orden 2 si fuera de orden 3 nos quedaría cada página de 6 claves y no tendríamos problema. Entonces para solucionar este problema hay que tener en cuenta el numero que queda en la mitad al insertar el 77 y vemos que es el 52, ahora ya después de haberlo identificado lo que hacemos es subir el 52 a la pagina Raíz y partir la pagina en la que quedo el (39-41-77-90), entonces quedaría de la siguiente manera.
Eliminación en arboles B
Es una operación más complicada, consiste en eliminar o quitar la clave sin violar los principios del árbol B.
-Si la clave a borrar se encuentra en una hoja simplemente se suprime, si no debe bajarse la clave adyacente de la pagina antecedente y sustituir esta clave por la que se encuentra más a la derecha del sub-árbol izquierdo o por la que se encuentra más a la izquierda del sub-árbol derecho.
Ejemplo:
A partir de este árbol B eliminar el 27, entonces como esta en una hoja y la pagina tiene tres claves simplemente se suprime el 27, así quedaría de la siguiente manera:
Ahora eliminemos el 10, si observamos nos damos cuenta de que si lo eliminamos el 13 quedaría solo y estaríamos violando una de las reglas del árbol B entonces lo que hacemos es bajar 15 y unirlo con el (13-17-21) y así no estaríamos violando ninguna regla porque el único que puede quedar con una clave es la página RAIZ con dos hijos, quedaría de la siguiente manera:
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 de claves por nodo, un árbol B+ es una variación de un árbol B.
-Todas las claves se encuentran en las hojas
-Cualquier camino desde la raíz hasta la clave tiene la misma longitud
-Ocupan más espacio que los arboles B porque hay duplicidad de claves
Las operaciones básicas son la búsqueda la inserción y la eliminación.
Búsqueda:
Se comienza con la raíz y llega a las hojas.
Inserción:
Es similar a la inserción del árbol B, cuando se inserta y la página está llena se divide en dos a la izquierda y derecha, una copia de la clave del medio sube a la página antecesora.
Ejemplo:
A partir de este árbol B+ insertar el 13 – 51.
Ahora si vamos a insertar el 13 lo primero que pensamos es que va entre la clave 10 y la 15 pero como pasaba en los arboles B hay que partir la pagina en dos porque no pueden haber 5 claves en una página.
Como la clave 15 es la que queda en el medio esta sube a la raíz pero deja un duplicado en las hojas entonces quedaría de la siguiente manera:
Como dijimos antes el 15 sube pero deja un duplicado en las hojas que es donde está la pagina (15-17-21), y no está rompiendo ninguna regla de los arboles B+.
Ahora vamos a insertar el 51, observamos que al insertarlo queda a la derecha del 31 pero la pagina quedaría de 5 claves y no puede quedar así entonces identificamos quien queda en el medio y seria el 29. Así el 29 sube pero deja un duplicado en las hojas y quedaría de la siguiente forma:
Como se observa el 29 subió y dejo una copia en la hoja y se abrió la pagina, tenga en cuenta que no puede haber un número mayor a la izquierda es decir por ejemplo si el 29 está en la página RAÍZ no puede haber un 40 a la izquierda de él porque estaríamos rompiendo una regla de los arboles B+.
Eliminación del Árbol B+
La eliminación es más simple que en arboles B porque las claves siempre están en las hojas.
Existen dos casos:
*Si al eliminar una clave m queda >=d termina la operación, las claves de la página raíz o internas no se modifican por más que sean copias.
* Si m queda menor que “d” debe realizarse una distribución de claves tanto en el índice como en las páginas hojas. El árbol puede disminuir de altura.
Ejemplo 1:
A partir de este árbol eliminar el 27 – 21.
Empezamos eliminando el 27, ahora deberíamos identificar que si eliminamos el 27 la clave que contiene al 25 quedaría sola por lo que romperíamos una regla de árbol B+, entonces lo que hacemos es subir el 21 y bajar el 25 de la página raíz a la hoja, se puede hacer ya que tenemos una copia en la hoja, así nos quedaría:
Así nos quedó después de haber eliminado el 27. Ahora eliminemos el 21 y lo primero que se viene a la mente es eliminarlo de la hoja pero si nos fijamos bien también está en la página raíz y no podemos subir el 17 porque el 15 quedaría solo pero lo que si podemos hacer es eliminar el 21 y unir el (15,17, 25), entonces nos quedaría:
Esta eliminación es válida porque como se dan cuenta no estamos rompiendo ninguna regla y lo más importante es que al eliminar es como si nos estuviéramos devolviendo es por eso que quedo la raíz con dos hijos, después de haber tenido tres hijos.
Los grafos son estructuras de datos que permiten representar diferentes tipos de relaciones entre objetos, se utilizan en el manejo de redes, en la construcción de circuitos eléctricos, en la estrategia de ventas, economía, cartografía etc.
Grafo Dirigido:
Es un tipo de grafo en el cual las aristas o arcos tienen una dirección definida es decir:
Como pueden observar el arco tiene una dirección o sentido definido.
Adyacencia:
Existe adyacencia entre dos vértices si están unidos por un arco o arista.
- Para el grafo seria:
a y b son adyacentes o viceversa, b y c son adyacentes. a y c son adyacentes o viceversa, c y a son adyacentes. b y d son adyacentes o viceversa, d y b son adyacentes. c y d son adyacentes o viceversa, d y c son adyacentes. Observe que los vértices a y d no están conectados por un arco por lo tanto no son adyacentes, lo mismo pasa con los vértices c y b. - Para el dígrafo: Adyacencia: - Desde
- Hacia
a es adyacente "hacia" b
a es adyacente "desde" c
d es adyacente "desde" b
Si notan el "hacia" lo utilizamos cuando es de un vértice apuntando al otro mientras que el "desde" lo utilizamos cuando del vértice llega un arco.
Incidencia:
Los arcos inciden en los vértices, si una de sus puntas llega a ese vértice.
- Para el grafo seria:
El arco " f " incide en C y D - Para el dígrafo seria:
El arco " f " es incidente en D Grado de un vértice: El grado de un vértice es el numero de arcos que inciden en ese vértice es decir:
El grado del vértice " 1 " es 4 El grado del vértice " 2 " es 4 El grado del vértice " 3 " es 2 El grado del vértice " 4 " es 4 El grado del vértice " 5 " es 2 El grado del vértice " 6 " es 4 El grado del vértice " 7 " es 4 El grado del vértice " 8 " es 2 Tipos de grafos - Componentes conectados separadamente:
Estos grafos pueden tener varios componentes separados es decir, si observan del nodo A al nodo D no puedo pasar directamente sino tengo que pasar por B para poder llegar a D.
-Grafo y dígrafo fuertemente conectado: Grafo
Dígrafo
Para que un grafo y un dígrafo estén fuertemente conectados es empezando desde cualquier vértice poder llegar a los demás.
- Dígrafo débilmente conectado:
Un dígrafo débilmente conectado es cuando se empieza desde cualquier vértice pero no puede llegar a todos los demás vértices es decir:
Si queremos llegar desde el vértice A al vértice E, veremos que no se puede llegar porque no hay ningún arco que apunte al vértice E por lo tanto lo llamamos un dígrafodébilmente conectado.
- Camino simple
si partiendo de un vértice podemos recorrer el grafo sin repetir vértices ni arcos es decir:
Si partimos de A podemos recorrer todos los vértices sin repetir arcos
-Grafo Euleriano:
El grafo euleriano consiste en comenzar desde cualquier vértice y recorrer todos los vértices para llegar de nuevo al punto de partida, pero hay que tener en cuenta de que al recorrer el grafo no se pueden repetir arcos pero si se pueden repetir vértices.
ejemplo:
Como hay que recorrer todo el grafo y terminar en el mismo vértice de partida entonces si empezamos desde el vértice " 1 ", debemos terminar en el mismo vértice entonces quedaría:
1 - 4 - 7 - 8 - 3 - 2 - 4 - 6 - 5 - 1 , como ven recorrimos todos los vértices y llegamos al mismo punto de partida sin repetir arcos.
- Grafo Hamiltoniano:
Si partiendo de cualquier vértice podemos recorrer los vértices sin repetir ninguno y finalmente podemos llegar al vértice origen. Los arcos se pueden recorrer una o mas veces.
Ejemplo:
Si hacemos el recorrido nos quedaria: 1 - 5 - 6 - 7 - 8 - 3 - 2 - 4 - 1 como pueden observar no repetimos ningún vértice. - Grafo regular Es regular si todos los vértices tienen el mismo grado
este es un grafo regular ya que si nos fijamos todos los vértices tienen el mismo grado, su grado es 1. - Grafo cíclico: Un grafo es cíclico si se parte del vértice y llega al mismo vértice hay que tener en cuenta que se presentan en los dígrafos es decir:
- Multigrafo: Es un grafo donde dos vértices están unidos por mas de un arco
- Grafo completo:
Un grafo es completo si cada vértice tiene un grado igual a n-1 donde n es el numero de vértices que componen el grafo
Si nos fijamos bien se cumple la regla ya que el grafo esta compuesto por 4 vértices y su grado es de 3, pero también podemos interpretarlo como: cada vértice se conecta directamente con los demás. En este link encontraras mas tipos de grafos http://docencia.udea.edu.co/regionalizacion/teoriaderedes/tiposu1.html
Lista de adyacencia
Se hace con un arreglo de listas, cada lista almacena los adjuntos a un vértice dado
Es decir:
si dice que tiene que ser las adjuntos a un vértice dado, entonces los adjuntos al vértice A serian B y E. Así hay que hacerlo con todos los vertices del grafo y quedaría representado de la siguiente manera
Donde la primera columna son los vértices que vamos escogiendo para hacer la lista de adyacencia.
Aquí un vídeo donde podrás entender mejor el concepto de lista de adyacencia
Matriz de adyacencia La matriz de adyacencia tiene el mismo objetivo que el de la lista de adyacencia, lo que cambia ahora es que vamos a guardar los vértices adyacentes en una matriz. El tamaño de la matriz la decidimos por el numero de vértices que hay en el grafo, es decir, si el grafo tiene 5 vértices, la matriz sera de 5x5, si el grafo tiene 8 vértices entonces la matriz sera de 8x8.
Ejemplo: Realizaremos la matriz de adyacencia a partir del grafo que utilizamos en la lista de adyacencia.
Entonces si realizamos la matriz de adyacencia quedaría de la siguiente manera
Como ven la matriz es de 6x6 por que el grafo contiene 6 vertices, lo siguiente es colocar 0 y 1 dentro de la matriz, el " 0 " se coloca cuando un vertice no es adyacente a otro.
Es decir por ejemplo del vertice "A" al vertice "C"si se fijan en el grafo no hay un arco que los conecte por lo tanto no son adyacentes, entonces en la matriz se coloca un cero.
Así lo hacemos con los demás vértices. Si hay que colocar un "1" es por que entre dos vértices hay adyacencia como se ve de "A" a "B" o de "A" a "E", y si nos devolvemos y miramos el grafo entre "A" y "B" hay un arco que los une como también hay un arco de "A" a "E". Así lo hacemos con los demásvértices.
Este es un vídeo para una mejor comprensión de la matriz de adyacencia.
Matriz de caminos
La matriz de caminos consiste en saber cuantos caminos de longitud n existen entre un vértice y otro
Donde
n = al numero de arcos que se recorren.
Ejemplo:
¿cuantos caminos hay de "A" a "F" para n=3?
Observamos y nos damos cuenta de que hay 2 caminos los cuales son:
A - B - D - F, y el otro es de A - E - C - F.
Pero para no hacer este proceso tan largo y complicado hacemos la matriz de caminos el cual consiste en multiplicar la matriz de adyacencia.
Hay que tener en cuenta que para multiplicar matrices es "fila x columna" como se multiplica normalmente.
Entonces para saber la matriz de caminos para n=2, solo debemos multiplicar la matriz de adyacencia por ella misma.
Si queremos saber la matriz de caminos para n=3, debemos multiplicar la matriz de adyacencia por la matriz para n=2.
Para entenderlo mejor haremos un ejemplo para n=3 de un digrafo.
Lo primero es crear la matriz de adyacencia entonces nos quedaría:
Ahora multiplicamos la matriz por ella misma para obtener la matriz de caminos para n=2, entonces nos quedaría:
Después de tener la matriz de caminos para n=2, ahora tomamos la matriz adyacente y la multiplicamos por la matriz de caminos para n=2, con esto obtenemos la matriz de caminos para n=3. Entonces al multiplicarla nos quedaría:
Y así obtenemos la matriz de caminos para n=3. Dígrafos fuertemente conectados Un dígrafo esta fuertemente conectado si desde cualquier vértice podemos llegar a todos los demás. Para saber si está fuertemente conectado es necesario hallar la sumatoria de matrices.
S= M + M2 + M3 + M4...+M(NV-1)
Donde NV es : numero de vértices M: las matrices para n=1, n=2 etc... S: la sumatoria de matrices.
Entonces si necesitamos hallar la sumatoria de matrices seria primero conseguir la matriz de adyacencia y después hacer las matrices de caminos hasta n=5, es decir necesitamos hacer 5 matrices, y una sexta que seria la sumatoria de estas 5 matrices. Para hacer un ejemplo vamos a trabajar con el dígrafo anterior y miraremos si es un dígrafo fuertemente conectado, Al hallar la sumatoria de matrices también estamos hallando todos los caminos que hay de un vértice a otro. Ejemplo:
Entonces como ya sabemos lo primero es hallar la matriz de adyacencia que ya la tenemos y es:
Para n=2
Para n=3
Para n=4, en esta matriz hay dos posibilidades de hacerla
Multiplicando la matriz de adyacencia y la matriz de caminos para n=3, con esto nos da la matriz para n=4.
Multiplicando la matriz para n=2 con ella misma para que nos de la matriz de caminos para n=4.
Nos va a dar el mismo resultado con cualquiera de las dos formas entonces al hacerla nos quedaría la matriz:
Para la matriz n=5, también hay dos opciones:
Multiplicar la matriz de adyacencia con la matriz de caminos para n=4, para que así nos de la matriz de caminos para n=5.
Multiplicar la matriz para n=2 con la matriz n=3, para que asi nos de la matriz para n=5.
También nos debe de dar la misma matriz por cualquiera de las dos formas, entonces la matriz para n=5 nos quedaría:
Ahora para hacer la suma de matrices simplemente es tomar las 5 matrices y sumarlas. Se suman como se suma una matriz normal, entonces la sumatoria de matrices nos quedaría:
Si no nos da un cero en la sumatoria de matrices, eso nos quiere decir que el dígrafo está fuertemente conectado. Algoritmos Algoritmo de Warshall "Este escrito fue elaborado por el estudiante Jeisson Gonzalez de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
Es un algoritmo de
análisis sobre grafos para encontrar el camino mínimo entre un par de vértices,
como resultado nos da la mejor ruta para poder llegar al vértice destino en
grafos dirigidos Como resultado nos dará una matriz de clausuratransitiva. Ejemplo:
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 )
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];
}
Algoritmo de Dijkstra
"Este escrito fue elaborado por el estudiante Miguel Gonzalez de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
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]
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. Aqui un vídeo para que puedas comprender mejor el algoritmo de dijkstra
Código para el algoritmo de Dijkstra
#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];
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]);
}
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…
Y en este vídeo dan una explicación del algoritmo de Prim
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;
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]);
}
Algoritmo de Floyd "Este escrito fue elaborado por la estudiante luisa Aponte de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
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:
Matriz de caminos
A
B
C
D
E
A
-
4
4
3
∞
B
3
-
5
∞
∞
C
∞
∞
-
3
2
D
∞
∞
2
-
∞
E
∞
2
∞
∞
-
Fila A y columna A
Matriz de Padres
A
B
C
D
E
A
-
A
A
A
B
B
-
B
C
-
C
C
D
D
-
E
E
-
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.
A
B
C
D
E
A
-
4
4
3
∞
B
3
-
5
6
∞
C
∞
∞
-
3
2
D
∞
∞
2
-
∞
E
∞
2
∞
∞
-
Fila B y columna B
Matriz de padres
A
B
C
D
E
A
-
A
A
A
B
B
-
B
A
C
-
C
C
D
D
-
E
E
-
A
B
C
D
E
A
-
4
4
3
∞
B
3
-
5
6
∞
C
∞
∞
-
3
2
D
∞
∞
2
-
∞
E
5
2
7
8
-
Fila C y columna C
Matriz de padres
A
B
C
D
E
A
-
A
A
A
B
B
-
B
A
C
-
C
C
D
D
-
E
B
E
B
B
-
A
B
C
D
E
A
-
4
4
3
6
B
3
-
5
6
7
C
∞
∞
-
3
2
D
∞
∞
2
-
4
E
5
2
7
8
-
Fila D y columna D
Matriz de padres
A
B
C
D
E
A
-
A
A
A
C
B
B
-
B
A
C
C
-
C
C
D
D
-
C
E
B
E
B
B
-
A
B
C
D
E
A
-
4
4
3
6
B
3
-
5
6
7
C
∞
∞
-
3
2
D
∞
∞
2
-
4
E
5
2
7
8
-
Fila E columna E
Matriz de padres
A
B
C
D
E
A
-
A
A
A
C
B
B
-
B
A
C
C
-
C
C
D
D
-
C
E
B
E
B
B
-
Este sería el resultado final
A
B
C
D
E
A
-
4
4
3
6
B
3
-
5
6
7
C
7
4
-
3
2
D
9
6
2
-
4
E
5
2
7
8
-
A
B
C
D
E
A
-
A
A
A
C
B
B
-
B
A
C
C
E
E
-
C
C
D
E
E
D
-
C
E
B
E
B
B
-
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. Un vídeo para el algoritmo de Floyd
Código para el algoritmo de Floyd
#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;}}
Algoritmo de kruskal
"Este escrito fue elaborado por el estudiante Santiago Rodriguez de la universidad INCCA de Colombia de la facultad de ingeniería de sistemas".
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
Un video para que puedas entender mejor el algoritmo de kruskal
