jueves, 21 de mayo de 2009

Implementacion con matrices




IMPLEMENTACION CON MATRICES


Almacenamiento de Datos
En esta sección se va a tratar las Colecciones, o Estructuras de Datos, que Java aporta para la manipulación y Almacenamiento de Datos e información. Se presentan en primer lugar las Colecciones que están disponibles en la versión 1.1 del JDK, para luego tratar las nuevas Colecciones que se incorporan al lenguaje con el JDK 1.2 y que representan un tremendo avance en la potencia y facilidad de uso de las estruturas de datos orientadas al almacenamiento de información.
Arrays
Mucho de lo que se podría decir de los arrays ya se cuenta en otra sección, aquí sólo interesa el array como almacén de objetos. Hay dos características que diferencian a los arrays de cualquier otro tipo de colección: eficiencia y tipo. El array es la forma más eficiente que Java proporciona para almacenar y acceder a una secuencia de objetos. El array es una simple secuencia lineal, que hace que el acceso a los elementos sea muy rápido, pero el precio que hay que pagar por esta velocidad es que cuando se crea un array su tamaño es fijado y no se puede cambiar a lo largo de la vida del objeto. Se puede sugerir la creación de un array de tamaño determinado y luego, ya en tiempo de ejecución, crear otro más grande, mover todos los objetos al nuevo y borrar el antiguo. Esto es lo que hace la clase Vector, que se verá posteriormente, pero debido a la carga que supone esta flexibilidad, un Vector es menos eficiente que un array, en cuestiones de velocidad.
Colecciones
Cuando se necesitan características más sofisticadas para almacenar objetos, que las que proporciona un simple array, Java pone a disposición del programador las clases colección: Vector, BitSet, Stack y Hashtable.
Entre otras características, las clases colección se redimensionan automáticamente, por lo que se puede colocar en ellas cualquier número de objetos, sin necesidad de tener que ir controlando continuamente en el programa la longitud de la colección.
La gran desventaja del uso de las colecciones en Java es que se pierde la información de tipo cuando se coloca un objeto en una colección. Esto ocurre porque cuando se escribió la colección, el programador de esa colección no tenía ni idea del tipo de datos específicos que se iban a colocar en ella, y teniendo en mente el hacer una herramienta lo más general posible, se hizo que manejase directamente objetos de tipo Object, que es el objeto raíz de todas las clases en Java. La solución es perfecta, excepto por dos razones:
Como la información de tipo se pierde al colocar un objeto en la colección, cualquier tipo de objeto se va a poder colar en ella, es decir, si la colección está destinada a contener animales mamíferos, nada impide que se pueda colar un coche en ella.
Por la misma razón de la pérdida de tipo, la única cosa que sabe la colección es que maneja un Object. Por ello, hay que colocar siempre un moldeo al tipo adecuado antes de utilizar cualquier objeto contenido en una colección.
ejemplo:
import java.util.*;

class Coche {
private int numCoche;
Coche( int i ) {
numCoche = i;
}
void print() {
System.out.println( "Coche #"+numCoche );
}
}

class Barco {
private int numBarco;
Barco( int i ) {
numBarco = i;
}
void print() {
System.out.println( "Barco #"+numBarco );
}
}

public class java411 {
public static void main( String args[] ) {
Vector coches = new Vector();
for( int i=0; i < 7; i++ )
coches.addElement( new Coche( i ) );
// No hay ningun problema en añadir un barco a los coches
coches.addElement( new Barco( 7 ) );
for( int i=0; i < coches.size(); i++ )
(( Coche )coches.elementAt( i ) ).print();
// El barco solamente es detectado en tiempo de ejecucion
}
}

Enumeraciones
En cualquier clase de colección, debe haber una forma de meter cosas y otra de sacarlas; después de todo, la principal finalidad de una colección es almacenar cosas. En un Vector, el método addElement() es la manera en que se colocan objetos dentro de la colección y llamando al método elementAt() es cómo se sacan. Vector es muy flexible, se puede seleccionar cualquier cosa en cualquier momento y seleccionar múltiples elementos utilizando diferentes índices.

