unidad 6 - grafos

ALGORITMOS(CIC621)

Unidad 6. Grafos

J. Miguel Guanira Erazo MSc.

Escuela de Posgrado Maestra en Informtica 1

Unidad 6. Grafos

GRAFOS:

Un grafo G = (V, A) es una estructura de datoscompuesta por un conjunto de elementosdenominados Vrtices (nodos) y un conjunto deAristas o Arcos que conectan los vrtices.

Cada arista es un par (v, w), donde v, w V. Si elpar (v, w) es un par ordenado, el grafo recibe elnombre de Grafo Dirigido.


Unidad 6. Grafos

GRAFOS:Los Grafos permiten abordar todos los problemas de tipo conectividad (el objeto O1 est conectado de una manera u otra al objeto O2) o de optimizacin (caminos ms cortos).Ejemplos: Modelacin de trfico Planificacin de movimientos: recoleccin de

basura, reparto de correspondencia Redes informticas, Internet. Etc.


Unidad 6. Grafos


Lima

Ancash

Cajamarca

Junn

Ucayali

Cuzco

Ica

Ayacucho Puno

EJEMPLO DE GRAFO

Unidad 6. Grafos


GRAFO DIRIGIDO

H

Y

P

F

U Q

K

M

A

Unidad 6. Grafos

GRAFOS:Definiciones: Grado(v): Denominado grado de un vrtice, es elnmero de aristas que se conectan a un vrtice. Sedenota como grado(v). En el ejemplo, P es unvrtice de grado 4, grado(K) = 3, y grado(A) = 0.


H

Y

P

F

U QK

MA

Unidad 6. Grafos

GRAFOS:Definiciones: Vrtices adyacentes: Dos vrtices son adyacentessi est unidos por una arista. En ese caso se dice quela arista es incidente en esos vrtices. En elejemplo, P y Q son adyacente, P y K no sonadyacentes.


H

Y

P

F

U QK

M

GRAFOS:Definiciones: a = (u, u): Denominado lazo o bucle, es una aristaque conecta un vrtice consigo mismo.En el ejemplo los nodos H y M estn conectados

con lazos.

Unidad 6. Grafos


H

Y

P

F

U QK

M

Unidad 6. Grafos

GRAFOS:Definiciones : P = (v1, v2,, vn): Denominado camino, es lasecuencia de vrtices que se debe seguir para llegardel vrtice v1 (origen) al vrtice vn(destino). En elejemplo un camino P para llegar del nodo H al nodoA es H-Y-F-K-A


H

Y

P

F

U QK

MA

Unidad 6. Grafos

GRAFOS:Definiciones : P = (v1, v2,, vn): Se denomina camino cerrado, siel origen (v1) coincide con el destino (vn). En elejemplo el camino H-Y-F-Q-P-H, es un caminocerrado.


H

Y

P

F

U QK

MA

Unidad 6. Grafos

GRAFOS:Definiciones : P = (v1, v2,, vn): Se denomina camino simple, sitodos los vrtices excepto el origen y el destino,son distintos. En el ejemplo el camino H-Y-F-Q-P-H, es un camino simple, pero el camino H-Y-Q-P-M-Q-K no lo es.


H

Y

P

F

QK

MA

Unidad 6. Grafos

GRAFOS:Definiciones : Ciclo: Se denominado ciclo, al camino simple ycerrado que incluye 3 o ms vrtices. En el ejemplolos caminos H-Y-Q-P-H y M-K-A-M son ciclos.


H

Y

P

F

QK

MA

Unidad 6. Grafos

GRAFOS:Definiciones : Tour: Se denominado tour, al camino simple queune todos los vrtices. En el ejemplo el caminosdado por H-Y-F-K-A-M-P-Q es un tour.


H

Y

P

F

QK

MA

Unidad 6. Grafos

GRAFOS:Definiciones : Grafo conexo: Un grafo es conexo si para todo parde vrtices del grafo existe un camino entre ellos.Si el grafo no es dirigido se dice que es dbilmenteconexo. En el ejemplo se puede decir que el grafoes dbilmente conexo.


H

Y

P

F

QK

MA

Unidad 6. Grafos

GRAFOS:Definiciones : Grafo rbol: Un grafo es de tipo rbol si es un esun grafo conexo y no tiene ciclos.

En el ejemplo se puede decir que el grafo es de tiporbol.


