Universidad Fermín toro vice-rectorado académico

facultad de ingeniería

Estructura de dato Grafo

CREADOR:

MARIANA SANCHEZ PARRA

MATERIA: Análisis de algoritmo

SECCION:

NI-318

PROF: Elvia

Sánchez

índice DEFINICION DE ARISTA

DEFINICION DE VERTICE

GRADO INTERNO, EXTERNO

DEFINICION DE MATRIZ DE ADYACENCIA

CARACTERISTICAS

ALGORITMO DE RECORRIDO DE GRAFO

PROFUNDIDAD

EXPANSIÓN

ALGORITMO PRIM

ALGORITMO DIJKSTRA

CHISTES

HOROSCOPO

DEFINICION DE ARISTA

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.

• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el

mismo.

• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

• Cruce: Son dos aristas que cruzan en un punto.

2

3

DEFINICION DE VERTICE

Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

• Vértice Aislado: Es un vértice de grado

cero.

• Vértice Terminal: Es un vértice de grado 1.

La longitud de camino interno es la suma de las longitudes de camino de todos los nodos del árbol. Es importante porque permite conocer los caminos que tiene el árbol. Puede calcularse por medio de la siguiente fórmula:

LCI = Σni * i

i=1

donde „i‟ representa el nivel del árbol, „h‟ su altura y„ni‟ el número de nodos en el nivel „i‟.

Se puede definir ahora la longitud de camino externo como la suma de las longitudes de camino de todos los nodos especiales del árbol. Se calcula por medio de la siguiente fórmula:

h+1 LCE = Σ n ei * i

i=2 4

GRADO INTERNO Y EXTERNO

en donde „i‟ representa el nivel del árbol, „h‟ su altura y „nei‟ el número de nodos especiales en el nivel „i‟.

Grado _ interno (a) = 1 Grado _ externo (a) = 2 Grado (a) = 3

Grado _ interno (b) = 4 Grado _ externo (b) = 2 Grado (b) = 6

Grado _ interno (c) = 1 Grado _ externo (c) = 2 Grado (c) = 3

Grado _ interno (d) = 2 Grado _ externo (d) = 2 Grado (d) = 4

5

MATRIZ DE ADYACENCIA

Un grafo se puede representar mediante una matriz. Es la forma más sencilla de representar un grafo. A esta matriz se le denomina matriz de adyacencia. Esta matriz consiste en un arreglo bidimensional de tamaño “n”, donde “n” es la máxima cantidad de nodos en el grafo. Cada casilla de la matriz se carga con valores verdadero “V” o falso “F” en caso de que posea un camino de un nodo o fila con columna. En caso de los grafos no dirigidos la matriz será simétrica.

Esto no ocurre en los dígrafos, donde se considera la dirección de cada uno de los arcos. Para el caso de los grafos ponderados, la matriz podrá ser cargada con el peso asociado a cada uno de los arcos.

La ventaja principal es su simplicidad, dado que facilita las operaciones que puedan realizarse sobre el grafo. La desventaja es que se limita a un número máximo de nodos en el grafo, lo que provoca que sea imposible almacenar más información en la matriz.

Si la matriz es muy grande para representar un grafo pequeño, se desperdicia el espacio de almacenamiento de la matriz y de la memoria. Para un grafo no dirigido, el desperdicio será mayor porque al ser simétrica la matriz, su información se duplicaría.

6

CARACTERISTICAS

Para un grafo no dirigido la matriz de adyacencia es simétrica.

El número de caminos Ci,j(k), atravesando k aristas desde el nodo i al nodo j, viene dado por un elemento de la potencia k-ésima de la matriz de adyacencia:

Existen otras formas de representar relaciones binarias, como por ejemplo los pares ordenados o los grafos. Cada representación tiene sus virtudes y desventajas.

7

En particular, la matriz de adyacencia es muy utilizada en la programación, porque su naturaleza binaria y matricial calza perfecto con la de los computadores. Sin embargo, a una persona común y corriente se le hará mucho más sencillo comprender una relación descrita mediante grafos, que mediante matrices de adyacencia.

Otra representación matricial para las relaciones binarias es la matriz de incidencia.

Algoritmo de recorrido de grafo Privado:

ACCION DFS_R(Nodo Actual)

#se marca el nodo actual como visitado

Actual.visitado ¬ verdad;

Ady aux;

aux ¬Actual.ListaDeAdyacentes;

#se recorre la lista de adyacentes al nodo Actual para