Tipos de Colecciones
Con el JDK 1.0 y 1.1 se proporcionaban librerías de colecciones muy básicas, aunque suficientes para la mayoría de los proyectos. En el JDK 1.2 ya se amplía esto y, además, las anteriores colecciones han sufrido un profundo rediseño. A continuación se verán cada una de ellas por separado para dar una idea del potencial que se ha incorporado a Java.
Vector
El Vector es muy simple y fácil de utilizar. Aunque los métodos más habituales en su manipulación son addElement() para insertar elementos en el Vector, elementAt() para recuperarlos y elements() para obtener una Enumeration con el número de elementos del Vector, lo cierto es que hay más métodos, pero no es el momento de relacionarlos todos, así que, al igual que sucede con todas las librerías de Java, se remite al lector a que consulte la documentación electrónica que proporciona Javasoft, para conocer los demás métodos que componen esta clase.
EJEMPLO
import java.util.*;
public class java416 extends Dictionary {
private Vector claves = new Vector();
private Vector valores = new Vector();
public int size() {
return( claves.size() );
}
public boolean isEmpty() {
return( claves.isEmpty() );
}

public Object put( Object clave,Object valor ) {
claves.addElement( clave );
valores.addElement( valor );
return( clave );
}

public Object get( Object clave ) {
int indice = claves.indexOf( clave );
// El metodo indexOf() devuelve -1 si no encuentra la clave que se
// esta buscando
if( indice == -1 )
return( null );
return( valores.elementAt( indice ) );
}

public Object remove(Object clave) {
int indice = claves.indexOf( clave );

if( indice == -1 )
return( null );
claves.removeElementAt( indice );
Object valorRetorno = valores.elementAt( indice );
valores.removeElementAt( indice );
return( valorRetorno );
}

public Enumeration keys() {
return( claves.elements() );
}

public Enumeration elements() {
return( valores.elements() );
}

// Ahora es cuando se prueba el ejemplo
public static void main( String args[] ) {
java416 ej = new java416();
for( char c='a'; c <= 'z'; c++ )
ej.put( String.valueOf( c ),String.valueOf( c ).toUpperCase() );

char[] vocales = { 'a','e','i','o','u' };
for( int i=0; i < vocales.length; i++ )
System.out.println( "Mayusculas: " +
ej.get( String.valueOf( vocales[i] ) ) );
}
}



Funciones de dispersion



FUNCIONES DE DISPERSION



Consiste en la elección de una clave, para el buen funcionamiento de la estructura, debe cumplir las siguientes características:
• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos
• Para dos claves muy similares, generar posiciones distantes.


En primer lugar, obtenemos un numero a partir de la clave alfanumérica utilizada y luego hacemos la operación modulo N sobre ese numero. Así obtendremos una posición donde almacenar nuestro elemento. Hay que cuenta que N (el tamaño de la tabla) ha de ser un número primo.
El código seria:

prívate static int Hash1(String Clave) {

int valor = Clave.charAt(0);

int tam = Clave.length();

for (int i = 1; i <>

valor += Character.getNumericValue( Clave.charAt(i));

}

return (valor % N); }

METODO DE DIVISION


§Es la función de dispersión clásica para claves enteras.
§Consiste en tomar el resto de la división de la clave por el número de entradas de la tabla (B).
§Código: x = x % B;
§Como ventajas citar que es una función fácil de calcular y que se puede utilizar para tablas de cualquier tamaño, aunque se recomienda elegir B con cuidado.
§Como inconvenientes podemos citar que el rango de valores es limitado.

domingo, 17 de mayo de 2009

Metodo d hashing o de dispersion



Metodo d hashing o de dispersion





En informática, Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.
Una función de hash es una
función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.
Es posible que existan claves resultantes iguales para objetos diferentes, ya que el rango de posibles claves es mucho menor que el de posibles objetos a resumir (las claves suelen tener en torno al centenar de bits, pero los ficheros no tienen un tamaño límite).
Son usadas en múltiples aplicaciones, como los
arrays asociativos, criptografía, procesamiento de datos y firmas digitales, entre otros. Una buena función de hash es una que experimenta pocas colisiones en el conjunto esperado de entrada; es decir que se podrán identificar unívocamente las entradas (ver función inyectiva).
Orígenes del término [editar]
El término hash proviene, aparentemente, de la analogía con el significado estándar (en
inglés) de dicha palabra en el mundo real: picar y mezclar. Donald Knuth cree que H. P. Luhn, empleado de IBM, fue el primero en utilizar el concepto en un memorándum datado en enero de 1953. Su utilización masiva no fue hasta después de 10 años.
En el algoritmo
SHA-1, por ejemplo, el conjunto de partida de la función es dividido en palabras que son mezcladas entre sí utilizando funciones matemáticas seleccionadas especialmente. Se hace que el rango de valores que puede devolver la función sea de longitud fija: 160 bits utilizando la adición modular.

Formal
Más formalmente, la función de hash está definida por su dominio (cadenas de
bytes de longitud variable), su imagen (secuencias de bytes de longitud fija) y por la función que relaciona dichos conjuntos (llamada función H). La característica deseada en una función Hash es:
Primer criterio:
Desafortunadamente esta idealización (denominada colisiones de hash) es precisa pero indeterminada. Si el conjunto de valores que puede tomar H(x) es mucho menor que las posibilidades de x, entonces esto no puede ser cierto siempre que todos los valores de x pueden ser igualmente probables. Entonces, existe una segunda condición para hacer la función útil. Por ejemplo:
Segundo criterio (1): dado un H(x) es
complejo encontrar y tal que H(y) = H(x).
Segundo criterio (2): dados x y H(x + s) no es sencillo encontrar s.
En estos ejemplos anteriores, al referirse al grado de dificultad de una tarea se habla siempre en un sentido puramente
computacional. Esto es, que el tiempo necesario para ejecutar dicha tarea sea increíblemente grande (ver NP-C). Además, + puede ser cualquier operación válida sobre el conjunto de partida.
En la práctica, para la mayoría de las aplicaciones sin contar la corrección de errores las funciones hash criptográficas son suficientemente útiles. Los
algoritmos MD5 y SHA-1 son dos de los más populares.