1

5

2

4

3

3

1

4

2

Unidad 6. Grafos

GRAFOS:Definiciones : Si el grafo es dirigido se dice que es fuertementeconexo. En el ejemplo se puede decir que el grafoes fuertemente conexo.


H

Y

P

F

Q

Unidad 6. Grafos

GRAFOS:Definiciones : Grafo completo: Un grafo es completo si todos susnodos son adyacentes. En el ejemplo se puede decirque el grafo es completo.


H

Y

P

F

Q

Unidad 6. Grafos

GRAFOS:Definiciones : Multigrafo: Se denomina as al grafo que por lomenos dos de sus vrtices estn conectados por dosaristas. En el ejemplo se puede decir que el grafo esmultigrafo.


H

Y

P

F

Q

Unidad 6. Grafos

GRAFOS:Definiciones : Subgrafo: Dado un grafo G = (V, A), se denominasubgrafo a aquel grafo G1 = (V1, A1) en el que secumple que V1 V, V1 y que A1 A. Ademscada arista de A1 es incidente con V1. En elsiguiente ejemplo se puede apreciar este concepto.


Unidad 6. Grafos


H

Y

P

F

Q

A

C

B

SubGrafo

Unidad 6. Grafos

GRAFOS:Definiciones: Grafo etiquetado: Se dice que un grafo estetiquetado si sus arista tienen algn valor (costo,peso, longitud etc.).


H

Y

P

F

U QK

M1055

9

25

8

20

6018

Unidad 6. Grafos


GRAFOS DIRIGIDOS

Unidad 6. Grafos

GRAFOS DIRIGIDOS:

Un grafo dirigido G, denominado tambin digrafo, esaquel grafo en el que cada una de sus aristas a estasignada a un par ordenado (u, v) de vrtices de G, esdecir tienen una direccin asignada.


H

Y

P

F

Q

Unidad 6. Grafos

ARCO O ARISTA DIRIGIDA:

Se denominan as a las aristas de un grafo dirigido.Se expresan como u v.

-u es el origen y v es el destino.-u es predecesor de v y v es sucesor de u.-u es adyacente hacia v y v es adyacente desde u.


u varco a:

Unidad 6. Grafos

MATRIS DE AYACENCIA:

Los grafos dirigidos, por lo general se modelan mediantearreglos de dos dimensiones de valores binarios (0/1 ofalse/true). Son matrices cuadradas de orden n x n,donde n es representa el nmero de vrtices del grafo. Aestos arreglos se les denomina matrices de adyacenciaM. Las filas de la matriz se relacionan con los vrtices deorigen, mientras que las columnas los vrtices de destino,y los valores de sus elementos M[u][v] tienen un valorde 1 (uno) si existe un arco desde u hacia v y 0 (cero) sino.


Unidad 6. Grafos

MATRIS DE AYACENCIA:Ejemplo:


H

Y

P

F

U QK

M

F H K M P Q U YF 0 0 1 0 0 1 0 0H 0 0 0 0 1 0 0 1K 0 0 0 1 0 0 0 0M 0 0 1 0 0 0 0 0P 0 0 0 1 0 1 0 1Q 0 0 1 0 1 0 0 0U 0 0 0 0 0 0 0 0Y 1 1 0 0 0 0 1 0

Unidad 6. Grafos

MATRIS DE AYACENCIA:Variante (grafos etiquetados):


F H K M P Q U YF 0 0 12 0 0 9 0 0H 0 0 0 0 6 0 0 0K 0 0 0 10 0 0 0 0M 0 0 0 0 0 0 0 0P 0 0 0 5 0 1 0 8Q 0 0 11 0 14 0 0 0U 0 0 0 0 0 0 0 0Y 7 2 0 0 0 0 2 0

H

Y

P

F

U QK

M

10

56

8

12

2

7

211

14

9

Unidad 6. Grafos

LISTAS DE AYACENCIA:

Otra manera de modelar los grafos dirigidos, es pormedio de arreglos unidimensionales de n elementos,donde n representa el nmero de vrtices del grafo. Cadaelemento u del arreglo representan los vrtices de origeny su valor M[u] es un puntero a una lista ligada en dondecada nodo representa el vrtice de destino.


Unidad 6. Grafos

LISTA DE AYACENCIA:Ejemplo:


F

H

K

M

P

Q

U

Y

H

