El 90% de los ejercicios están comprobados.Tipos Abstractos de Datos

Abstracción de datos

Consiste en un objeto y un conjunto de operaciones que lo definen. Estas operaciones son abstracciones procedurales. La abstracción de datos oculta los detalles de la implementación de estos objetos a los que se les llama Tipos Abstractos de Datos.

Abstacción procedural

Consiste en ocultar los detalles de los algoritmos. Acepta un conjunto de entradas y proporciona una visión global desde sus entradas hasta sus salidas, modificando quizás alguna de sus entradas.

Axiomas

Son los métodos que permiten crear el TAD (Ej: Crear) y los que le hacen crecer (Ej: Insertar). La sintaxis de los demás se hace en función de estos.

CONJUNTOS

Un conjunto es una estructura de datos en la cuál éstos NO pueden estar repetidos y, además, están desordenados. Sobre una estructura de tipo conjunto se pueden aplicar todas las operaciones del álgebra de conjuntos (unión, intersección, diferencia). Para extraer un dato del conjunto se realiza de forma aleatoria, es decir, no hay cima, ni frente, etc.

La implementación SET (pascal) o con un ARRAY BOOLEANO sólo almacena tipos enumerados simples, para los complejos debemos usar un TAD basado en un vector de elementos o con una implementación dinámica.

Métodos de la clase

Crear ConjuntoVacio Pertenece (x:datosconjunto)

Insertar (x:datosconjunto) .- No inserta en ningún lugar especial de la estructura

Borrar(x:datosconjunto)

Elegir (var x:datosconjunto).- Devuelve un elemento al azar del conjunto y lo borra del mismo (Comprobar si está vacío antes).

Union (a,b:Conjunto) .- Nos devuelve en la instancia que llama A"B.

Interseccion (a,b:Conjunto) .- Nos devuelve en la instancia que llama A"B.

Diferencia(a,b:Conjunto) .- Nos devuelve en la instancia que llama A-B.

La implementación estática se trata en el tema de Grafos.

Función que cuente el número de elementos de un conjunto.

Función que copìe un conjunto en otro.

Función que compruebe si un conjunto A está incluido en otro B.

Función que compruebe si dos conjuntos son iguales.

LISTAS

Una lista es una estructura de datos en la cuál éstos pueden estar o no ordenados, las inserciones pueden realizarse por el principio, por el final o en orden; los datos de la lista forman una secuencia desde a1 hasta an y podemos clasificarlos de diferentes formas:

• Según su ordenación:

Listas no ordenadas.- Inserciones por el principio o el final y los datos pueden estar repetidos.

Listas ordenadas.- Inserciones en orden y no puede haber datos repetidos normalmente.

• Según la estructura de la lista:

Listas simples.- Son las listas enlazadas normalmente.

Listas doblemente enlazadas.

Listas circulares

Listas circulares doblemente enlazadas.

Listas Enlazadas

Cada nodo de la lista tiene dos campos: dato y suce. Existe un puntero que apunta al primer elemento de la lista.

Métodos de la clase

Crear ListaVacia Primero (x:datoslista)

InsLista (x:datoslista) .- Inserta al principio de la lista.

SupLista (x:datoslista)

Resto (var L: lista).- Se usa para recorrer la lista pero sin hacer inserciones ni borrados

Modificar (x: datoslista) .- Cambia el valor del dato al principio de la lista.

A estos métodos se les puede añadir InsFinal e InsOrden.

Función que cuente el número de elementos de una lista.

Función Pertenece.

Procedimiento que reemplace un elemento A por otro B.

Procedimiento InsFinal como si fuera un método del objeto.

Dadas dos listas L1 y L2 ordenadas obtener una nueva lista ordenada L3 con los elementos de L1 y L2.

Procedimiento que mezcle n listas ordenadas, usaremos el ejercicio anterior; las n listas vendrán por parámetro en una lista de listas.

Listas Circulares

En este tipo de lista el sucesor del último elemento es el primero de la lista.

Método de inserción: Se inserta siempre en el segundo lugar de la lista.

