Recorridos de Grafos

50 %
50 %
Information about Recorridos de Grafos

Published on November 30, 2007

Author: evansbv

Source: slideshare.net

Description

Recorridos de Grafos

ESTRUCTURA DE DATOS II RECORRIDOS DE GRAFOS UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIA PROFESOR: Ing. Evans Balcazar Veizaga

PROFESOR:

Ing. Evans Balcazar Veizaga

Recorridos en Grafos: Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida.    Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura y el recorrido en profundidad. Así, para recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Hay dos formas. Recorrido en profundidad (DFS). Recorrido en anchura (BFS).

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodo de salida.    Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura y el recorrido en profundidad.

Así, para recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Hay dos formas.

Recorrido en profundidad (DFS).

Recorrido en anchura (BFS).

Recorrido en Profundidad (DFS) : Trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente. La búsqueda en profundidad empieza por un vértice V. del grafo G; V no visitado; así hasta que no haya mas vértices adyacentes no visitados.

Trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más. Cuando ya no puede avanzarse más sobre el camino elegido, se vuelve atrás en busca de caminos alternativos, que no se estudiaron previamente.

La búsqueda en profundidad empieza por un vértice V. del grafo G; V no visitado; así hasta que no haya mas vértices adyacentes no visitados.

Ejemplo de DFS : Analice el siguiente grafo y realice el recorrido primero en profundidad: Grafo => DFS(50)=50,17,12,9,14,23,19,72,54,67,76

Analice el siguiente grafo y realice el recorrido primero en profundidad:

Recorrido en Anchura (BFS) : Supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida. Este método comienza visitando el vértice de partida A, para continuación visitar los adyacentes que no estuvieron ya visitados. Así sucesivamente con los adyacentes. Este método utiliza una cola como estructura auxiliar en la que se mantienen los vértices que se vayan a procesar posteriormente.

Supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que están a una distancia de un arco del nodo de salida, después los que están a dos arcos de distancia, y así sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.

Este método comienza visitando el vértice de partida A, para continuación visitar los adyacentes que no estuvieron ya visitados. Así sucesivamente con los adyacentes. Este método utiliza una cola como estructura auxiliar en la que se mantienen los vértices que se vayan a procesar posteriormente.

Ejemplo de BFS : Analice el siguiente grafo y realice el recorrido primero en anchura: Grafo => DFS(50)=50,17,72,12,23,54,76,9,14,19,67

Analice el siguiente grafo y realice el recorrido primero en anchura:

Recorridos Primero en profundidad Visitar vértice inicial v i Visitar vértice adyacente a v i ... proceder así hasta encontrar uno ya visitado... Volver atrás hasta llegar a un vértice con adyacentes sin visitar El recorrido termina cuando volviendo atrás llegamos al vértice inicial v i y no quedan adyacentes por recorrer Primero en anchura Visitar vértice inicial v i Visitar todos los vértices adyacentes a v i Al terminar, comenzar a visitar los adyacentes a los adyacentes a v i ... proceder así hasta que no queden vértices por visitar

Primero en profundidad

Visitar vértice inicial v i

Visitar vértice adyacente a v i

... proceder así hasta encontrar uno ya visitado...

Volver atrás hasta llegar a un vértice con adyacentes sin visitar

El recorrido termina cuando volviendo atrás llegamos al vértice inicial v i y no quedan adyacentes por recorrer

Primero en anchura

Visitar vértice inicial v i

Visitar todos los vértices adyacentes a v i

Al terminar, comenzar a visitar los adyacentes a los adyacentes a v i

... proceder así hasta que no queden vértices por visitar

Recorridos Profundidad DFS(v i ){ marcar v i como visitado para cada v k adyacente a v si v k no visitado entonces DFS(v k ) } Anchura BFS(v i ){ marcar v i como visitado meter v i en cola q mientras cola q no vacía sacar v de cola q para cada v k adyacente a v si v k no visitado entonces marcar v k visitado meter v k en cola q }

Profundidad

DFS(v i ){

marcar v i como visitado

para cada v k adyacente a v

si v k no visitado

entonces DFS(v k )

}

Anchura

BFS(v i ){

marcar v i como visitado

meter v i en cola q

mientras cola q no vacía

sacar v de cola q

para cada v k adyacente a v

si v k no visitado

entonces

marcar v k visitado

meter v k en cola q

}

Recorridos: operaciones auxiliares Marcar vértice como visitado Si los vértices están identificados por algún tipo ordinal, emplear un conjunto que contenga los identificadores de los vértices visitados Encontrar los vértices adyacentes Con matrices de adyacencia: recorrer la fila correspondiente al vértice, buscando columnas a TRUE Con listas de adyacencia: recorrer la lista Cola de vértices visitados en anchura Operaciones del TAD Cola