Y

P

F

U Q K

M

K Q

P Y

M

K

M Q Y

K P

F H U

Unidad 6. Grafos

LISTA DE AYACENCIA:Ejemplo:


F

H

K

M

P

Q

U

Y

K/12 Q/9

P/6

M/10

M/5 Y/8

K/11 P/14

F/7 H/2 U/2

H

Y

P

F

U QK

M

10

56

8

12

2

7

211

14

9

Unidad 6. Grafos


DETERMINACIN DE CAMINOS EN GRAFOS

DIRIGIDOS

Unidad 6. Grafos

DETERMINACIN DE CAMINOS EN GRAFOS DIRIGIDOS:

Existen muchos problemas en los que se requiereconocer la existencia de caminos , de manera directa oindirectamente, entre dos puntos. Por otro lado ladeterminacin del menor camino entre dos puntos esigualmente til.Los grafos dirigidos son ideales para resolver este tipo deproblemas.


Unidad 6. Grafos

DETERMINACIN DE CAMINOS EN GRAFOS DIRIGIDOS:

Existen muchos algoritmos que permiten encontrarcaminos que partan de un punto de origen y que lleguena un punto destino recorriendo la menor distancia. Losalgoritmos ms famosos son:

El algoritmo de Dijkstra El algoritmo de Floyd El algoritmo de Warshall

Los tres algoritmos emplean una matriz de adyacencia


Unidad 6. Grafos


ALGORITMO DE DIJKSTRA

Unidad 6. Grafos

ALGORITMO DE DIJKSTRA:

El algoritmo de Dijkstra determina la ruta ms cortaentre un vrtice de origen a cualquier otro vrtice delgrafo dirigido.

Elementos requeridos:

Una matriz de adyacencia M de n x n elementos en elque se coloca en cada elemento M[u][v], la distanciaentre los puntos u y v, si no existe el camino se colocaun valor muy grande (). No se consideran los bucles(M[u][u] = 0).


Unidad 6. Grafos


Un arreglo S que guardar los vrtices una vez seconozca el camino mnimo entre l y el origen.Inicialmente contendr el vrtice origen. Se manejacomo un conjunto.

Un arreglo D de n elementos, cada uno representa unvrtice del grafo, en el que se guarda la distancia entre elorigen y el vrtice. Al terminar el algoritmo, loselementos tendrn las distancias mnimas


Unidad 6. Grafos


Se tienen el conjunto de vrtices V: 1(origen), 2,3,4,, n

Colocar el vrtice origen en el conjunto S. Repetir desde 2 hasta n

o Elegir un vrtice v en V-S tal que D[v] sea el mnimovalor.

o Agregar v a S.o Repetir para cada vrtice w en V-SHacer D[w] mnimo ( D[w], D[v] + M[v][w] )


Unidad 6. Grafos

ALGORITMO DE DIJKSTR:Ejemplo 1: origen ==> 1


11

1

3

2

5

464

3

3

5

6

2

1 2 3 4 51 0 4 11 2 0 6 23 3 0 6 4 0 5 5 3 0

Unidad 6. Grafos ALGORITMO DE DIJKSTR:

Ejemplo 1:


S={1} V - S={2, 3,4,5}

V ={1,2,34,5}

1 2 3 4 5

D 0 4 11 1)min = 4 v = 2 S = {1, 2} V - S = {3, 4, 5}

w 3 D[3] = 11D[2] + M[2][3] = 4 + = min = 11

w 4 D[4] = D[2] + M[2][4] = 4 + 6 = 10min = 10

w 5 D[5] = D[2] + M[2][5] = 4 + 2 = 6min = 6


Ejemplo 1:


S={1, 2} V - S={3,4,5}1 2 3 4 5

D 0 4 11 10 62)

min = 6 v = 5 S = {1, 2, 5} V - S = {3, 4}w 3 D[3] = 11

D[5] + M[5][3] = 6 + 5 = 11min = 11

w 4 D[4] = D[5] + M[5][4] = 6 + 3 = 9min = 9


Ejemplo 1:


S={1, 2,5} V - S={3,4}1 2 3 4 5

D 0 4 11 9 63)

min = 9 v = 4 S = {1, 2, 4, 5} V - S = {3}w 3 D[3] = 11

D[4] + M[4][3] = 9 + = min = 11

