Corporación Universitaria Minuto de Dios
INVESTIGACION SOBRE GRAFOS
Asignatura:
Estructura de Datos
NRC: 12766
Presenta:
Jeyson Alejandro Pereira Forero
ID: 660953
Docente:
Daymer Arley Garcia Galindo
12 de mayo de 2019 -Villavicencio, Meta.
GRAFOS
Desde un punto de vista intuitivo un grafo es un conjunto de nodos unidos por un conjunto de
arcos. Un ejemplo de grafo que podemos encontrar en la vida real es el
de un plano de trenes. El plano de trenes está compuesto por varias
estaciones (nodos) y los recorridos entre las estaciones (arcos)
constituyen las líneas del trazado.
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
Figura 1 Grafo no dirigido
las relaciones entre vértices. Se representa con el par G = (V, A).
La Figura 1.1 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 de la Figura 2 es no dirigido. 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
Figura 2 Grafo dirigido
la dirección de la relación, u → v. El grafo de la Figura 1.2, que 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}
Dado el arco (u,v) de un grafo, se dice que los vértices u y v son adyacentes. Si el grafo es
dirigido, el vértice u es adyacente a v, y v es adyacente de u.
OPERACIONES BÁSICAS DE LOS GRAFOS
En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y
borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e
insertar/eliminar aristas.
Insertar vértice
La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente
consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los
vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más,
inicialmente aislado, ya que ningúna arista llegará a él.
Insertar arista
Esta operación es también muy sencilla. Cuando se inserte una nueva arista en el grafo, habrá
que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un
vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se
deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino.
Eliminar vértice
Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la
eliminación de la tabla de vértices del vértice en sí. A continuación habrá que eliminar las aristas
que tuviesen al vértice borrado como origen o destino.
Eliminar arista
Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario
eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.
Otras operaciones
Las operaciones adicionales que puede incluir un grafo son muy variadas. Además de las clásicas
de búsqueda de un elemento o recorrido del grafo, también podemos encontrarnos con ejecución
de algoritmos que busquen caminos más cortos entre dos vértices, o recorridos del grafo que
ejecuten alguna operación sobre todos los vértices visitados, por citar algunas operaciones de las
más usuales.
Utilización de los grafos
Los campos de utilización de los grafos son muy variados, ya que los vértices pueden representar
cualquier elemento (ciudades, aeropuertos, pc's...), y las aristas serían la conexión entre esos
elementos (carreteras, pasillos aéreos, redes...). Por lo tanto, los grafos son muy usados en la
modelización de sistemas reales.
Implementación
Los grafos se implementan de dos formas: matriz de adyacencia y listas de adyacencia. Cada una
tiene sus ventajas y desventajas relativas. La elección depende, entre otros factores, de la
densidad del grafo; para grafos densos, con muchos arcos, se recomienda representarlos con la
matriz de adyacencia. Los grafos poco densos y que experimenten modificaciones en sus
componentes se representan con listas de adyacencia.
RECORRIDO DE UN GRAFO
Recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Muchos
de los problemas que se plantean con los grafos exigen examinar las aristas o arcos de que consta
y procesar los vértices.
Hay dos formas de recorrer un grafo: recorrido en profundidad y recorrido en anchura. Si el
conjunto de nodos marcados se trata como una cola, el recorrido es en anchura; si se trata como
una pila, el recorrido es en profundidad.
Recorrido en anchura
Se utiliza una cola como estructura en la que se mantienen los vértices marcados que se van a
procesar posteriormente. El proceso de los elementos en una cola (primero en entrar primero en
salir) hace que, a partir del vértice de partida v se procesen primero todos los vértices adyacentes
a v, después los adyacentes de éstos que no estuvieran ya marcados o visitados, y así
sucesivamente con los adyacentes de los adyacentes. El orden en que se visitan los nodos en el
recorrido en anchura se expresa de manera más concisa en los siguientes pasos:
a) Marcar el vértice de partida v.
b) Meter en la cola el vértice de partida v.
c) Repetir los pasos 4 y 5 hasta que se cumpla la condición cola vacía.
d) Quitar el nodo frente de la cola, w, visitar w.
e) Meter en la cola todos los vértices adyacentes a w que no estén marcados y, a
continuación
f) marcar esos vértices.
g) Fin del recorrido.
Recorrido en profundidad
La búsqueda de los vértices y aristas de un grafo en profundidad persigue el mismo objetivo que
el recorrido en anchura: visitar todos los vértices del grafo alcanzables desde un vértice dado.
Difiere este recorrido con el recorrido en anchura sólo en el orden en que se procesan los vértices
adyacentes. El orden en el recorrido en profundidad es el que determina la estructura pila. El
recorrido empieza por un vértice v del grafo, se marca como visitado y se mete en la pila.
Después se recorre en profundidad cada vértice adyacente a v no visitado; hasta que no haya más
vértices adyacentes no visitados. Esta estrategia de examinar los vértices se denomina en
profundidad porque la dirección de visitar es hacia adelante mientras resulta posible; al contrario
que la búsqueda en anchura que primero visita todos los vértices posibles en amplitud.
Bibliografía:
Joyanes Aguilar, L., Zahonero Martínez, I. (2007). Estructuras de datos en Java. Madrid:
McGraw-Hill