Funciones Resumen
Estos métodos son muy variados, pueden llegar a tomar en cuenta diversos parámetros tales como el nombre de un archivo, su longitud, hora de creación, datos que contenga, etc. aplicándole diversas transformaciones y operaciones matemáticas. Algunas aplicaciones de las funciones resumen son las siguientes:
Identificar algún archivo de computadora independientemente de su nombre o ubicación, lo cual es ampliamente usado en redes
P2P o Peer to peer (intercambio de archivos punto a punto), tales como Kazaa, Ares Galaxy, Overnet, BitTorrent, entre otras.
Corroborar que el archivo no ha cambiado (que algún virus se haya agregado, se haya copiado con errores, se haya transferido mal, se haya cambiado su comportamiento en caso de ser un ejecutable, etc.), un ejemplo de esto es el
algoritmo MD5, el cual es comúnmente empleado para corroborar la integridad de un archivo bajado de internet, usualmente en la misma página que se publica el archivo, se encuentra su hash MD5 para que una vez bajado a nuestra computadora comprobemos que se haya bajado correctamente. Esto es una práctica común dentro del ambiente del software libre, donde después de bajar el archivo se puede comprobar su integridad ejecutando el comando md5sum e indicándole el archivo a analizar.
Identificar un registro en una
base de datos y permitir con ello un acceso más rápido a los registros (incluso más rápido que teniendo índices).

Tablas hash
Artículo principal:
Tabla hash
Las tablas hash, una de las aplicaciones más extendidas de las funciones de hash, aceleran el proceso de búsqueda de un registro de información según una clave (nota: este uso de la palabra poco se relaciona con su significado habitual). Por ejemplo, una cadena alfanumérica puede ser utilizada para buscar la información de un empleado en la base de datos de un sistema.
La utilización de tablas hash provee de un acceso casi directo a dichos registros, lo que significa que, en promedio, una búsqueda puede llegar a requerir sólo uno o dos intentos en la
memoria o el archivo que contiene la información. Naturalmente, se prefiere una buena función de hash que evitará colisiones de hash.
Si asumimos que la clave es una cadena de bytes, entonces la función de hash debería ser como un índice de los registros que tiene una
distribución aleatoria sobre las cadenas de entrada esperadas. De otra forma, habría más colisiones de hash degradando así el tiempo de búsqueda. Si, por ejemplo, la clave es alfabética, cada byte puede tener sólo 26 de sus 256 valores posibles. Funciones tan simples no distribuirán los índices de una forma pareja.
Para una comparación de velocidad y calidad de varias funciones de hash, referirse a los enlaces externos...

Corrección de errores
Para la corrección de errores, se asume una proximidad de la distribución de perturbaciones altamente probables. Las perturbaciones son clasificadas en: errores grandes (improbables) y pequeños (probables). El segundo criterio de las funciones de hash se modifica como sigue: Segundo criterio (3): dados H(x) y x + s, se puede conseguir x si s es lo suficientemente pequeño.
Las funciones que se guían según estos criterios son conocidas como "códigos de corrección de errores". Las derivaciones más importantes de este tipo de códigos de corrección son los chequeos redundancia cíclica y los códigos Reed-Solomon.

Identificación de audio
Para la identificación de audio, como verificar si un archivo
MP3 coincide con alguno de una lista conocida, uno podría utilizar una función hash conocida como MD5. Sin embargo, esto sería extremadamente sensible a perturbaciones extremadamente probables como variación de ritmo, errores de lectura, cambios en el algoritmo de compresión o diferencias en el volumen del sonido. El utilizar MD5 es útil como un primer paso para encontrar archivos idénticos, pero se requiere un algoritmo más sofisticado para encontrar los elementos coincidentes.
Contrariamente a lo que se cree, existen algoritmos robustos para funciones hash con estas características. La mayoría de los que se encuentran disponibles no son extremadamente precisos con respecto a estos cambios, pero algunos son lo suficientemente precisos como para identificar la música que proviene de los altavoces en una sala ruidosa.