Distancia mnima de 1 a 2 41 a 3 111 a 4 91 a 5 6


Ejemplo 1:


Resultado: Distancia mnima de 1 a 2 41 a 3 111 a 4 91 a 5 6

Unidad 6. Grafos

ALGORITMO DE DIJKSTR:Ejemplo 2:


4 1 2 3 4 5 6 7 81 0 2 3 2 4 0 4 6 3 6 0 7 4 0 5 45 6 0 4 36 0 7 2 0 58 1 8

71

32

54

4

36

5

62

6

78

6

42

5

1

3

4

Unidad 6. Grafos


ALGORITMO DE FLOYD

Unidad 6. Grafos

ALGORITMO DE FLOYD:

El algoritmo de Floyd determina la ruta ms corta entretodos los vrtices de un grafo dirigido.


Una matriz de adyacencia M de n x n elementos en elque se coloca en cada elemento M[u][v], la distanciaentre los puntos u y v, si no existe el camino se colocaun valor muy grande (). No se consideran los bucles(M[u][u] = 0).


Unidad 6. Grafos

ALGORITMO DE FLOYD:

Repetir para todo w desde 1 hasta noRepetir para todo u desde 1 hasta nRepetir para todo v desde 1 hasta nSi Muw+Mwv < Muv entonces9Muv Muw+Mwv


Unidad 6. Grafos


ALGORITMO DE WARSHALL

Unidad 6. Grafos

ALGORITMO DE WARSHALL:

El algoritmo de Warshall determina si hay una ruta entretodos los vrtices de un grafo dirigido (no da distancias).


Una matriz de adyacencia M de n x n elementos en elque se coloca en cada elemento M[u][v], el valor 1 sihay un arco que une los vrtices u y v, 0 si no.

Una matriz de C de n x n, inicialmente igual a M dondese guardar 1 si hay un camino entre los vrtices u y v, 0si no.


Unidad 6. Grafos

ALGORITMO DE WARSHALL:

Repetir para todo w desde 1 hasta noRepetir para todo u desde 1 hasta nRepetir para todo v desde 1 hasta nSi Cuv = 0 entonces9Cuv Cuw Cwv


Unidad 6. Grafos


GRAFOS NO DIRIGIDOS

Unidad 6. Grafos

DETERMINACIN DE CAMINOS EN GRAFOS NO DIRIGIDOS:

Los grafos no dirigidos sirven para solucionar problemasde ruteo en los que el costo de ir del vrtice u al vrtice vel igual al de ir del vrtice v al vrtice u.


11

1

3

2

5

4

64

3

35

6

2

Unidad 6. Grafos

RBOL DE EXTENSIN MNIMA:

Un rbol de extensin mnima de un grafo no dirigidoG(V,A) se define como un rbol que conecta todos losvrtices V y est formado por las aristas de menor costo.


1

5

2

4

3

3

1

3

45

62

1

5

2

4

3

3

1

4

2

Unidad 6. Grafos

RBOL DE EXTENSIN MNIMA:

Si se necesita cablear una casa con un mnimode cable, entonces se necesita resolver unproblema de rbol de extensin mnima.


Unidad 6. Grafos


ALGORITMO DE PRIM

Unidad 6. Grafos

ALGORITMO DE PRIM:

El algoritmo de Prim permite encontrar el rbol deextensin mnima para un grafo.


Un conjunto V que contiene los vrtices del grafo.V={1,2,3n}

Un conjunto U que contendr los vrtices del grafo.Inicialmente contiene el primer vrtice, U = {1}.

Un conjunto L de aristas que se formar con las aristasde menor costo. Inicialmente la lista estar vaca, L= .


Unidad 6. Grafos

ALGORITMO DE PRIM:

Mientras V U haceroElegir una arista (u, v) del grafo tal que:Su costo sea mnimo yu U y v V-U

oAgregar la arista (u, v) a LoAgregar el vrtice v al conjunto U


Unidad 6. Grafos

ALGORITMO DE PRIM:Ejemplo 1:


5

4

1

3

2

1

4

3

35

6

2

V = {1, 2, 3, 4, 5}

U = {1}

A = { 1-2, 1-3, 2-3, 2-4,3-4, 3-5,4-5}

L = {}

Unidad 6. Grafos

ALGORITMO DE PRIM:paso 1:


5

4

1

3

2

1

3

V = {1, 2, 3, 4, 5}