Para el borrado hay que tener en cuenta los siguientes casos:

• Si el elemento a borrar es el único que hay en la lista.

• Si el elemento a borrar es el primero de la lista.

• Si el elemento a borrar es cualquier otro.

Listas Doblemente Enlazadas

Cada nodo tiene dos punteros, uno al nodo sucesor y otro al antecesor, y un campo dato. El objeto lista doblemente enlazada tiene dos atributos E_Lista1 y E_Lista2 que apuntan al primer y último elemento respectivamente.

Consideraciones en la inserción.- Tipos de inserción.

• Por el principio.- Casos a tener en cuenta:

Lista Vacía.

Lista No Vacía.

• Por el final.- Casos a tener en cuenta:

Lista Vacía.

Lista No Vacía.

• En Orden.- Casos a tener en cuenta:

Lista Vacía.- Actualizar E_Lista1 y E_Lista2.

El elemento a insertar es el primero.- Actualizar E_Lista1.

El elemento a insertar es el último.- Actualizar E_Lista2.

El elemento a insertar está en cualquier otra posición.

Consideraciones en el borrado.

• El elemento a borrar es el único que hay en la lista.- Actualizar E_Lista1 y E_Lista2.

• El elemento a borrar es el primero de la lista.- Actualizar E_Lista1.

• El elemento a borrar es el último de la lista.- Actualizar E_Lista2.

• El elemento a borrar es cualquier otro.

Listas Circulares Doblemente Enlazadas

1. Implementar la operación SupLista de una lista circular.

2. Implementar la operación SupLista de una lista doblemente enlazada.

RECURSIVIDAD

Divide y Vencerás.

Término General:

Donde T(n) es el problema de tamaño n. Lo divido en a problemas, de tamaño n/b, y el tiempo que tardo en combinar las soluciones parciales es cnk. a,b,c,k son constantes.

Backtracking.

Los algoritmos de backtracking son algoritmos recursivos que prueban todos los posibles casos de un problema hasta encontrar la solución. Estos algoritmos aseguran que si existe una solución se va a encontrar.

Dada una solución parcial los algoritmos de backtracking la van a ir aumentando hasta encontrar la solución general; en este tipo de algoritmo según avanza la recursión cuando se llega a un punto a partir del cuál no se puede ampliar y no estamos en solución general, el algoritmo retrocede a la anterior solución parcial e intenta ampliar de nuevo ésta.

Los algoritmos de backtracking son bastante ineficientes aunque tienen la ventaja de que si la solución existe, siempre la encuentran.

Los esquemas en Fotocopias.

Diseñar una función que sume un 1 a un número binario que viene almacenado en una lista donde el primer elemento es el bit menos significativo.

Función que indique si una pila P es sombrero de una pila Q. Una pila es sombrero de otra cuando tiene los mismos elementos dispuestos en el mismo orden.

Dada una lista, procedimiento que inserte un elemento al final.

Procedimiento recursivo que borre todos los elementos repetidos que haya en una lista.

Procedimiento que liste de forma inversa los elementos de una cola.

Dada una lista de Pilas recorrer dicha estructura.

Backtracking

Ejercicio 9 de la hoja. Dada una matriz como la anterior y que es la representación de un laberinto diseñar una función que nos saque de él. La función recibe las coordenadas de inicio y las de la solución.

Ejercicio 10 de la Hoja. Diseñar una función que dado un tablero de NxN y una posición inicial, lo recorra entero y sin pasar más de una vez por la misma casilla con el movimiento de la figura de ajedrez.

ÁRBOLES

Un árbol es una estructura de datos jerárquica formada por unos elementos que llamaremos nodos y que podemos definir de forma recursiva: A es un árbol vacío si no tiene ningún nodo o bien A tiene un nodo llamado raíz que contiene n subárboles.

El subárbol del cuál parten todos los descendientes se denomina raíz. Un nodo cuyos descendientes sean vacíos se denomina hoja. En este subárbol se dice que A es padre de B y E, y que B y E son hijos de A y hermanos entre sí.

