Unidad III

 Grafos

¿Qué es un Grafo?

Es un conjunto de vértices (V) y aristas (E), en donde cada arista se relaciona con uno o más nodos de un vector.

 

Existen dos tipos de grafos:

• Grafos Dirigidos: es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida.

• Grafos No Dirigidos: no poseen un orden especifico como en el grafo dirigido por ende no tiene una dirección definida.

Los grafos dirigidos y no dirigidos se pueden representar por:

• Matriz de Adyacencia: es una matriz cuadrada de tamaño «n» que representa relaciones binarias.

• Lista de Adyacencia:  se representan todas las aristas del grafo en una lista.

• Arreglos para la lista de Adyacencia: implementación de las listas de adyacencia.

Conceptos Básicos de Grafos:

Recorridos de Grafos

Recorrido por amplitud o anchura : Se establece a los grafos un esquema de árbol en donde se ordenan los nodos por niveles, en donde los valores quedan organizados de izquierda a derecha (menor a mayor).

Recorrido por profundidad: Al igual que el recorrido por amplitud se puede establecer como un árbol pero difiere en su forma de recorrer el grafo; trata de recorrer la mayor cantidad de nodos posibles (se recorre de izquierda a derecha como un árbol de pre-orden) .

Tabla Comparativa de Recorridos

ALGORITMO DE DIJKSTRA