U = {1} u

(u, v) 1-2 (1) 91-3 (3)

V-U = {2, 3, 4, 5} vL = {}

Unidad 6. Grafos



V = {1, 2, 3, 4, 5}

U = {1, 2} u

(u, v) 1-3 (3) 92-3 (3) 92-4 (6)

V-U = {3, 4, 5} v5

4

1

3

2

1

3

6

L = {1-2}

Unidad 6. Grafos



V = {1, 2, 3, 4, 5}

U = {1, 2, 3} u

(u, v) 2-4 (6)3-4 (4)3-5 (2) 9

V-U = {4, 5} v5

4

1

3

2

1

4

3

6

2 L = {1-2, 1-3}

Unidad 6. Grafos



V = {1, 2, 3, 4, 5}

U = {1, 2, 3, 5} u

(u, v) 2-4 (6)3-4 (4) 95-4 (5)

V-U = {4} v5

4

1

3

2

1

4

3

56

2 L = {1-2, 1-3, 3-5}

Unidad 6. Grafos

ALGORITMO DE PRIM:resultado:


V = {1, 2, 3, 4, 5}

U = {1, 2, 3, 4, 5} u

rbol de extensin mnima

V-U = {} v5

4

1

3

2

1

4

3

2 L = {1-2, 1-3, 3-5, 3-4}

Unidad 6. Grafos

ALGORITMO DE PRIM:Ejercicio:


V = {1, 2, 3, 4, 5, 6, 7}U = {1}L = {}

3

6

1

5

2

1

4 3 10

5 6

2

4

7

2 7

1

48

Unidad 6. Grafos


ALGORITMO DE KRUSKAL

Unidad 6. Grafos

ALGORITMO DE KRUSKAL:

El algoritmo de Kruskal permite encontrar tambin elrbol de extensin mnima para un grafo.


Un conjunto L que contiene las aristas del grafo y suscostos.

Un conjunto P de particiones. P = {{1}, {2}, {3},{n}}


Unidad 6. Grafos

ALGORITMO DE KRUSKAL:

Mientras haya vrtices en P que pertenezcan aparticiones distintas haceroElegir de L la arista (u, v) que tenga costo mnimoo Si u y v estn en particiones distintas entoncesUnir las particiones a las que pertenezcan u y v


Unidad 6. Grafos

ALGORITMO DE KRUSKAL:Ejemplo 1:


5

4

1

3

2

1

4

3

35

6

2P = {{1}, {2}, {3}, {4}, {5}}

L = { 1-2(1), 1-3(3), 2-3(3), 2-4(6),3-4(4), 3-5(2),4-5(5)}

Unidad 6. Grafos

ALGORITMO DE KRUSKAL:paso 1:


5

4

1

3

2

1

4

3

35

6

2P = {{1}, {2}, {3}, {4}, {5}}

L = { 1-2(1), 1-3(3), 2-3(3), 2-4(6),3-4(4), 3-5(2),4-5(5)}

1-2(1) (u, v)

Unidad 6. Grafos



5

4

1

3

2

1

4

3

35

6

2P = {{1, 2}, {3}, {4}, {5}}

L = { 1-3(3), 2-3(3),2-4(6), 3-4(4),3-5(2), 4-5(5)}

3-5(2) (u, v)

Unidad 6. Grafos



5

4

1

3

2

1

4

3

35

6

2P = {{1, 2}, {3, 5}, {4}}

L = { 1-3(3), 2-3(3),2-4(6), 3-4(4),4-5(5)}

1-3(3) (u, v)

Unidad 6. Grafos



5

4

1

3

2

1

4

3

35

6

2P = {{1, 2, 3, 5}, {4}}

L = { 2-3(3), 2-4(6),3-4(4), 4-5(5)}

2-3(3) 8 ciclo3-4(4) (u, v)

Unidad 6. Grafos

ALGORITMO DE KRUSKAL:resultado:


5

4

1

3

2

1

4

3

2P = {{1, 2, 3, 4, 5}}

L = { 2-4(6), 4-5(5)}

Unidad 6. Grafos

ALGORITMO DE KRUSKAL:Ejercicio:


P = {{1}, {2}, {3}, {4}, {5}, {6}, {7}}

L = { 1-2(2), 1-3(4), 1-4(1), 2-4(3), 2-5(10), 3-4(2),3-6(5), 4-5(7), 4-6(8),4-7(4), 5-7(6), 6-7(1)}