Se llama grado de un árbol al número de subárboles que tiene, el grado de un árbol es el máximo de los grados de cualquiera de sus nodos. Un árbol es n-ario si cada nodo tiene como máximo grado n.

Cada nodo del árbol tiene asociado un número de nivel de forma que el nodo raíz siempre tiene nivel 1, y al resto de nodos se le asigna un número de nivel más que el nodo padre.

Se llama profundidad o altura de un árbol al máximo nivel asignado a cualquiera de sus nodos.

El máximo número de nodos del nivel i-ésimo de un árbol de grado n es ni-1. Para un árbol binario es 2i-1. El número máximo de nodos de un árbol binario de profundidad k es 2k-1.

Un árbol completo es aquél que tiene el número máximo de nodos que podría tener dado su grado y su profundidad. Un árbol binario está equilibrado si para cada uno de sus nodos las alturas de sus dos subárboles difieren como mucho en 1.

Árboles Binarios

En un árbol binario cada nodo está compuesto por un campo raíz - de tipo datosarbol - y dos punteros, uno al subárbol izquierdo y otro al subárbol derecho. Podemos distinguir entre Árboles Binarios Ordenados y Árboles Binarios No Ordenados.

Árboles Binarios Ordenados

En un árbol binario ordenado, para cada nodo los datos menores que su raíz están en el subárbol izquierdo y los mayores en el subárbol derecho.

En un ABO las búsquedas proporcionan en su mejor caso - cota inferior - (log n); esto se da cuando el árbol está equilibrado ya que en la búsqueda, cada vez que descendemos en un nivel, nos olvidamos de la mitad del subárbol. El peor caso - cota superior - nos proporciona O(n); esto se da cuando el árbol se encuentra balanceado hacia el subárbol derecho, hacia el izquierdo o bien cuando cada nodo, que no sea una hoja, tiene un subárbol vacío.

Inserción en un Árbol Binario Ordenado

Se realiza buscando un subárbol vacío. Se comienza en la raíz decidiendo si el dato a insertar es mayor o menor que ésta, realizando sucesivas llamadas al subárbol en el cual debe encontrarse el hueco para insertar el dato. Cuando se encuentra el árbol vacío se inserta el nuevo elemento; de esta forma los ABO crecen desde la raíz a las hojas.

Normalmente los datos no están duplicados, aunque puede darse. En este caso según la implementación del árbol el dato repetido estará en el subárbol izquierdo o en el derecho según si usamos la comparación <= ó >=. La inserción es recursiva.

Para equilibrar un árbol se vuelcan los nodos a una lista ordenada y recursivamente se inserta el elemento central de cada una de las sublistas resultantes.

Borrado en un Árbol Binario Ordenado

Esta función elimina un dato de un árbol reconstruyéndolo para que quede ordenado de nuevo. Hay 3 casos:

El elemento a borrar tiene el hijo derecho vacío.- El padre del elemento a borrar apuntará al subárbol izquierdo de dicho elemento y éste se borra.

El elemento a borrar tiene el hijo izquierdo vacío.- El padre del elemento a borrar apuntará al subárbol derecho de dicho elemento y éste se borra.

El elemento a borrar tiene dos hijos no vacíos.- Se selecciona del subárbol izquierdo el mayor de los elementos; éste se sube a la raíz y se elimina el elemento seleccionado usando el mecanismo del caso 1.

Métodos del TAD ABO

• Crear

• Vacio

• Insertar (x:datosarbol) {En Orden}

• Raíz (VAR x:datosarbol)

• HijoDer (VAR D:Arbol)

• HijoIzq (VAR I:Arbol)

• Borrar (x:datosarbol)

Ejemplo:

Function Pertenece (A:Arbol; x:DatosArbol): boolean;

VAR Iz,De:Arbol; y:DatosArbol;

BEGIN

IF A.Vacio THEN Pertenece:=FALSE

ELSE

Begin

A.Raiz(y);

IF x=y THEN Pertenece:=TRUE

