Grafos c++

PNFSI
Asignatura: Desarrollo de Software Tema: Grafos

Ing. Zamantha González

Abril, 2008

Tema 4: Grafos
Contenido • Definición de grafo. • Operaciones sobre grafos. • Representación matricial de grafos en un lenguaje de programación. • Grafos (representación enlazada) • Operaciones sobre grafos representados de manera enlazada. • Representación enlazada de grafos en un lenguaje deprogramación

Objetivos
Conozcan las estructuras de datos arbóreas y las formas de trabajar con ellas en la solución de problemas de mediana complejidad

Introducción
Estructuras de datos estudiadas:

Listas lineales y sus variantes. Las relaciones entre los nodos de información son lineales. •Todos los nodos tienen un único antecesor, excepto el primero que no tiene antecesor.
•Todos losnodos tienen un único sucesor, excepto el último que no tiene sucesor.

Introducción
Estructuras de datos estudiadas: Los árboles y sus variantes Cuando se está en presencia de relaciones no lineales de tipo jerárquica, se utilizan los árboles.
• Un nodo puede tener más de un sucesor. • Se puede establecer un camino único desde el nodo raíz hasta un nodo cualquiera del árbol. • Cada nodotiene un único padre, exceptuando al nodo raíz del árbol, que no tiene padre.

Introducción
En ocasiones, incluso, se requiere tener acceso a un nodo determinado a partir de más de un nodo de la estructura. Existen varios caminos entre un nodo y otro. Ejemplo: • Una red hidráulica, • Caminos entre ciudades, • Afinidad entre miembros de un colectivo, entre otros.

Introducción

Ciudad B CiudadA

Ciudad D
Ciudad C

Ciudad F

Ciudad E

Caminos entre ciudades

Definición de Árbol
Un árbol (tree) es un T.D.A. que consta de un conjunto finito T de nodos y una relación R (paternidad) entre los nodos tal que: • Hay un nodo, especialmente designado, llamado la raíz del árbol T. A

B
D

C E
F G

Definición de Árbol
• Los nodos restantes, excluyendo la raíz, sonparticionados en m (m  0) conjuntos disjuntos T1, T2, ..., Tm, cada uno de los cuales es, a su vez, un árbol, llamado subárbol de la raíz del árbol T.

A
B C E

D

F

G

Definición de Árbol
• A los nodos que no son raíces de otros subárboles se les denomina hojas del árbol T, o sea, no tienen sucesores o hijos. A B C E

D

F

G

Grafos
Un grafo (en inglés graph) es un T.D.A. querepresenta un conjunto finito N de nodos, llamados vértices, relacionados entre sí por un conjunto R de arcos.
Grafo con 5 vértices y 6 arcos. A

• Vértices del Grafo N ={ A, B, C, D, E } • Arcos del Grafo C
E

B
D

R={(A, A), (A, B), (A, D), (A, C), (D, C), (C, E)}

Grafos: Aclaraciones
•Si el conjunto N es vacío, el grafo será vacío.
• Cada arco de un grafo establece una únicarelación entre dos vértices. • No existe restricción en la relación que establece un arco, o sea, un vértice puede estar relacionado consigo mismo o con otro vértice.

• Cada arco se representa a través de un par, donde cada elemento determina uno de los vértices.

Observación
Dado que no hay restricciones en cuanto a los arcos de un grafo, todas las estructuras vistas con anterioridad pueden serconsideradas como un grafo.
Ejemplo, una lista lineal puede ser vista como un grafo donde cada nodo está relacionado con exactamente un nodo distinto de él.

Clasificación de los Grafos
Un grafo es no orientado o no dirigido (en inglés not directed o not oriented graph) si el hecho de que el arco (Nj, Nk) pertenezca a R implica que el arco (Nk, Nj) pertenece a R, para todo j y k.
• Esirrelevante el sentido de las saetas en los arcos • Al representarlos, los arcos se grafican sin saeta. • El arco que los relaciona aparece una sola vez en el conjunto R de arcos del grafo.

Si el grafo es no orientado, al arco se le llama arista.

Clasificación de los Grafos
Un grafo es orientado o dirigido (en inglés: oriented graph o directed graph) si el hecho de que el arco (Nj, Nk)...