Grafos

     Definición: Estructura de datos no lineales, conjunto de puntos llamados nodos o vértices a través de un conjunto de líneas llamadas aristas o arcos.  

       Utilidad: Relaciones múltiples en estructuras compuestas por puntos (redes principalmente).

     Aplicaciones: redes informáticas, redes de obras civiles (luz, teléfono, alcantarillado, acueducto, etc.).

     Terminología:

Figura numero 29

En figura Número 29 se muestra gráficamente un grafo lo cual lo conforman:

·        
   

d    Adyacencia: cunado nodos se comunican a través de una sola arista.

Orden: cantidad de nodos.

Camino: conjunto de aristas que comunican dos nodos.

Tipos de Grafos

• Dirigido: las aristas tienen dirección o sentido.
• Ponderado: las aristas tienen peso o valor.
• Conexo: siempre existe un camino que puede comunicar dos nodos.

En la Figura numero 29  el grafo es, no dirigido, no ponderado, conexo.

Ejemplo: 

Figura numero 30

En la Figura numero 30  es un tipo de grafos, no conexo, no dirigido, penderado.

1     Implementación

        Las implementaciones se realizan con el grafo de la figura numero 29.

Arreglos (Matrices): La implementación mediante matrices se realiza de la siguiente manera:

La implementacion mediante matrices se realiza colocando en el espacio de la posición tanto vertical y horizontal el valor de cero en caso de que no exista camino entre esas dos posiciones, y uno en caso de que exista un camino entre esas dos posiciones.

Multilistas: (vector de listas): la implementacion mediante multilistas es el siguiente:

Recorridos:

Profundidad (pilas):   

Amplitud (Colas):

Algoritmos:

Dijkstra.

Kruskal.

Prim

Warshaw

Apreciaciones importantes:

La implementacion de estos algoritmos son realizados en grafos ponderados.