analisis de algoritmo
1
Facultad:
Ingeniería
Escuela:
Computación
Asignatura: Programación IV
Tema: Grafos en C#.
Objetivos Específicos
•
Definir el concepto de Grafo.
•
Apartir de una clase agregar la sintaxis necesaria para construir una función de grafos en C#
Materiales y Equipo
•
Guía Número 7.
•
Computadora con programa Microsoft Visual C#.Introducción Teórica
Grafos.
Un grafo G = (V, E) está formado por un conjunto de elementos llamados vértices “V” y un
conjunto de aristas “E” que conectan a los distintos vértices. En ocasiones losvértices son
llamados nodos y las aristas arcos.
Las aristas se definen como el par de vértices que conectan y pueden tener asociado un valor
el cual representa el peso o dificultad para desplazarse de unvértice a otro.
Ejemplo gráfico de un grafo:
Figura 1.
Donde:
Vértices = {A, B, C, D, E}
Aristas = {(A, B), (A, D), (B, C), (B, D), (B, E), (C, E), (D, E), (E, D)}
2
Programación IV.Guía 7
Tipos de grafos.
Existen dos tipos de grafos: los no dirigidos y los dirigidos.
Grafos No Dirigidos.
Son aquellos en los cuales las aristas no están orientadas (no son flechas). Cada ladose
representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta que
ambos vértices son origen y destino a la vez: (Vi, Vj) = (Vj, Vi).
Grafos Dirigidos.
Son aquellos en loscuales las aristas están orientadas (son flechas). Cada arista se representa
entre paréntesis, separando sus vértices por comas y teniendo en cuenta (Vi, Vj) ≠ (Vj, Vi).
Los grafos puedenrepresentarse de varias formas en una computadora:
Listas adyacentes.
Cada vértice tiene una lista de vértices los cuales son adyacentes a él.
Representación del ejemplo (grafo de Figura 1):
(A) => B=> D
(B) => C => D => E
(C) => E
(D) => E
(E) => D
Listas de pares ordenados (incidentes).
Las aristas se representan como un arreglo de pares ordenados.
Matriz de adyacencia.
El...
Regístrate para leer el documento completo.