Algoritmo Rabin-Karp
Este algoritmo es relativamente rápido para la búsqueda de cadena de caracteres. En promedio, el
tiempo de ejecución es lineal con respecto a la longitud de la entrada. Se basa en la utilización de funciones hash para comparar cadenas.
Un modelo simple (e ineficiente) de función de hash es f(x) = 0 para todo entero x.
Obviamente, la colisión hash en esta función es total. Una un poco más interesante es: f(x) = x mod 1021
Esto es devuelve el resto de la división x entre 1021. Obviamente, la colisión es menor siempre que el conjunto del cual toma valores x no sea muy grande o lo suficientemente aleatorio. Además, nótese que el hecho de que 1021 sea un
número primo no es algo azaroso sino que fue cuidadosamente elegido ya que mecanismos que utilizan este tipo de funciones con números primos como base son muy comunes en criptografía.
1.3.2. HashingLas técnicas de búsqueda basadas en comparaciones, tal como los enfoques secuenciales no son muy eficientes en velocidad y recuperación de información.En ese caso HASHING (también conocido como método de dispersión) es una metodología altamente eficiente para estas operaciones.Hashing consiste en una transformación matemática de una clave k con una función h(k) que da como resultado la posición de k en una tabla (llamado también transformación key-to-address o KAT).El verbo en ingés \'to hash\' significa cortar o mezclar, analógicamente en recuperación de la información hashing significa cortar una parte de la clave y uti.lizarla como base de la búsqueda.La función hash h(k) toma como entrada una clave k y produce como resultado un valor entero distribuído uniformemente en un rango determinado. Este valor se usa como índice para la búsqueda o inserción de un dato en un arreglo llamado también \' tabla de hash \' o también \'tablas dispersas\'.Los elementos del arreglo en los que se almacenan los registros están divididos en \'buckets\' o cajones que contienen un determinado número de \'slots\' o espacios. El número de slots por bucket es llamado tamaño del bucket (bucket size).
Muchos sistemas relacionados con la seguridad informática usan funciones o tablas hash.

Ordenamiento Heapsort

Ordenamiento Heapsort


El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un
montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Descripción

He aquí una descripción en pseudocódigo del algoritmo. Se pueden encontrar descripciones de las operaciones insertar_en_monticulo y extraer_cima_del_monticulo en el artículo sobre montículos.function heapsort(array A[0..n]):
montículo M
integer i := 124578
for i = 0..n:
insertar_en_monticulo(M, A[i])
for i = 0..n:
A[i] = extraer_cima_del_monticulo(M)
return A

Ordenacion por shell

ORDENACION SHELL