#visitarlos

Mientras ( aux ¹ NULL ) hacer

si ( (aux.AdyAeste).visitado ¹ verdad) entonces

#se hace la llamada recursiva a los nodos

#adyacentes para visitarlos

DFS_R(aux. AdyAeste);

fsi

aux ¬ aux.proximo;

fmientras

FACCION

Publico:

ACCION DFS() #Depth-First Search

Nodo aux;

aux ¬ primerNodo;

#aquí se recorre la lista de nodos iterativamente

#haciendo las llamadas al DFS_R (DFS recursivo) cada vez que

#se consiga a alguien no visitado. Esto se hace para evitar

#que el algoritmo no funcione si el grafo tiene varias com-

#ponentes conexas

mientras (aux ¹ NULL) hacer

si (aux.visitado ¹ verdad) entonces

DFS_R(aux);

Fsi aux ¬ aux.proximo;

fmientras

FACCION

8

El método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria. Ahora pasamos a ver la implementación de los distintos recorridos

función DFS (Grafo G(V,E), función DFS (Grafo G(V,E), int i)

{

visitado[i] = true;

foreach foreach (v[j] adyacente a v[i]) (v[j] adyacente a v[i])

if (!visitado[j]) if (!visitado[j])

DFS(G,j);

}

9

PROFUNDIDAD

EXPANSION

10

Recorridos en amplitud (o por niveles): En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que solo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.

Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo. El esquema algoritmo para implementar un recorrido por niveles es exactamente el mismo que el utilizado en la versión iterativa del recorrido en preorden pero cambiando la estructura de datos que almacena los nodos por una cola.

void arbol_recorrido_anch (tipo_Arbol* A)

tipo_Cola cola_nodos; // esta cola esta implementada previamente, almacena punteros (posiciones de nodos de árbol)

tipo_Pos nodo_actual; // este es un puntero llevara el recorrido

if (vacio(A)) // si el árbol esta vacio, salimos

return;

cola_inicializa(&cola_nodos); // obvio, y necesario

cola_enqueue(A, &cola_nodos); // se encola la raíz

while (!vacia(&cola_nodos)) { // mientras la cola no se vacie se realizara el recorrido

nodo_actual = cola_dequeue(&cola_nodos) // de la cola saldran los nodos ordenados por nivel

printf("%c,", nodo_actual->info); // se "procesa" el nodo donde va el recorrido, en este caso se imprime

if (nodo_actual->izq != null) // si existe, ponemos el hijo izquierdo en la cola

cola_enqueue(nodo_actual->izq, &cola_nodos);

if (nodo_actual->der != null) // si existe, ponemos el hijo derecho en la cola

cola_enqueue(nodo_actual->der, &cola_nodos);

} // al vaciarse la cola se han visitado todos los nodos del árbol

}

11

ALGORITMO DE PRIM

12

El algoritmo de Prim es tal vez el algoritmo de MST más sencillo de implementar y el mejor método para grafos densos. Este algoritmo puede encontrar el MST de cualquier grafo conexo pesado.

Sea V el conjunto de nodos de un grafo pesado no dirigido. El algoritmo de Prim comienza cuando se asigna a un conjunto U de nodos un nodo inicial perteneciente a V, en el cual “crece” un árbol de expansión, arista por arista. En cada paso se localiza la arista más corta (u,v) que conecta a U con V-U, y después se agrega v, el vértice en V-U, a U. Este paso se repite hasta que V=U. El algoritmo de Prim es de O(N2), donde | V | = N.

El siguiente ejemplo ilustra el funcionamiento del algoritmo. La secuencia de ilustraciones va de izquierda a derecha y de arriba hacia abajo. La primera imagen muestra el grafo pesado y las siguientes muestran el funcionamiento del algoritmo de Prim y como va cambiando el conjunto U durante la ejecución.

13

ALGORITMO DE DIJKSTRA

El algoritmo de Dijkstra resuelve el problema de encontrar los caminos más cortos a partir de un origen, en grafos pesados que no tengan pesos negativos.

El algoritmo de Dijkstra es un algoritmo voraz que opera a partir de un conjunto S de nodos cuya distancia más corta desde el origen ya es conocida. En principio, S contiene sólo el nodo origen. En cada paso, se agrega algún nodo v a S, cuya distancia desde el origen es la más corta posible. Bajo la hipótesis de que los pesos son no negativos, siempre es posible encontrar un camino más corto entre el origen y v que pasa sólo a través de los nodos de S, al que llamaremos “especial”. En cada paso del algoritmo, se utiliza un arreglo D para registrar la longitud del camino “especial” más corto a cada nodo. Una vez que S incluye todos los nodos, todos los caminos son “especiales”, así que D contendrá la distancia más corta del origen a cada vértice. Se puede utilizar un arreglo P, para ir almacenando los caminos más cortos.