3

6

1

5

2

1

4 3 10

5 6

2

4

7

2 7

1

48

Unidad 6. Grafos


BSQUEDA EN AMPLITUDBREADTH-FIRST

Unidad 6. Grafos

BSQUEDA EN AMPLITUD:

La bsqueda en amplitud es un algoritmo quepermite encontrar un camino entre dos vrtices de ungrafo.El mtodo consiste en que a partir del vrtice inicial,se van analizando los siguientes vrtices porniveles (los que estn conectados al vrtice inicial)y as se va avanzando hasta encontrar el vrtice meta.


Unidad 6. Grafos

BSQUEDA EN AMPLITUD :


Una lista P (pendientes) que contiene los vrtices queaun no se han visitado. Funciona como una cola

Una lista V (visitados) que contiene los vrtices quehan sido visitados.


Unidad 6. Grafos

BSQUEDA EN AMPLITUD : Insertar el vrtice inicial en la lista P Mientras P y no se lleg al vrtice metaoTomar en X un elemento de P (cola: atender)oSi X V entoncesPoner X en V (cola: llegada)Determinar todos los vrtices conectados a XSi en estos vrtices no se encuentra el vrtice meta

Colocarlos en P (cola: llegada)

Si se encontr el vrtice meta XITO De lo contrario FRACASO


Unidad 6. Grafos

BSQUEDA EN AMPLITUD :Ejemplo 1:


V = {} P = { 1 }

6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :paso 1:


V = {}

P = { 2, 8 }6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 1X = VV = {1}

X 2 8

8

1

2

P = { 1}

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :paso 2: X = V


V = {1}

P = { 8, 1, 3, 4, 8}6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 2

X 4

P = { 2, 8}

3 81

8

1

2

3 4 81

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :Paso 3: X = V


V = {1, 2}

P = { 1, 3, 4, 8, 1, 2, 9}6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 8

X 2

P = {8, 1, 3, 4, 8}

1 99

8

1

2

3 4 8 1 2 91

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :Paso 4: X = V, V


V = {1, 2, 8}

P = {4, 8, 1, 2, 9, 2, 5}6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 3

X 2

P = {1, 3, 4, 8, 1, 2, 9 }

5

8

1

2

3 4

2

9

5

8 1 2

1

1

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :Paso 5: X = V


V = {1, 2, 8, 3}

P = {8, 1, 2, 9, 2, 5, 2, 5,6, 9}

6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 4

X 2

P = {4, 8, 1, 2, 9, 2, 5}

5 6 9

8

1

2

3 4 9

5 5 62 92

1 28

Unidad 6. Grafos



V = {1, 2, 8, 3, 4}

P = {2, 5, 2, 5, 6, 9, 4, 6,8, 10 }

6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 9

X 4

P = {8, 1, 2, 9, 2, 5, 2, 5, 6, 9}

86 10

8 21

8

1

2

3 4 9

5 5 62 92

1 28

6 84 10

Unidad 6. Grafos



V = {1, 2, 8, 3, 4, 9}

P = {2, 5, 6, 9, 4, 6, 8, 10,3, 7}

6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 5

X

P = {2, 5, 2, 5, 6, 9, 4, 6, 8, 10}

3 7

2

8

1

2

3 4 9

5 5 62 926 84 10

73

X = V, V

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :Paso 8:


V = {1, 2, 8, 3, 4, 9, 5}

P = {9, 4, 6, 8, 10, 3, 7, 4,7, 9, 11}

6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 6

X

P = {2, 5, 6, 9, 4, 6, 8, 10, 3, 7}

4 7

2 5

9 11

8

1

2

3 4 9

5 5 62 9

6 84 10

73 7 94 11

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :Paso 9: X = V V


V = {1, 2, 8, 3, 4, 9, 5, 6}

P = {3, 7, 4, 7, 9, 11, 7,11, 9, 11}

6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12 9

X

P = {9, 4, 6, 8, 10, 3, 7, 4, 7, 9, 11}

11

610

4

8

9

8

1

2

3 4 9

5 6 9

6 84 10

73 7 94 11 9 11

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :Paso 10: X = V V


V = {1, 2, 8, 3, 4, 9, 5, 6, 10}

P = {4, 7, 9, 11, 7, 11, 9,11, 5, 6}