ELSE IF x>y THEN Begin

A.HijoDer(De);

Pertenece:=Pertenece(De);

End

ELSE Begin

A.HijoIzq(Iz);

Pertenece:=Pertenece(Iz);

End;

End;

END;

Diseñar una función que dado un árbol cuente el número de nodos.

Diseñar una función que dado un árbol cuente el número de nodos cuya raíz es par.

Diseñar una función que dado un árbol sume los nodos cuya raíz es impar.

Diseñar una función que dado un árbol sume sus nodos.

Dado un árbol comprobar si se trata de una hoja.

Dado un árbol contar el número de hojas.

Función que diga si un árbol es degenerado o no. Es Degenerado si para todos sus nodos sólo tienen un hijo o ninguno.

Función que calcule la Profundidad de un árbol.

Función que diga si un árbol es equilibrado o no.

Función que cuente el número de hijos izquierdos.

Función que cuente el número de enlaces vacíos.

Dado un árbol y un dato implementar una función que liste los descendientes de un dato.

Implementar una función que cuente el número de nodos de un nivel.

Implementar una función que cuente el número de nodos que hay por debajo de un nivel.

Implementar una función que cuente el número de nodos que hay entre dos niveles.

Implementar una función que nos diga si dos árboles son iguales.

Implementar una función que copie un árbol en otro.

Procedimiento que dado un árbol y un dato devuelva el árbol que apunte a dicho dato.

Procedimiento que dado un árbol y un dato devuelva 2 árboles, uno apuntando al dato y otro al padre del dato.

Hacer una función que dado un árbol y dos datos x e y nos diga si X es padre de Y.

Procedimiento que liste los nodos indicando el nivel en que está cada nodo.

Función que diga si un árbol es completo o no.

Procedimiento que liste los nodos por nivel de abajo a arriba.

Recorridos sobre un árbol

En Profundidad

Buscan los nodos del máximo nivel. Hay 3 casos:

• InOrden: Se usa para hacer recorridos En Orden sobre los datos de un árbol. Si hacemos la siguiente secuencia de llamadas:

InOrden(iz);WRITE(x); InOrden(de)

Recorremos el árbol de menor a mayor, en el siguiente caso el recorrido sería de mayor a menor: InOrden(de);WRITE(x); InOrden(iz);

• PreOrden: Se usa para pasar información desde los nodos de niveles superiores a los nodos de niveles inferiores. Procesado:

WRITE(x);PreOrden(iz); PreOrden(de)

• PostOrden: Se usa para devolver información desde los nodos de niveles inferiores a los nodos de niveles superiores. Procesado:

PostOrden(iz); PostOrden(de); WRITE(x);

En Anchura

Búsqueda por niveles; se procesan todos los nodos del nivel i antes de pasar a los que está en el nivel i+1.

Árboles Binarios No Ordenados

Los Árboles Binarios No Ordenados no mantienen ninguna relación entre los nodos insertados. Se construyen desde las hojas hacia la raíz, en este tipo de árboles pueden existir elementos repetidos.

Búsqueda en un Árbol Binario No Ordenado

Se realiza una búsqueda por las dos ramas del árbol ya que, debido a la ausencia de orden, el dato buscado puede estar en cualquiera de los dos subárboles o no estar.

Inserción en un Árbol Binario Ordenado

Se utiliza el método construir que crea un nuevo nodo con el dato a insertar y dos subárboles vacíos. Ello permite construir el árbol desde las hojas a la raíz.

Borrado en un Árbol Binario Ordenado

Se borra todo el árbol.

Diseñar la función Pertenece de un ABNO.

Diseñar una función que copie un ABNO en otro.

Árboles Generales

Un árbol general es aquel cuyo grado es mayor que dos, es decir, cada nodo tiene n subárboles donde n es el grado de un árbol.

Representación de una árbol general mediante un árbol binario.

Se establece la relación siguiente entre padres e hijos: como hijo izquierdo del AB de un nodo se toma el hijo más a la izquierda de dicho nodo en el AG, y como hijo derecho en el AB se toma su hermano de la derecha en el AG.