El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(nlog2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del
ordenamiento por inserción, teniendo en cuenta dos observaciones:
El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

Ejemplo

Considere un pequeño valor que está inicialmente almacenado en el final del vector. Usando un ordenamiento O(n2) como el ordenamiento de burbuja o el ordenamiento por inserción, tomará aproximadamente n comparaciones e intercambios para mover este valor hacia el otro extremo del vector. El Shell sort primero mueve los valores usando tamaños de espacio gigantes, de manera que un valor pequeño se moverá bastantes posiciones hacia su posición final, con sólo unas pocas comparaciones e intercambios.
Uno puede visualizar el algoritmo Shell sort de la siguiente manera: coloque la lista en una tabla y ordene las columnas (usando un
ordenamiento por inserción). Repita este proceso, cada vez con un número menor de columnas más largas. Al final, la tabla tiene sólo una columna. Mientras que transformar la lista en una tabla hace más fácil visualizarlo, el algoritmo propiamente hace su ordenamiento en contexto (incrementando el índice por el tamaño de paso, esto es usando i += tamaño_de_paso en vez de i++).
Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas. Esto quedaría así:13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una única lista de números, obtenemos [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Aquí, el 10 que estaba en el extremo final, se ha movido hasta el extremo inicial. Esta lista es entonces de nuevo ordenada usando un ordenamiento con un espacio de 3 posiciones, y después un ordenamiento con un espacio de 1 posición (ordenamiento por inserción simple).
El Shell sort lleva este nombre en honor a su inventor,
Donald Shell, que lo publicó en 1959. Algunos libros de texto y referencias antiguas le llaman ordenación "Shell-Metzner" por Marlene Metzner Norton, pero según Metzner, "No tengo nada que ver con el algoritmo de ordenamiento, y mi nombre nunca debe adjuntarse a éste."

Secuencia de espacios

La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por
Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción, se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
Quizás la propiedad más crucial del Shell sort es que los elementos permanecen k-ordenados incluso mientras el espacio disminuye. Se dice que un vector dividido en k subvectores esta k-ordenado si cada uno de esos subvectores esta ordenado en caso de considerarlo aislado. Por ejemplo, si una lista fue 5-ordenada y después 3-ordenada, la lista está ahora no sólo 3-ordenada, sino tanto 5-ordenada como 3-ordenada. Si esto no fuera cierto, el algoritmo desharía el trabajo que había hecho en iteraciones previas, y no conseguiría un tiempo de ejecución tan bajo.
Dependiendo de la elección de la secuencia de espacios, Shell sort tiene un tiempo de ejecución en el peor caso de O(n2) (usando los incrementos de Shell que comienzan con 1/2 del tamaño del vector y se dividen por 2 cada vez), O(n3 / 2) (usando los incrementos de Hibbard de 2k − 1), O(n4 / 3) (usando los incrementos de Sedgewick de 9(4i) − 9(2i) + 1, o 4i + 1 + 3(2i) + 1), o O(nlog2n), y posiblemente mejores tiempos de ejecución no comprobados. La existencia de una implementación O(nlogn) en el peor caso del Shell sort permanece como una pregunta por resolver.

Implementaciones

public static void shellSort(int[] a) {
for ( int increment = a.length / 2;
increment > 0;
increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
for (int i = increment; i <>
for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) {
int temp = a[j];
a[j] = a[j - increment];
a[j - increment] = temp;
}
}
}
}

Ordenacion Binaria

ORDENACION BINARIA



El algoritmo de inserción directa se mejora fácilmente al notar que la secuencia destino aj..ai-1, donde debe insertarse el nuevo elemento, ya está ordenada . Por eso puede ser empleado un método más rápido para determinar el punto de inserción . La elección obvia es una búsqueda binaria que prueba la secuencia destino en la mitad y continúa buscando hasta encontrar el punto
de inserción. El algoritmo de clasificación modificado recibe el nombre de inserción binaria.
PROCEDURE InsercionBinaria;
VAR
i,j,m,L,R:index;
x:item;
BEGIN
FOR i=2 TO n DO
x=a[i];
L:=1;
R:=i;
WHILE Lm:=(L+R) DIV 2;
IF a[m] <=x THEN L:=m+1 ELSE R:=m END
END;
FOR j=i TO R+1 BY -1 DO
a[j]:=a[j-1] (*desplazamiento*)
END;
a[R]:=x(*insercion*)
END
END InserciónBinaria

Carácteristicas fundamentales:
1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el lugar de inserción.
3.-Desplazar elementos.
4.-Insertar.
Análisis:
Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces

Grafos



GRAFO






Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una
red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las
ciencias exactas y las ciencias sociales.


Historia y problema de los puentes de Königsberg


El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible, partiendo de un lugar arbitrario, regresar al lugar de partida cruzando cada puente una sola vez?
Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.
De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez?


Definiciones
Un grafo G es un
par ordenado G = (V,E), donde:
V es un
conjunto de vértices o nodos, y
E es un conjunto de arcos o aristas, que
relacionan estos nodos.
Normalmente V suele ser
finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, V .

Lazos o bucles
Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.


Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos.
Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al
conjunto potencia de V de cardinalidad 2.


Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:

es un conjunto de
pares ordenados de elementos-.
Dada una arista (a,b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.

Pseudografo
Un pseudografo es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos.
Es decir, un pseudografo es un grafo no dirigido que acepta bucles

Pseudografo dirigido
Un pseudografo dirigido es un grafo G = (V,E) donde:

es un conjunto de pares ordenados y etiquetados de elementos de
Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles.

Variantes sobre las definiciones principales
Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces V o E pueden ser un
multiconjunto, pudiendo haber más de una arista entre cada par de vértices. La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

Propiedades
Adyacencia:
dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
Incidencia:
una arista es incidente a un vértice si ésta lo une a otro.
Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del
vendedor viajero o del camino más corto.
Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.


Grafos importantes
Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:
Grafo nulo o vacío: aquel que no tiene vértices ni aristas. Nótese que algunas personas exijen que el conjunto de vértices no sea vacío en la definición de grafo.
Grafo trivial: aquel que tiene un vértice y ninguna arista.
Grafo simple: aquel que no posee
bucles.
Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.
Grafo bipartito completo: sea (W,X) una partición del conjunto de vértices V, es aquel donde cada vértice en W es adyacente sólo a cada vértice en X, y viceversa.
Grafo bipartito: sea (W,X) una partición del conjunto de vértices V, es aquel donde cada arista tiene un vértice en W y otro en X.
Grafo planar o plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas.
Árbol: grafo conexo sin ciclos.
Algunos ejemplos más avanzados son:
Los
grafos de Petersen y sus generalizaciones.
Los
grafos perfectos.
Los
cografos.
Los
grafos de Cayley.
Los
grafos fuertemente regulares y su generalización en grafos de distancia regular.
Una generalización de los grafos son los llamados
hipergrafos.
EJEMPLO:

import adts.*;
import java.util.*;
/**
* Clase que contiene algoritmos de caminos minimos en grafos
*/
public class Caminos
{

/**
* Algoritmo del calculo del camino minimo sin pesos
*/
public static CaminoSinPesos caminoMinimoSinPesos
(Grafo g, int origen, int destino) throws NoExiste,IdIncorrecto
{
// inicializaciones
LinkedList procesar= new LinkedList();
int[] anterior= new int[g.numVertices()];
boolean[] visitado= new boolean[g.numVertices()];
// todas las casillas valen vale false por omision en Java
procesar.addLast(new Integer(origen));
visitado[origen]=true;
anterior[origen]=-1; // para indicar que no tiene
while (!procesar.isEmpty()) {
int v=procesar.removeFirst().intValue();
List> adj=g.listaAristas(v);
for (Arista a:adj) {
int dest=a.destino();
if (!visitado[dest]) {
anterior[dest]=v;
if (dest==destino) {
// hemos encontrado el camino minimo
return caminoDe(origen,destino,anterior,g);
}
visitado[dest]=true;
procesar.addLast(dest);
}
}
}
// el destino no ha sido hallado)
throw new adts.NoExiste();
}
/**
* Metodo para formar el camino sin pesos
*/
private static CaminoSinPesos caminoDe(int origen, int destino,
int[] anterior, Grafo g)
{
CaminoSinPesos cam= new CaminoSinPesos(g);
int v=destino;
while (anterior[v]!=-1) {
cam.inserta(v);
v=anterior[v];
}
cam.inserta(origen);
return cam;
}
/**
* Clase interna para los objetos a almacenar en la cola de
* prioridad en el algoritmo del camino minimo con pesos
*/
static class SubCamino implements Comparable {
int dest;
double peso;
SubCamino (int dest, double peso) {
this.dest=dest;
this.peso=peso;
}
public int compareTo(SubCamino otro) {
if (this.pesoreturn -1;
} else if (this.peso>otro.peso) {
return 1;
} else {
return 0;
}
}
}
/**
* Algoritmo del calculo del camino minimo con pesos
*/
public static CaminoConPesos caminoMinimoConPesos
(Grafo g, int origen, int destino) throws NoExiste, IdIncorrecto
{
// inicializaciones
PriorityQueue procesar= new PriorityQueue();
int[] anterior= new int[g.numVertices()];
double[] peso= new double[g.numVertices()];
boolean[] procesado= new boolean[g.numVertices()];
// valor por omision es false para todas sus casillas
// dar valor infinito a todas las casillas de peso
for (int i=0; ipeso[i]=Double.POSITIVE_INFINITY;
}
procesar.add(new SubCamino(origen,0.0));
peso[origen]=0.0; // para no hacer ciclos
anterior[origen]=-1; // para indicar que no tiene
// bucle para procesar vertices
while (! procesar.isEmpty()) {
int v=procesar.remove().dest;
if (! procesado[v]) {
procesado[v]=true;
List> adj=g.listaAristas(v);
for (Arista a: adj) {
int dest=a.destino();
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
anterior[dest]=v;
peso[dest]=peso[v]+p;
procesar.add(new SubCamino(dest,peso[dest]));
}
} // for
} // if
} // while
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe(origen,destino,anterior,peso[destino],g);
}
}
/**
* Metodo para formar el camino con pesos
*/
private static CaminoConPesos caminoDe(int origen, int destino,
int[] anterior, double peso, Grafo g)
{
CaminoConPesos cam= new CaminoConPesos(g,peso);
int v=destino;
while (anterior[v]!=-1) {
cam.inserta(v);
v=anterior[v];
}
cam.inserta(origen);
return cam;
}
/**
* Algoritmo del calculo del camino minimo con pesos negativos
*/
public static CaminoConPesos caminoMinimoConPesosNegativos
(Grafo g, int origen, int destino)
throws NoExiste, IdIncorrecto, CicloNegativo
{
// inicializaciones
LinkedList procesar= new LinkedList();
int numVertices=g.numVertices();
int[] anterior= new int[numVertices];
double[] peso= new double[numVertices];
int[] visitado= new int[numVertices];
// valor por omision es 0 para todas sus casillas
boolean[] estaEnLaCola= new boolean[numVertices];
// valor por omision es false para todas sus casillas
// dar valor infinito a todas las casillas de peso
for (int i=0; ipeso[i]=Double.POSITIVE_INFINITY;
}
procesar.addLast(new Integer(origen));
peso[origen]=0.0; // para no hacer ciclos
anterior[origen]=-1; // para indicar que no tiene
visitado[origen]++;
// bucle para procesar vertices
while (! procesar.isEmpty()) {
int v=procesar.removeFirst().intValue();
estaEnLaCola[v]=false;
List> adj=g.listaAristas(v);
for (Arista a: adj) {
int dest=a.destino();
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
visitado[dest]++;
if (visitado[dest]>numVertices) {
throw new CicloNegativo();
}
anterior[dest]=v;
peso[dest]=peso[v]+p;
if (!estaEnLaCola[dest]) {
estaEnLaCola[dest]=true;
procesar.addLast(new Integer(dest));
}
}
} // for
} // while
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe(origen,destino,anterior,peso[destino],g);
}
}
/**
* Calcular el grado de entrada, para el orden topologico
*/
private static int[] calculaGradoEntrada(Grafo g) {
try {
int[] grado= new int[g.numVertices()];
// en Java, todas las casillas valen 0 por omision
for (int v=0; vList> ady=g.listaAristas(v);
for (Arista a: ady) {
grado[a.destino()]++;
}
}
return grado;
} catch (IdIncorrecto e) {
System.out.println("Error inesperado "+e);
return null;
}
}
/**
* Mostrar los vertices del grafo en un orden topologico
*/
public static void ordenTopologico(Grafo g) throws HayCiclos
{
try {
int[] grado= calculaGradoEntrada(g);
LinkedList procesar = new LinkedList();
int procesados=0;
// insertar en la cola vertices de grado cero
for (int v=0; vif (grado[v]==0) {
procesar.addLast(new Integer(v));
}
}
// bucle principal
while (!procesar.isEmpty()) {
procesados++;
int v=procesar.removeFirst().intValue();
System.out.print(g.contenido(v)+" ");
// procesar las aristas de v
List> ady=g.listaAristas(v);
for (Arista
a: ady) {
int dest=a.destino();
grado[dest]--;
if (grado[dest]==0) {
procesar.addLast(new Integer(dest));
}
}
}
if (procesados!=g.numVertices()) {
throw new HayCiclos();
}
System.out.println();
} catch (IdIncorrecto e) {
System.out.println("Error inesperado "+e);
}
}
/**
* Calcular el camino minimo en un grafo aciclico
*/
public static CaminoConPesos caminoMinimoAciclico
(Grafo g, int origen, int destino)
throws NoExiste, IdIncorrecto, HayCiclos
{
// inicializaciones
int anterior[]= new int[g.numVertices()];
double[] peso= new double[g.numVertices()];
// dar valor infinito a todas las casillas de peso
for (int i=0; ipeso[i]=Double.POSITIVE_INFINITY;
}
peso[origen]=0.0; // para no hacer ciclos
anterior[origen]=-1; // para indicar que no tiene
int[] grado= calculaGradoEntrada(g);
LinkedList procesar = new LinkedList();
int procesados=0;
// insertar en la cola vertices de grado cero
for (int v=0; vif (grado[v]==0) {
procesar.addLast(new Integer(v));
}
}
// bucle principal
while (!procesar.isEmpty()) {
procesados++;
int v=procesar.removeFirst().intValue();
// procesar las aristas de v
List> ady=g.listaAristas(v);
for (Arista a: ady) {
int dest=a.destino();
grado[dest]--;
if (grado[dest]==0) {
procesar.addLast(new Integer(dest));
}
if (!Double.isInfinite(peso[v])) {
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
anterior[dest]=v;
peso[dest]=peso[v]+p;
}
}
}
}
if (procesados!=g.numVertices()) {
throw new HayCiclos();
}
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe(origen,destino,anterior,peso[destino],g);
}
}
}