6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12

X

P = {3, 7, 4, 7, 9, 11, 7, 11, 9, 11}

3 7

8

1

2

3 4 9

5 6 10

73 7 94 119 11

65

65

Unidad 6. Grafos



V = {1, 2, 8, 3, 4, 9, 5, 6, 10, 7}

P = { 11 }6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12

X EXITO

P = {4, 7, 9, 11, 7, 11, 9, 11, 5, 6}

7 11

12

X = V, V4 910

81

2

3 4 9

5 6 10

7 7 94 11 9 11

65 10 12

Unidad 6. Grafos



6

5

2

43

7

89

10

11

12

1

Ruta de 1 a 12

8

1

2

3 4 9

5 6 10

7 11 9 11

65 10 12

Unidad 6. Grafos


BSQUEDA EN PROFUNDIDADDEPTH-FIRST

Unidad 6. Grafos

BSQUEDA EN PROFUNDIDAD:

La bsqueda en profundidad es un algoritmo quepermite encontrar tambin un camino entre dosvrtices de un grafo.El mtodo consiste en que a partir del vrtice inicial,se van analizando los siguientes vrtices poradyacencia, se toma un vrtice adyacente al delinicio y se repite el proceso con el vrtice elegidocomo inicial. Si al final no se encuentra la meta sesigue con otro vrtice adyacente al inicio.


Unidad 6. Grafos

BSQUEDA EN PROFUNDIDAD :


Una lista P (pendientes) que contiene los vrtices queaun no se han visitado. Funciona como una pila.

Una lista V (visitados) que contiene los vrtices que aunno han sido visitados.