Ejercicio de examen. Sea A un ABO que representa un AG, se pide construir un procedimiento itrerativo que imprima toda la jerarquí del árbol por niveles.

Ejercicio de examen. Modificar el anterior para obtener el grado de un AG.

Ejercicio de examen. Implementar la función etiquetar que dado un ABO nos devuelva la etiqueta que corresponde a la raíz del árbol, teniendo en cuenta que las hojas tienen como etiqueta la suma de los antecesores y los que no son hojas tiene como etiqueta la suma de las etiquetas de sus sucesores.

Ejercicio de examen. En Inteligencia Artificial existe un algoritmo que propaga la información hacia arriba en un árbol binario equilibrado de la siguiente forma:

• Si estamos en una hoja, se propaga el valor que devuelve una cierta función heurísitca H.

• Si estamos en nodos situados en niveles impares, se propaga el máximo valor de sus nodos inmediatamente sucesores.

• Si estamos en nodos situados en niveles pares se propaga el mínimo valor de sus nodos inmediatamente sucesores.

Se pide: Haciendo uso de P.O.O., construir una función que implemente este algoritmo y devuelva el valor que se ha propagado hasta la ráiz de un cierto árbol. El prototipo debe ser:

Function MinMax (A:Arbol; Nivel:Intege): Integer;

NOTA: Se puede hacer uso de las siguientes funciones sin necesidad de implementarlas (siempre que se respete su sintaxis).

Function H(A:Arbol):integer; {Devuelve el valor con que se etiqueta la hoja A}

Function Maximo (a,b:integer):integer; {Devuelve el máximo de a y b}

Function Minimo (a,b:integer):integer; {Devuelve el mínimo de a y b}

Function Impar (a:integer):Boolean; {Devuelve true si a es impar}

Ejemplo:

La llamada MinMax (A,1) para el caso del ejemplo devolverá H.

Ejercicio de examen (6-1998). Hemos estudiado dos formas generales de hacer recorridos sobre árboles. Existen otro tipo de recorridos que no siguen ninguno de esos esquemas. Concretamente, un algoritmo que llamaremos recorrido_guiado, permite realizar un recorrido sobre un árbol de forma que, en cada iteración, se selecciona el nodo más pequeño de entre todos los disponibles en ese momento, independientemente de en qué rama se encuentre. Se entiende por nodo disponible aquel nodo cuyo padre ya ha sido procesado (excluyendo el nodo raíz). Además, este tipo de algoritmos optimiza el tiempo de proceso, de forma que, cuando un árbol tiene nodos repetidos, y se llega a un nodo igual que uno anteriormente visitado, este último se ignora sin más.

Suponer además que tenemos implementada una clase COLA cuya operación de inserción coloca los datos en la cola ordenados de menor a mayor.

SE PIDE: Usando técnicas de POO en Borland Pascal, implementar una función que, dado un árbol binario, y empleando el algoritmo descrito anteriormente, realice un recorrido guirado por el árbol, mostrando en pantalla el contenido de cada nodo. El prototipo de la función será:

Procedure Recorrido_Guiado (A:Arbol);

NOTA: Los nodos del árbol se deben procesar una sola vez.

Ejemplo de recorrido:

Para este árbol, el procedimiento recorrido_guiado debe mostrar en pantalla: 20, 4, 3, 1, 7, 6, 8, 9

Ejercicio de examen (9-1998). Un árbol Rojo-Negro coloreado (se añade un nuevo campo en cada nodo del árbol que indica su color) en el que todo nodo está coloreado de rojo o negro, y en el que la disposición de los nodos obredece las siguientes restricciones.

• (Regla del Negro): Toda hoja está coloreada de Negro.

• (Regla del Rojo): El número de nodos rojos del subárbol izquierdo y del subárbol derecho del nodo raíz difiere como mucho en 1.

Se pide: Usando técnicas de POO en Borland Pascal, implementar una función que, dado un árbol binario DECIDA si se trata de un árbol Rojo-Negro.