import adts.*;
/**
* Prueba del camino minimo con pesos
*/
public class PruebaAciclico
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",4.0);
g.nuevaArista("V2","V5",5.0);
g.nuevaArista("V0","V1",2.0);
g.nuevaArista("V0","V3",1.0);
g.nuevaArista("V2","V3",2.0);
g.nuevaArista("V3","V5",8.0);
g.nuevaArista("V3","V6",4.0);
g.nuevaArista("V3","V4",2.0);
g.nuevaArista("V1","V3",3.0);
g.nuevaArista("V1","V4",10.0);
g.nuevaArista("V4","V6",6.0);
g.nuevaArista("V6","V5",1.0);
OpGrafos.muestra(g);

System.out.println();
try {
Caminos.ordenTopologico(g);
CaminoConPesos cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
} catch (HayCiclos e) {
System.out.println("Se ha lanzado HayCiclos");
}
}
}

import adts.*;
/**
* Prueba del camino minimo con pesos negativos
*/
public class PruebaCaminosConPesosNegativos
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",4.0);
g.nuevaArista("V2","V5",5.0);
g.nuevaArista("V0","V1",1.0);
g.nuevaArista("V0","V3",2.0);
g.nuevaArista("V3","V2",2.0);
g.nuevaArista("V3","V5",8.0);
g.nuevaArista("V3","V6",4.0);
g.nuevaArista("V3","V4",2.0);
g.nuevaArista("V1","V3",3.0);
g.nuevaArista("V1","V4",-10.0);
//g.nuevaArista("V4","V1",-10.0);
g.nuevaArista("V4","V6",6.0);
g.nuevaArista("V6","V5",1.0);
System.out.println();
try {
CaminoConPesos cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
} catch (CicloNegativo e) {
System.out.println("Se ha lanzado CicloNegativo");
}
}
}