Un valor entero LP que indica el lmite de profundidadpermitido (el vrtice inicial tiene profundidad cero, eladyacente a l uno, etc. Si se llega al lmite la ruta notiene xito.


Unidad 6. Grafos

BSQUEDA EN PROFUNDIDAD : Insertar el vrtice inicial en la lista P Mientras P y no se lleg al vrtice metaoTomar en X un elemento de P (pila: pop)oSi X V y su prof(X) LP entoncesPoner X en V (pila: push)Determinar todos los vrtices adyacentes a XSi en estos vrtices no se encuentra el vrtice meta

Colocarlos en P (pila: push)

Si se encontr el vrtice meta XITO De lo contrario FRACASO


Unidad 6. Grafos

BSQUEDA EN PROFUNDIDAD :Ejemplo 1:


V = {} P = { 1 }

Ruta de 1 a 12

LP = 10

6

5

2

43

7

89

10

11

12

1

Unidad 6. Grafos



V = {}

P = { 2, 8 }

Ruta de 1 a 12 1X = VV = {1}

X 2 8

8

1

2

P = { 1}

6

5

2

43

7

89

10

11

12

1

prof(1) = 1

Unidad 6. Grafos



V = {1}

P = {1, 3, 4, 8, 8}

Ruta de 1 a 12 2

X 4

P = { 2, 8}

3 8

8

1

2

3 4 8

6

5

2

43

7

89

10

11

12

1

1

1

Prof(2) = 2

Unidad 6. Grafos

BSQUEDA EN AMPLITUD :paso 3: X = V V


V = {1, 2}

P = {2, 5, 4, 8, 8}

Ruta de 1 a 12 3

X

P = {1, 3, 4, 8, 8}

5

6

5

2

43

7

89

10

11

12

1

2

1

8

1

2

3 4 81

2 5

prof(3) = 3

Unidad 6. Grafos



V = {1, 2, 3}

P = {3, 7, 4, 8, 8}

Ruta de 1 a 12 5

X

P = {2, 5, 4, 8, 8}

7

6

5

2

43

7

89

10

11

12

1

3

2

8

1

2

3 4 8

2 5

3 7

prof(5) = 4

Unidad 6. Grafos



V = {1, 2, 3, 5}

P = {5, 6, 4, 8, 8}

Ruta de 1 a 12 7

X

P = {3, 7, 4, 8, 8}

6

6

5

2

43

7

89

10

11

12

1

5

3

8

1

2

3 4 8

5

3 7

5 6

prof(7) = 5

Unidad 6. Grafos



V = {1, 2, 3, 5, 7, 6}

P = {4, 7, 9, 11, 4, 8, 8}

Ruta de 1 a 12 6

X

P = {5, 6, 4, 8, 8}

7

6

5

2

43

7

89

10

11

12

1

4

5

9 11

81

23

4 85

7

5 6

4 7 9 11

prof(6) = 6

Unidad 6. Grafos



V = {1, 2, 3, 5, 7, 6}

P = {2, 5, 6, 9, 7, 9, 11, 4,8, 8}

Ruta de 1 a 12 4

X

P = {4, 7, 9, 11, 4, 8, 8}

5

6

5

2

43

7

89

10

11

12

1

2 6 9prof(4) = 7

81

23

4 857

6

4 7 9 11

25 6 9

Unidad 6. Grafos



V = {1, 2, 3, 5, 7, 6, 4}

P = {4, 6, 8, 10, 9, 7, 9,11,4, 8, 8}

Ruta de 1 a 12

X

P = {2, 5, 6, 9, 7, 9, 11, 4, 8, 8}

6

6

5

2

43

7

89

10

11

12

1

4 8prof(9) = 8

X = V V62 5 910

81

23

4 857

6

4 7 9 11

25 6 9

4 6 8 10

Unidad 6. Grafos



V = {1, 2, 3, 5, 7, 6, 4, 9}

P = {1, 2, 9, 8, 10, 9, 7, 9,11, 4, 8, 8}

Ruta de 1 a 12

X

P = {4, 6, 8, 10, 9, 7, 9,11, 4, 8, 8}

2

6

5

2

43

7

89

10

11

12

1

1 9

81

23

4 857

6

4 7 9 11

prof(8) = 9

9

X = V V64

4 6 8

8

10

1

2

9

Unidad 6. Grafos



V = {1, 2, 3, 5, 7, 6, 4, 9, 8}

P = { 9, 11, 9, 7, 9, 11, 4,8, 8}

Ruta de 1 a 12

X

P = {1, 2, 9, 8, 10, 9, 7, 9, 11, 4, 8, 8}

6

5

2

43

7

89

10

11

12

1

prof(10) = 9 X = V V21 9 8 10

9 11

81

23

4 857

6

4 7 9 11

9

8

10 1

29

911

Unidad 6. Grafos



V = {1, 2, 3, 5, 7, 6, 4, 9, 8, 10}

P = { 9, 7, 9, 11, 4,8, 8}

Ruta de 1 a 12

X EXITO

P = {9, 11, 9, 7, 9, 11, 4, 8, 8}

6

5

2

43

7

89

10

11

12

1

prof(11) = 10 X = V V9 11

6 10 12

81

23

4 857

6

4 7 9 11

910

9

11 12

Unidad 6. Grafos



Ruta de 1 a 12

6

5

2

43

7

89

10

11

12

1

8

1

2

3 4 8

5

7

6

4 7 9 11

9

1011 12

Unidad 6. Grafos


EJEMPLOS DE BSQUEDA EN AMPLITUD Y PROFUNDIDAD

Unidad 6. Grafos


PROBLEMA DEL PUZZLE-8

3 2 14 5 6

8 7

1 2 387

46 5

Unidad 6. Grafos



321 4

568

7

1 2 387

46 5

ESTADO INICIAL ESTADO FINAL

Unidad 6. Grafos


PROBLEMA DEL PUZZLE-82 31 8 47 6 5

BSQUEDA EN AMPLITUD

2 31 8 47 6 5

2 31 8 47 6 5

2 31

84

7 6 5

2 318 4

7 6 5

2 318 47 6 5

2 31 8

4

7 6 5

2 318

47 6 5

2 31

84

7 6 5

2 31

84

76

5

Unidad 6. Grafos



321 4

56

8

7

1 2 387

46 5

ESTADO INICIAL ESTADO FINAL

Unidad 6. Grafos



2 31

84

7 6 5

BSQUEDA POR PROFUNDIDADprofundidad = 4

2 31

84

76

5

2 31

84

7 6 5

2 31 8 47 6 5

2 318

47 6 5

23

18

47 6 5

23

18

47 6 5 2

3184

7 6 5

231

84

7 6 5

2 318

476 5

2 318

476 5

2 3

1

847

6 52 3

18

476 52 3

1 8 47 6 5

2 31 8 47 6 5

2 318 4

7 6 52 31

8 47 6 5

ALGORITMOS(CIC621)Unidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. GrafosUnidad 6. Grafos

unidad 6 - grafos

Documents