GRAFOS

Un grafo es una estructura de datos formada por un conjunto V de vértices y un conjunto E de pares de vértices llamados arcos, V(G) y E(G) respectivamente.

Un grafo es dirigido si para el par de vértices v1 y v2, que representa a cualquier arco, es ordenado. Los arcos se representan con flechas.

Un grafo es no dirigido si para el par de vértices v1 y v2, que representa a cualquier arco, no es ordenado. Los arcos se representan con aristas.

Un grafo sólo puede ser dirigido o no dirigido, no puede haber mezclas.

En un grafo no pueden aparecer arcos recursivos (bucles o lazos). Como E(G) es un conjunto, el par v1 y v2 sólo puede aparecer una sola vez, es decir, en un grafo no puede haber arcos repetidos. Si esto ocurre se llama multigrafo.

El número máximo de nodos de un grafo no dirigido de n vértices es n(n-1)/2. Si un grafo no dirigido tiene este número de vértices se dice que es completo.

El número máximo de nodos de un grafo dirigido de n vértices es n(n-1). Si un grafo dirigido tiene este número de vértices se dice que es completo.

Si v1 y v2 es un arco de E(G) siendo G un grafo no dirigido, se dice que los vértices v1 y v2 son adyacentes, y que el arco < v1, v2> es incidente en los vértices v1 y v2. Por tanto, para cada vértice podemos obtener su conjunto de adyacentes.

Si el grafo es dirigido se dice que v1 es adyacente a v2, mientras que v2 es adyacente desde v1. Para cada vértice podemos distinguir dos conjuntos de adyacentes por la izquierda y por la derecha.

Adyacentes por la derecha de un vértice v1 son aquellos vértices a los que llegan arcos que parten de v1. Adyacentes por la izquierda de un vértice v1 son aquellos vértices de los que parten arcos que llegan a v1. Si sólo se habla de adyacentes , nos estamos refiriendo al conjunto de vértices de adyacentes por la derecha.

Se llama camino desde el vértice vi a vj en un grafo G a la secuencia de vértices vi, vk1, vk2,..., vkn, vj tales que (vi, vk1) (vk1, vk2) ... (vkn, vj) son arcos de E(G). La longitud de un camino es el número de arcos que lo forman.

Un camino simple es un camino en el que todos los vértices son distintos excepto un caso especial en el que el primero y el último son iguales. Si el grafo es dirigido se denomina camino dirigido simple.

Un ciclo es un camino en el que el primer y el último vértice coinciden. Por convenio, para que exista ciclo en un grafo no dirigido deben formar parte de él al menos tres vértices; si es un grafo dirigido el número mínimo de vértices para formar un ciclo es de dos.

En un grafo F no dirigido se dice que dos vértices vi, vj están conectados si existe un camino desde vi a vj, dado que el grafo es no dirigido también hay camino desde vj a vi.

Un grafo G es conexo si para cada par de vértices vi, vj distintos, existe un camino desde vi a vj, es decir, todos los vértices están conectados entre sí.

Un grafo G dirigido es fuertemente conexo si para cada par de vértices vi, vj distintos, existe un camino desde vi a vj y viceversa.

Un subgrafo G1 de un grafo G es máximo si no existe ningún subgrafo de G que lo contenga.

Un subgrafo G1 de un grafo G es mínimo si no existe ningún subgrafo de G distinto del vacío que esté incluido en G1.

Una componente conexa de un grafo no dirigido es un subgrafo conexo máximo.

Una componente fuertemente conexa de un grafo dirigido es un subgrafo máximo que es fuertemente conexo.

El grado de un vértice es el número de arcos que inciden en él.

Para grafos dirigidos tenemos grado de entrada de un vértice, que es el número de arcos que llegan a él, y grado de salida, que es el número de arcos que salen de él. Por tanto, el grado de un vértice es la suma de ambos.

El grado de un grafo es el máximo grado de cualquiera de sus vértices.

Posibles implementaciones

• Matriz de adyacencia.