Marcar vértice como visitado

Si los vértices están identificados por algún tipo ordinal, emplear un conjunto que contenga los identificadores de los vértices visitados

Encontrar los vértices adyacentes

Con matrices de adyacencia: recorrer la fila correspondiente al vértice, buscando columnas a TRUE

Con listas de adyacencia: recorrer la lista

Cola de vértices visitados en anchura

Operaciones del TAD Cola

Recorrido primero en profundidad 1, 3, 6, 10, 13, 12, 9, 5, 2, 4, 7, 8, 11 1 2 3 4 6 7 8 5 10 11 9 13 12 1 10 2 11 6 8 3 9 7 4 5 12

Recorrido primero en anchura 1, 3, 4, 2, 6, 7, 8, 5, 10, 11, 9, 13, 12 1 2 3 4 6 7 8 5 10 11 9 13 12 1 2 3 4 5 6 7 8 9 10 11 12

Implementación de DFS : Se utilizara una composición de la class conjunto, para llevar la cuenta de los vértices marcados: void DFS(int v) { Conjunto v; DFS(v,c); } void DFS(int v1,Conjunto c) { cout<<v1; c.insertar(v1); for( w.adyancente(v1)) if(!c.pertenece(w)) DFS(w,c); } void DFS(int v1,Conjunto c) { cout<<v1; puntero L=V[v1]; while( L!=Tierra) { int w=Data(L); if(!c.pertenece(w)) DFS(w,c); } }

Se utilizara una composición de la class conjunto, para llevar la cuenta de los vértices marcados:

Implementación de BFS : Se utilizara una composición de la class conjunto, para llevar la cuenta de los vértices marcados: void grafo:: DFS(int v) { Conjunto v; Cola q; q.meter(v); do{ int w; q.sacar(w); if(!c.pertenece(w))//no marc { cout<<w; q.insertar(w);//marc for(x.adyacente(w)) { if(!c.pertecene(x)) q.meter(x); } } } while(!q.vacia()) }

Se utilizara una composición de la class conjunto, para llevar la cuenta de los vértices marcados:

¿Ahora a Trabajar?

GRACIAS INF-310 Estructura de Datos II

Add a comment

Related presentations

Related pages

Recorridos de grafos - cs.upc.edu

Table of Contents. Recorridos de grafos. Recorridos de grafos: Introducción. Recorridos de grafos: Recorrido en profundidad. Recorridos de grafos ...
Read more

Recorrido de Grafos | Análisis de Algoritmos

Recorridos de Grafos. En muchas aplicaciones es necesario visitar todos los vértices del grafo a partir de un nodo dado. Algunas aplicaciones son:
Read more

Recorrido de grafos - YouTube

Recorrido de grafos ... MATEMATICAS DISCRETA RECORRIDOS DE GRAFOS - Duration: 25:33. Ingenieria en computacion e informatica 1SC 54 views.
Read more

A-Recorridos de grafos - webdiis.unizar.es

J. Campos - C.P.S. Esquemas algorítmicos - Grafos Pág. 2 Recorridos de grafos: Introducción v Justificación de la necesidad: Programas que precisan ...
Read more

Algoritmos grafos recorrido recorrer nodos | Algoritmos

Posts about Algoritmos grafos recorrido recorrer nodos written by RoDelaRivera. Inicio; Búsqueda y Orden; Complejidad Computacional; Recorrido de Grafos ...
Read more

algoritmosygrafos - Algoritmos de recorrido de grafos.

Grupo 2 tomamos el tema 3: Algoritmos de recorrido de grafos. ... Los algoritmos de recorridos de grafos pueden ser: - por orden topologico. - por niveles.
Read more

RECORRIDOS EN GRAFOS - fiwiki.org

Departamento de Matemática Aplicada. Facultad de Informática. UPM Matemática Discreta II Curso 12 13 1 RECORRIDOS EN GRAFOS 3) Estudiar si los ...
Read more

algoritmosygrafos - Recorridos en grafos

RECORRIDOS DE UN GRAFO Recorrer un grafo significa “visitar” todos los nodos de esta a través de sus aristas. Se trata de realizar un recorrido del ...
Read more

Recorridos de un grafo, Arevalo Lara, Cristian Encalada ...

Autores: Arevalo Lara, Cristian Encalada, Cinthya Sanches Tema: Recooridos de Grafos busqueda de anchura y busqueda de profundidad Docente: ING ...
Read more