14

A continuación se muestra un esbozo del algoritmo de Dijkstra en lenguaje pseudoformal : #Supóngase la existencia del siguiente grafo Conjunto V; # Conj. de nodos del grafo-N nodos Arreglo C de real [1..N][1..N]; # Matriz de costos de las aristas #y las siguientes variables auxiliares entero i,w,v; Arreglo D de real [1..N]; # arreglo auxiliar de costos Arreglo P de entero [1..N]; # arreglo que guarda los caminos más # cortos Conjunto S; # Conjunto de nodos evaluados # Inicializado con el conjunto vacío #el esbozo del algoritmo de Dijkstra S.Agregar(1); # tomando el nodo 1 como nodo origen Para i ¬2 hasta N hacer D[i] ¬ C[1][i]; # asignando valores iniciales a D Fpara Para i ¬ 1 hasta N-1 hacer w ¬ nodo en V-S tal que D[w] sea un mínimo S.Agregar(w); Para cada nodo v Î V-S hacer15 D[v] ¬ min (D[v], D[w]+C[w,v]); Fpara P[v] ¬ w; Fpara

15

Al final de la ejecución, cada posición del arreglo P contiene el nodo inmediato anterior a v en el camino más corto a partir del nodo inicial. Dado el grafo

al final de la ejecución el arreglo P debe tener los valores P[2]=1, P[3]=4 , P[4]=1 y P[5]=3. Para encontrar el camino más corto del nodo 1 al nodo 5, por ejemplo, se siguen los predecesores en orden inverso comenzando en 5. Así, es sencillo encontrar que el camino más corto del nodo 1 al 5, es el 1, 4, 3, 5. Usando el arreglo P, o bien mediante alguna otra heurística, se puede construir fácilmente un SPT, tomando el nodo inicial del recorrido como raíz del árbol y luego añadiendo una arista y un nodo a la vez, siempre tomando la próxima arista que pertenezca al camino más corto a un nodo que no esté en el SPT.

16

El orden en tiempo de ejecución del algoritmo de Dijkstra depende muchísimo de las características del grafo y de cómo este almacenado.

Si se emplea una matriz de adyacencia como en el código anterior, entonces el ciclo más interno es de O(N) y como se ejecuta N-1 veces, tendríamos un algoritmo de O(N2). Si por el contrario se utiliza una representación dinámica, justificada en el hecho de que el número de aristas es mucho menor a N2, se podría emplear un árbol parcialmente ordenado para organizar los nodos V-S, y por lo tanto se reduciría la complejidad del ciclo más interno un orden logarítmico.

17

CHISTES

CHISTES CORTOS

- ¿Bailamos? - Claro. ¿Pero quién saca a mi amiga? - Ahhh, por eso no te preocupes. ¡SEGURIDAAAAD!

Jaimito le dice a su padre: - ¡Papá, papá, tengo una noticia buena y otra mala! - Primero la buena - ¡Que he aprobado todas! ¿Y la mala? - ¡Que es mentira!

18

HOROSCOPO

ARIES: EL DÍA DE HOY TRAERÁ NUEVA ENERGÍA EN TU CAMINO. UN COLEGA O AMIGO TE SUGERIRÁ UN NUEVO PROCEDIMIENTO O ESTRATEGIA DISTINTA. ¡SI ESCUCHAS LO QUE TIENE QUE DECIR, DESCUBRIRÁS QUE POSIBLEMENTE TE ESTÁ PRESENTANDO UNA SOLUCIÓN MÁGICA!

TAURO: HOY LA ALINEACIÓN CELESTIAL TE BENDICE CON BUENA FORTUNA Y SENTIMIENTOS DE ARMONÍA. ALGUNOS CORRESPONDERÁN A QUE RECIBIRÁS NOTICIAS FELICES. O PUEDE QUE PASES UN BUEN MOMENTO CON TU AMOR SECRETO QUE TE LLENARÁ EL CORAZÓN CON TERNURA.