El conjunto de arcos del grafo es una matriz cuadrada de MaxVert x MaxVert. Cada celda representa la existencia o no de un determinado arco.

El conjunto de vértices se representa mediante un conjunto, que se representa mediante un vector booleano de uno a MaxVert de tal forma que cada celda indica si un determinado vértice existe o no.

Arcos en la matriz de adyacencia: Si el grafo es dirigido se marca a TRUE la celda correspondiente origen(fila)-destino(columna) si existe el arco o FALSE en caso contrario.

Si el grafo es no dirigido la existencia de un determinado arco se establece marcando a TRUE las casillas origen-destino y destino-origen en la matriz.

Si el grafo es valuado cada arco lleva asociado un peso, en vez de usar una matriz booleana, se usa una matriz de números, de tal forma que si un determinado arco existe se marca en la matriz con su peso, si no existe el arco se marca con un número negativo (si no pueden existir pesos negativos) o con un valor muy alto al que nunca llegan los pesos.

Si el grafo es no dirigido y valuado se marca con el mismo valor la celda origen-destino y destino-origen.

Ventajas. Operaciones sobre matriz muy rápidas y fáciles de implementar.

Desventajas. Limitación del número de vértices y desperdicio de memoria.

• Dos conjuntos.

Un conjunto para vértices y otro para los arcos del grafo. Para cada arco se almacena el par de vértices origen-destino. Si el grafo es valuado, a cada arco se le añade el campo peso.

Ventajas. Si disponemos del TAD conjunto la implementación es rápida y sencilla.

Desventajas. Hay que implementar dos TAD conjunto.

• Lista de listas.

Existe una lista principal que son los vértices del grafo y cada uno de ellos contiene una lista con los vértices adyacentes. De la misma forma si el grafo fuese no dirigido.

Si el grafo es valuado cada nodo adyacente almacena también el peso del arco.

Ventajas. No hay limitación del número de vértices.

Desventajas. Complejidad alta a la hora de trabajar con el grafo.

Recorridos sobre un grafo

Dado un vértice de partida, los recorridos sobre un grafo visitan aquellos vértices que son accesibles de el primero, es decir, que normalmente no recorren todos los vértices del grafo.

En Profundidad

• Se visita el vértice v de partida.

• Se selecciona un vértice w adyacente a v que aún no haya sido visitado.

• Se realiza el recorrido en Profundidad partiendo de w.

• Cuando se encuentra un vértice cuyo conjunto de adyacentes ha sido visitado en su totalidad se retrocede hasta el último vértice que tenga adyacentes no visitados y se va al segundo punto.

Este recorrido sigue un esquema backtracking.

En Anchura

Primero se visita el vértice de partida v, después se visitan todos los vértices adyacentes a v antes de visitar cualquier otro vértice, en este tipo de recorrido sólo se visitan los vértices accesibles desde v, se trata de un recorrido iterativo y se usa una cola para almacenar los vértices que quedan por procesar y no perder el orden de aparición de los mismos.

Dado un grafo, implementar una función que compruebe si es Conexo.

Dado un grafo y dos vértices v,w distintos entre sí, implementar una función que indique si hay camino de v a w. Usar un recorrido.

Modificar el algoritmo de recorrido en profundidad para que tenga de entrada dos vértices en lugar de uno y devuelva un valor booleano indicando si están conectados.

Procedimiento que escriba las componentes conexas de un grafo.

Dado un vértice v y un grafo G, procedimiento que escriba todos los vértices a distancia 1, 2, 3,.. hasta acabar el grafo.

Sumidero es un vértice del que no sale ningún arco y llega, al menos, uno. Implementar una función que dado un grafo y un vértice diga si el vértice es un sumidero.

Un grafo dirigido es balanceado si cada vértice tiene el mismo grado de entrada y de salida. Hacer una función que diga si un grafo es o no balanceado. (Ejercicio del examen del 2-93. Increíble)

Dado un grafo y un vértice, implementar una función que diga si existe ciclo asociado a dicho vértice (Examen Junio 89. Pffffff!).

