• Author / Uploaded
• Endre Huaman de la Vega

Citation preview

UNIVERSIDAD NACIONAL DE SAN ANTONIO ABAD DEL CUSCO

FACULTAD DE INGENIERIA ELÉCTRICA, ELECTRÓNICA, INFORMÁTICA Y MECÁNICA

Escuela Profesional de Ingeniería de Informática y de Sistemas

INFORME DE LABORATORIO Nº 01 “RECORRIDO DE GRAFOS” Curso: Bioinformática

Docente: Ing. Julio César Carbajal Luna

Huaman de la Vega, Endre (130346) Cusco – Perú 2018

INFORME DE LABORATORIO N° 01

INDICE I.

II.

INFORMACION GENERAL ...................................................................................................... 3 -

Objetivos ........................................................................................................................... 3

-

Equipos, materiales, programas y recursos utilizados ...................................................... 3 MARCO TEORICO ................................................................................................................... 3

III. PROCEDIMIENTO ................................................................................................................... 6 IV. ANALISIS E INTERPRETACION DE RESULTADOS................................................................... 10 V.

CUESTIONARIO .................................................................................................................... 12

CONCLUSIONES ........................................................................................................................... 12 RECOMENDACIONES ................................................................................................................... 12 BIBLIOGRAFIA .............................................................................................................................. 12 WEBGRAFIA ................................................................................................................................. 12

INFORME DE LABORATORIO N° 01

I.

INFORMACION GENERAL - Objetivos -

Entender el concepto y definiciones de grafo, y conceptos relacionados con este. Estudiar algunas de las propiedades básicas de los tipos principales de grafos para poder aplicarlas a la resolución de problemas prácticos. Aplicar esquemas algorítmicos secuenciales clásicos (de busca y de recorrido) para la resolución de problemas de grafos. Conocer recorridos en anchura y profundidad de grafos dirigidos y no dirigidos. Implementación en Python de recorridos en grafos dirigidos y no dirigidos, y entender su funcionamiento.

-

-

-

- Equipos, materiales, programas y recursos utilizados -

II.

Laptop con sistema operativo Windows 10 Pro. Atom 1.27.2 (x64) Python 3.6.5 (x82)

MARCO TEORICO

¿Qué es un grafo? Un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices (V) y un conjunto de aristas (E), donde cada arista relaciona a un par de nodos pertenecientes a V. La estructura algebraica para los grafos es G= (V, E). Existen dos tipos de grafos: 

GRAFO DIRIGIDO: Un grafo dirigido G consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo.

INFORME DE LABORATORIO N° 01



GRAFO NO DIRIGIDO: Un grafo no dirigido se diferencia de un Grafo Dirigido a que cada arista en E es un par no ordenado de vértices.

RECORRIDO DE GRAFOS Los grafos se pueden recorrer de dos formas:  Por Profundidad (DFS).  Amplitud o Anchura (BFS). RECORRIDO EN PROFUNDIDAD (DFS) A medida que recorremos el grafo, iremos numerando correlativamente los nodos encontrados (1, 2, ...). Suponiendo que todos estos números son cero inicialmente, utilizamos un contador global n, también inicializado en cero. El siguiente en seudocódigo muestra cómo se puede hacer ese tipo de recorrido recursivamente: DFS(v) // recorre en profundidad a partir del vértice v { ++n; DFN[v]=n; for(todo w tal que {v,w} está en E y DFN[w]==0) DFS(w); } Para hacer un recorrido en profundidad a partir del nodo v, utilizamos el siguiente programa principal (Código en Python): n=0; for (todo w){ DFN[w]=0;}

INFORME DE LABORATORIO N° 01

DFS(v); Si hubiera más de un componente conexo, esto no llegaría a todos los nodos. Para esto podemos hacer:

n=0; ncc=0; // número de componentes conexas for(todo w) DFN[w]=0; while(existe v en V con DFN[v]==0) { ++ncc; DFS(v); }

RECORRIDO EN ANCHURA(BFS) La implementación es similar a la de DFS, con la diferencia de que se utiliza una cola en lugar de una pila. El resultado es que los nodos se visitan en orden creciente en relación a su distancia al nodo origen.

INFORME DE LABORATORIO N° 01

III.

PROCEDIMIENTO

Paso 1: Creación de una clase llamada class Grafo.

Paso 2: Creación de un módulo para agregar datos del grafo

INFORME DE LABORATORIO N° 01

Paso 3: Implementamos el algoritmo de recorrido en profundidad utilizando una pila.

INFORME DE LABORATORIO N° 01

Paso 4: Implementamos el algoritmo de recorrido en anchura utilizando una cola

INFORME DE LABORATORIO N° 01

Paso 5: Implementación de menú

Paso 6: Implementación de Opciones para grafo.

INFORME DE LABORATORIO N° 01

Paso 7: Instanciamos la clase Grafo.

IV.

ANALISIS E INTERPRETACION DE RESULTADOS

Visualización de Mostrar Grafo:

INFORME DE LABORATORIO N° 01

Resultado de recorrido en profundidad:

Resultado de recorrido en Anchura:

INFORME DE LABORATORIO N° 01

V.

CUESTIONARIO

CONCLUSIONES 

Los algoritmos de búsqueda BFS y DFS son una de las herramientas básicas a la hora de trabajar con grafos. No sólo podremos usarlos para recorrer grafos o buscar elementos, sino que también podemos adaptarlos y mejorarlos para resolver de manera eficiente cualquier tipo de situaciones que podamos moldear como un grafo o un árbol.

RECOMENDACIONES BIBLIOGRAFIA  

LEISERSON, Cormen. Introduction to Algorithms. MIT press, 1990 VIDAL, Enrique. Algoritmos en Grafos, Facultad de Informática, Universidad Politécnica de Valencia,2000.

WEBGRAFIA 

  

https://www.google.com.pe/search?q=grafos+wikipedia&oq=graf os+w&aqs=chrome.2.69i57j69i60j0l4.5129j0j7&sourceid=chrome &ie=UTF-8 https://rvargass.wordpress.com/unidad-iii-recorrido-degrafos/recorrido-de-grafos/ http://www.cs.cornell.edu/courses/CS2112/2012sp/lect www.comp.nus.edu.sg/~stevenha/visualization/df sbfs.html