GEMISIS: HOY DESCUBRIRÁS UN SECRETO OCULTO. NO EXISTE NADA QUE TE GUSTE MÁS QUE EL MISTERIO, Y HOY TENDRÁS LA OPORTUNIDAD DE DESCUBRIR UNO. PUEDE SER ALGO PEQUEÑO, COMO DESCUBRIR CUÁL ES LA MELODÍA FAVORITA DE TU PAREJA.

CANCER: HOY SENTIRÁS GANAS DE CONECTARTE CON TUS AMISTADES. A VECES TRABAJAS TANTO Y TE ESTANCAS TANTO EN LOS PROBLEMAS QUE TE NIEGAS UN POCO LA VIDA SOCIAL. ÁBRETE A LA ENERGÍA POSITIVA QUE LOS DEMÁS DESEAN BRINDARTE.

LEO: ES MUY COMÚN QUE TE HAYAS ACOSTUMBRADO A OTRAS DIMENSIONES. CON LA ENERGÍA CELESTIAL ACTUAL, RECIBIRÁS ALGUNAS PREMONICIONES O VISIONES QUE PARECEN PROVENIR DE ARRIBA. EL TRUCO ES REALMENTE HACERLE HONOR A LAS REVELACIONES QUE RECIBES, AUNQUE RESULTEN EFÍMERAS.

VIRGO: HOY LA CONFIGURACIÓN CELESTIAL TE PONDRÁ EN HUMOR DE FIESTA, POR LO TANTO SI NO HAS HECHO PLANES PARA LA NOCHE, COMIENZA A PENSAR EN ALGO ATREVIDO Y DIVERTIDO. SENTIRÁS COMO SI SALIERAS DEL CAPARAZÓN Y GRITARÁS A TODO PULMÓN.

19

HOROSCOPO

LIBRA: HOY TENDRÁS UN HUMOR MUY ROMÁNTICO. ES IMPORTANTE QUE ENCUENTRES UNA AMISTAD VERDADERA EN TU PAREJA. DESEAS QUE RESPETE LAS METAS DE TU VIDA Y EL RUMBO QUE HAS ELEGIDO PARA TU CARRERA.

ESCORPIO: LA ENERGÍA ASTRAL DEL DÍA TE HARÁ SENTIR NERVIOSISMO E INQUIETUD. DEMÁS, TENDRÁS SENSIBILIDAD HACIA LA ENERGÍA DE OTRAS PERSONAS PORQUE ESTARÁS CON UN HUMOR HIPERSENSIBLE.

SAGITARIO: EL DÍA DE HOY TE AUGURARÁ CAMBIOS INESPERADOS PERO POSITIVOS EN TU VIDA PERSONAL. LOS MIEMBROS FAMILIARES DESCUBRIRÁN NUEVOS CAMINOS QUE DESEAN SEGUIR. UNA OPORTUNIDAD REPENTINA PARA AVANZAR NECESITARÁ UN MOVIMIENTO, PERO NO PERMITAS QUE LA RESISTENCIA AL CAMBIO SE INTERPONGA EN TU CAMINO.

CAPRICORNIO: UNA SENSACIÓN INCREMENTADA DE UNIDAD ENTRE TUS AMISTADES MÁS ÍNTIMAS Y ENTRE CUALQUIER GRUPO AL QUE TENGAS AFILIACIÓN AUMENTARÁ TU SENSACIÓN DE EMOCIÓN Y ENTUSIASMO PARA EL FUTURO. LAS RELACIONES CON EL SEXO OPUESTO TE SERÁN ESPECIALMENTE BENEFICIOSAS.

ACUARIO: PROPONTE EL COMENZAR UNA RUTINA DE MEDITACIÓN O ALGÚN TIPO DE YOGA. PUEDES CONSIDERAR COMPRAR ALGÚN OBJETO ADIVINADOR O UN MAZO DE CARTAS DE TAROT. TIENES UNA CONEXIÓN MUY FUERTE CON LO OCULTO.

PISCIS: HOY, LAS COSAS NO SALDRÁN COMO TE ESPERABAS, PERO SI TE RELAJAS TODO SE RESOLVERÁ. LA ENERGÍA SOCIAL TRAERÁ ALGUNAS SORPRESAS QUE NO SERÁN DESAGRADABLES. LO QUE SÍ, TENDRÁS UNA DISCUSIÓN DESAGRADABLE CON UN FAMILIAR O AMIGO QUE TE HARÁ ABRIR LOS OJOS A ALGÚN SECRETO QUE SE TE HA ESCONDIDO.

20