Dado un grafo, comprobar si existe algún ciclo en él.

Un grafo es separable si sólo tiene un único vértice que al eliminarlo deja de ser conexo. A) Implementar una función que dé el grado de separabilidad B) Implementar una función que diga si un grafo es separable.

Sea G un grafo conexo no dirigido, se dice que el arco (i,j) perteneciente al conjunto de arcos de G es puente si al eliminarlo G deja de ser conexo. Implementar un procedimiento que liste los puentes de un grafo G.

Función que cuente el número de componentes conexas de un grafo.

Cierre Transitivo

Dado un grafo descrito por su Matriz de Adyacencia, la expresión lógica Ady[i,k] AND Ady[k,j] es TRUE si hay un camino de longitud 2 desde i hasta j pasando por k. La expresión (Ady[i,1] AND Ady[1,j]) OR (Ady[i,2] AND Ady[2,j]) OR ... (Ady[i,n] AND Ady[n,j]) será TRUE si existe cualquier camino de longitud 2, para ir desde i a j.

Si aplicamos esta expresión a cada par de vértices i,j de la matriz de adyacencia obtenemos una nueva matriz Ady2 que representa a la matriz de caminos de longitud 2 (¡Sólo los de longitud 2!), para obtener esta matriz basta con realizar el protocolo booleano de Ady x Ady. Para obtener Ady3, haríamos Ady x Ady2.

En general, para obtener Adyk, multiplicamos Adjk-1 x Ady.

Vamos a obtener si hay caminos de longitud k o no. Si queremos saber si existe un camino de longitud 2 o menor entre los nodos i, j de un grafo G hay que comprobar si existe bien un camino de longitud 1 o bien un camino de longitud 2. Si esta longitud operación la realizamos para cada par de vértices obtendremos una nueva matriz en la que están representados todos los caminos de longitud 2 o menor.

Si quiero calcular una matriz con todos los caminos de longitud menor o igual que 3 tendré que ver la expresión ady OR ady2 OR ady3. En general, si quiero calcular la matriz con todos los caminos de longitud k o menor haremos ady OR ady2 OR ady3 OR ... OR adyk. A esta matriz se le denomina cierre transitivo. Si es toda TRUE el grafo es conexo o fuertemente conexo según si es no dirigido o dirigido respectivamente.

Dado un grafo G comprobar si es conexo usando el cierre transitivo.

Dado un grafo G implementar un procedimiento que liste todos los caminos de longitud menor o igual que 5.

Dado un grafo G implementar un procedimiento que liste todos los caminos de longitud 4.

Algoritmo de Warshall

Este algoritmo obtiene una matrizen la que se indica si hay un camino o no entre el par de vértices i y j. Supongamos un grafo G donde los nodos están numerados de 1 a n, queremos calcular la matriz C de tal forma que C[i,j] es TRUE si hay camino de i a j, y FALSE en caso contrario.

Se define Ck[i,j]= TRUE si hay un camino de i a j que pasa por nodos intermedios etiquetados con un valor menor o igual a k. Por definición, C0[i,j] = Ady[i,j] (caminos entre i y j sin pasar por ningún nodo).

• Si Ck-1[i,j] es TRUE entonces Ck[i,j] también es TRUE.

• Si Ck[i,j] = TRUE y Ck-1[i,j] = FALSE entonces el camino desde i hsta j pasa forzosamente por el nodo k, es decir, (Ck-1[i,k] AND Ck-1[k,j]) = TRUE.

C3[1,4] = TRUE

C2[1,4]= FALSE

C2[1,3] AND C2[3,4]

• Para actualizar Ck se aplica lo siguiente:

Ck[i,j] = Ck-1[i,j] OR (Ck-1[i,k] AND Ck-1[k,j])

• La matriz final C se corresponde con Cn.

Ejemplo.

Descargar

Ady			K=1			K=2			K=3
			C1			C2			C3
0	1	0	0	1	0	0	1	1	1	1

Enviado por:	Mv
Idioma:	castellano
País:	España