import adts.*;
/**
* Write a description of class PruebaCaminos here.
*
* @author (your name)
* @version (a version number or a date)
*/
public class PruebaCaminos
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",1.0);
g.nuevaArista("V2","V5",1.0);
g.nuevaArista("V0","V1",1.0);
g.nuevaArista("V0","V3",1.0);
g.nuevaArista("V3","V2",1.0);
g.nuevaArista("V3","V5",1.0);
g.nuevaArista("V3","V6",1.0);
g.nuevaArista("V3","V4",1.0);
g.nuevaArista("V1","V3",1.0);
g.nuevaArista("V1","V4",1.0);
g.nuevaArista("V4","V6",1.0);
g.nuevaArista("V6","V5",1.0);
System.out.println();
try {
CaminoSinPesos cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
}
}
}

import java.util.*;
import adts.*;
/**
* Write a description of class PruebaGrafos here.
*
* @author (your name)
* @version (a version number or a date)
*/
public class PruebaGrafos
{
public static void main (String args[])
{
Grafo elGrafo = new GrafoAdyacencia();
System.out.println("Creamos un grafo vacio");
System.out.println("El numero de vertices es " + elGrafo.numVertices());
System.out.println("El numero de aristas es " + elGrafo.numVertices());
System.out.println("");
System.out.println("Anadimos 7 vertices y 11 aristas");
elGrafo.nuevaArista(0,1,1);
elGrafo.nuevaArista(0,3,2);
elGrafo.nuevaArista(1,3,3);
elGrafo.nuevaArista(1,4,10);
elGrafo.nuevaArista(2,0,4);
elGrafo.nuevaArista(2,5,5);
elGrafo.nuevaArista(3,2,2);
elGrafo.nuevaArista(3,4,2);
elGrafo.nuevaArista(3,5,8);
elGrafo.nuevaArista(3,6,4);
elGrafo.nuevaArista(4,6,6);
System.out.println("El numero de vertices es " + elGrafo.numVertices());
System.out.println("El numero de aristas es " + elGrafo.numAristas());
System.out.println("");
System.out.println("Recorremos todas las aristas del grafo");
for (int i=0; i<=elGrafo.numVertices()-1; i++)
{
try
{
List> lasAristas = elGrafo.listaAristas(i);
System.out.println("Aristas del vertice "+i+" cuyo contenido es "+elGrafo.contenido(i));
for (Arista a:lasAristas) {
System.out.println(" Origen: "+a.origen()+" Destino: "+a.destino()+" Peso: "+a.contenido());
}
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
}
System.out.println("");
elGrafo.nuevaArista(6,5,1);
System.out.println("Anadimos una nueva arista");
System.out.println("El numero de aristas es " + elGrafo.numAristas());
System.out.println("Recorremos todas las aristas del grafo");
for (int i=0; i<=elGrafo.numVertices()-1; i++)
{
try
{
List> lasAristas = elGrafo.listaAristas(i);
System.out.println("Aristas del vertice "+i+" cuyo contenido es "+elGrafo.contenido(i));
for (Arista a:lasAristas) {
System.out.println(" Origen: "+a.origen()+" Destino: "+a.destino()+" Peso: "+a.contenido());
}
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
}
try
{
System.out.println("El id del vertice con contenido 5 es :");
System.out.println(elGrafo.idVertice(new Integer(5)));
System.out.println("El id del vertice con contenido 9 es :");
System.out.println(elGrafo.idVertice(new Integer(9)));
} catch (NoExiste e) {
System.out.println("El vertice no existe");
}
System.out.println("");
try
{
System.out.println("El contenido del vertice con id 5 es :");
System.out.println(elGrafo.contenido(5));
System.out.println("El id del vertice con id 9 es :");
System.out.println(elGrafo.contenido(9));
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
System.out.println("");
System.out.println("Tratamos de acceder a las aristas de un vertice inexistente");
try
{
List> lasAristas = elGrafo.listaAristas(9);
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
}
}

import java.util.*;
import adts.*;
/**
* Operaciones con los grafos
*/
public class OpGrafos
{
/**
* Mostrar el grafo en pantalla
*/
public static void muestra(Grafo g) {
try {
System.out.println();
System.out.println("------------Grafo---------");
for (int i=0; iSystem.out.print(g.contenido(i)+" - ");
List> lista=g.listaAristas(i);
for (Arista
a:lista) {
System.out.print(g.contenido(a.destino())+"("+
a.contenido()+") ");
}
System.out.println();
}
} catch (IdIncorrecto e) {
System.out.println("Error inesperado: "+e);
}
}
/**
* Calcular el peso de un camino
*/
public static double calculaPeso(V[] camino, Grafo g)
throws NoExiste
{
try {
// Convertir los vértices a identificadores
int[] ruta=new int[camino.length];
for (int i=0; iruta[i]=g.idVertice(camino[i]);
}
// Calcular el peso
double pesoTotal=0;
for (int v=0; vList> ady=g.listaAristas(ruta[v]);
boolean encontrado=false;
// buscar la arista que llega a v+1
for (Arista a:ady) {
if (a.destino()==ruta[v+1]) {
encontrado=true;
pesoTotal=pesoTotal+a.contenido();
break;
}
}
if (!encontrado) {
throw new NoExiste();
}
}
return pesoTotal;
} catch (IdIncorrecto e) {
System.out.println("Error inesperado "+e);
throw new NoExiste();
}
}
}

import adts.*;
/**
* Prueba del camino minimo con pesos
*/
public class PruebaCaminosConPesos
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",4.0);
g.nuevaArista("V2","V5",5.0);
g.nuevaArista("V0","V1",2.0);
g.nuevaArista("V0","V3",2.0);
g.nuevaArista("V3","V2",2.0);
g.nuevaArista("V3","V5",8.0);
g.nuevaArista("V3","V6",4.0);
g.nuevaArista("V3","V4",2.0);
g.nuevaArista("V1","V3",3.0);
g.nuevaArista("V1","V4",10.0);
g.nuevaArista("V4","V6",6.0);
g.nuevaArista("V6","V5",1.0);
OpGrafos.muestra(g);
System.out.println();
try {
CaminoConPesos cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
}
}
}