Tomado de Joyanes Aguilar Luis Estructuras de datos en Java

Tomado De Joyanes Aguilar Luis Estructuras De Datos En Java-Free PDF

  • Date:02 Mar 2020
  • Views:79
  • Downloads:0
  • Pages:15
  • Size:625.00 KB

Share Pdf : Tomado De Joyanes Aguilar Luis Estructuras De Datos En Java

Download and Preview : Tomado De Joyanes Aguilar Luis Estructuras De Datos En Java


Report CopyRight/DMCA Form For : Tomado De Joyanes Aguilar Luis Estructuras De Datos En Java


Transcription:

Los grafos se estudian como estructuras de datos o tipos. abstractos de datos, Un grafo G agrupa entes f sicos o conceptuales y las relaciones. entre ellos Un grafo est formado por un conjunto de v rtices. o nodos V que representan a los entes y un conjunto de arcos. A que representan las relaciones entre v rtices Se. representa con el par G V A, Esta figura muestra un grafo formado por los v rtices V. 1 4 5 7 9 y el conjunto de arcos A 1 4 4 1 5 1 1 5 7 9. 9 7 7 5 5 7 4 9 9 4, Un arco o arista representa una relaci n entre dos nodos Esta. relaci n al estar formada por dos nodos se representa por u. v siendo u v el par de nodos, El grafo es no dirigido si los arcos est n formados por pares. de nodos no ordenados no apuntados se representa con un. segmento uniendo los nodos u v EL GRAFO ANTERIOR ES NO. Un grafo es dirigido tambi n denominado digrafo si los pares. de nodos que forman los arcos son ordenados se representan con. una flecha que indica la direcci n de la relaci n u v. EL SIGUIENTE GRAFO ES DIRIGIDO, consta de los v rtices V C D E F H y de los arcos A C D D F.
E H H E E C forma el grafo dirigido G V A, En los modelos realizados con grafos a veces una relaci n entre dos. nodos tiene asociada una magnitud denominada factor de peso en cuyo. caso se dice que es un grafo valorado Por ejemplo los pueblos que. forman una comarca junto con la relaci n entre un par de pueblos que. est n unidos por un camino esta relaci n tiene asociado el factor de peso. que es la distancia en kil metros,GRADOS DE ENTRADA Y DE SALIDA DE UN ARCO. El grado es una cualidad que se refiere a los nodos de un. grafo En un grafo no dirigido el grado de un nodo v grado v. es el n mero de arcos que contienen a v En un grafo dirigido. se distingue entre grado de entrada y grado de salida grado de. entrada de un nodo v gradent v es el n mero de arcos que. llegan a v grado de salida de v gradsal v es el n mero de. arcos que salen de v,grado Lupiana 3,gradent D 1,gradsal D 1. Un camino P de longitud n desde el v rtice v0 a vn en un grafo. G es la secuencia de n 1 v rtices v0 v1 v2 vn tal que vi. vi 1 A arcos para 0 i n Matem ticamente el camino P. v0 v1 v2 vn,VEAMOS EL SIGUIENTE GRAFO,P1 4 6 9 7 es un camino de longitud 3. P2 10 11 es un camino de longitud 1, En resumen la longitud del camino es el n mero de arcos que lo.
el camino Lupiana Valfermoso Atanz n tiene de longitud 12 7. Un camino P v0 v1 v2 vn es simple si todos los nodos que. forman el camino son distintos pudiendo ser iguales v0 vn es. decir los extremos del camino, En un grafo dirigido un ciclo es un camino simple cerrado Por. tanto un ciclo empieza y termina en el mismo nodo v0 vn y. adem s debe tener m s de un arco Un grafo dirigido sin ciclos. ac clico se acostumbra a denominar GDA Grafo Dirigido. Un grafo dirigido en el que los v rtices A E B F A forman un. ciclo de longitud 4, Un grafo no dirigido es conexo si existe un camino entre. cualquier par de nodos que forman el grafo Un grafo dirigido. con esta propiedad se dice que es fuertemente conexo Adem s. un grafo completo es aquel que tiene un arco para cualquier par. de v rtices,GRAFO CONEXO,GRAFO FUERTEMENTE CONEXO,TIPO ABSTRACTO DE DATOS GRAFO. Es preciso definir las operaciones b sicas para construir la. estructura grafo y en general modificar sus elementos En. definitiva especificar el tipo abstracto de datos grafo. Operaciones b sicas a partir de las cuales se construye el. arista u v A ade el arco o arista u v al grafo, aristaPeso u v w Para un grafo valorado a ade el arco u v. al grafo y el coste del arco w,borraArco u v Elimina del grafo el arco u v.
adyacente u v Operaci n que devuelve cierto si los v rtices. u v forman un arco,nuevoV rtice u A ade el v rtice u al grafo G. borraV rtice u Elimina el v rtice u del grafo G,REPRESENTACION DE LOS GRAFOS. Para trabajar con los grafos y aplicar algoritmos que permitan. encontrar propiedades entre los nodos hay que pensar c mo. representarlo en memoria interna qu tipos o estructuras de. datos se deben utilizar para considerar los nodos y los arcos. Una primera simplificaci n es considerar los v rtices o nodos. como n meros consecutivos empezando por el v rtice 0 Es. preciso tener en cuenta que se ha de representar un n mero. finito de v rtices y de arcos que unen dos v rtices. Se puede elegir una representaci n secuencial mediante un. array bidimensional conocida como matriz de adyacencia o. bien una representaci n din mica mediante una estructura. multienlazada denominada listas de adyacencia La elecci n de. una representaci n u otra depende del tipo de grafo y de las. operaciones que se vayan a realizar sobre los v rtices y arcos. MATRIZ DE ADYACENCIA, La caracter stica mas importante de un grafo que distingue a. uno de otro es el conjunto de pares de v rtices que est n. relacionados o que son adyacentes Por ello la forma m s. sencilla de representaci n es mediante una matriz de tantas. filas columnas como nodos que permite modelar f cilmente esa. Sea G V A un grafo de n nodos siendo V v0 v1 vn 1 el. conjunto de nodos y A vi vj el conjunto de arcos Los. nodos est n numerados consecutivamente de 0 a n 1 La. representaci n de los arcos se hace con una matriz A de n x n. elementos denominada matriz de adyacencia tal que todo. elemento aij puede tomar los valores, Dado el siguiente grafo escribir la matriz de adyacencia. Suponiendo que el orden de los v rtices es D F K L R. entonces la matriz de adyacencia, Dado el siguiente grafo no dirigido escribir la matriz de adyacencia.
La matriz de adyacencia, En los grafos no dirigidos la matriz de adyacencia siempre es sim trica ya. que las relaciones entre v rtices no son ordenadas si vi est relacionado. con vj entonces vj est relacionado con vi,MATRIZ DE PESOS. Dado el siguiente grafo escribir la matriz de pesos. El grafo es un grafo dirigido con factor de peso Si los v rtices se numeran. en el orden de V Alicante Barcelona Cartagena Murcia Reus la. matriz de pesos es P y en ella se representa con 0 la no existencia de arco. LA MATRIZ DE ADYACENCIA, La clase Vertice representa un nodo del grafo con su nombre String y. n mero asignado, El constructor inicializa el nombre y pone como n mero de v rtice 1 el. m todo que a ade el v rtice al grafo establece el n mero que le. corresponda,package Grafo,public class Vertice,String nombre.
int numVertice,public Vertice String x,numVertice 1. public String nomVertice devuelve identificador del v rtice. return nombre, public boolean equals Vertice n true si dos v rtices son iguales. return nombre equals n nombre, public void asigVert int n establece el n mero de v rtices. numVertice n, public String toString caracter sticas del v rtice. return nombre numVertice, La clase GrafoMatriz define la matriz de adyacencia el array de v rtices y.
los m todos para a adir nodos y arcos al grafo,package Grafo. public class GrafoMatriz,int numVerts,static int MaxVerts 20. Vertice verts, El constructor sin argumentos crea la matriz de adyacencia para un. m ximo de v rtices preestablecido el otro constructor tiene un. argumento con el m ximo n mero de v rtices,public GrafoMatriz. this maxVerts,public GrafoMatriz int mx,matAd new int mx mx.
verts new Vertice mx,for int i 0 i mx i,for int j 0 i mx i. matAd i j 0,numVerts 0,A ADIR UN VERTICE, La operaci n recibe la etiqueta String de un v rtice del grafo. comprueba si ya est en la lista de v rtices en caso negativo incrementa. el n mero de v rtices y lo asigna a la lista,public void nuevoVertice String nom. boolean esta numVertice nom 0,Vertice v new Vertice nom. v asigVert numVerts,verts numVerts v, numVertice busca el v rtice en el array Devuelve 1 si no lo.
boolean int numVertice String vs,Vertice v new Vertice vs. boolean encontrado false,for i numVerts encontrado. encontrado verts i equals v,if encontrado i,return i numVerts i 1. A ADIR UN ARCO, El m todo recibe el nombre de cada v rtice del arco busca en. el array el n mero de v rtice asignado a cada uno de ellos y. marca la matriz de adyacencia, public void nuevoArco String a String b throws Exception.
va numVertice a,vb numVertice b, if va 0 vb 0 throw new Exception V rtice no existe. matAd va vb 1, Otra versi n del m todo recibe directamente los n meros de. v rtice del arco, public void nuevoArco int va int vb throws Exception. if va 0 vb 0 throw new Exception V rtice no existe. matAd va vb 1, Para grafos valorados este m todo tiene un tercer argumento que. es el factor de peso del arco,VERIFICAR ADYACENCIA.
Determina si dos v rtices v1 y v2 forman un arco es decir. si el elemento de la matriz de,adyacencia es 1, public boolean adyacente String a String b throws Exception. va numVertice a,vb numVertice b, if va 0 vb 0 throw new Exception V rtice no existe. return matAd va vb 1, ublic boolean adyacente int va int vb throws Exception. if va 0 vb 0 throw new Exception V rtice no existe. return matAd va vb 1,LISTA DE ADYACENCIA, Las listas de adyacencia son una estructura multienlazada formada por. una tabla directorio en la que cada elemento representa un v rtice del. grafo del cual emerge una lista enlazada con todos sus v rtices. adyacentes Es decir cada lista representa los arcos con el v rtice origen. del nodo de la lista directorio por eso se llama lista de adyacencia. Para el siguiente grafico dirigido elaborar la matriz de adyacencia. Si se analiza el v rtice 5 es adyacente a los v rtices 1 2 y 4 por ello su. lista de adyacencia consta de tres nodos cada uno con el v rtice destino. que forma el arco El v rtice 4 no es origen de ning n arco su lista de. adyacencia est vac a,Las listas de adyacencia de ste grafo.
ULTIMO PARCIAL, Desarrollar un aplicativo Java que implemente un grafo no dirigido. 1 Que permita definir la cantidad de vectores del grafo. 2 Que permita agregar vectores,3 Que muestre la matriz de adyacencia. Tomado de Joyanes Aguilar Luis Estructuras de datos en Java CASOS 1 4 El recorrido del cartero Imaginemos un grafo que representa el mapa de las calles de un barrio Una calle va de una esquina a la otra En una esquina esta ubicada una oficina de correos Un cartero sale de la oficina de correos y tiene que

Related Books