Grafos

Un grafo consiste en un conjunto de vértices o nodos y un conjunto de arcos (o aristas). Se representa con el par G=(V,A).

Propiedades

Grafo Dirigido: los pares de nodos que forman los arcos son ordenados.

Grafo Valorado: los arcos pueden tener asociado un factor de peso.

Grado de un nodo: nº de aristas que contienen al nodo (Grafo no Dirigido).

Grado entrada/salida de un nodo: nº de arcos entrantes/salientes (Grafo Dirigido).

Camino Simple: todos sus nodos son distintos, pudiendo ser iguales los extremos.

Ciclo: es un camino simple cerrado, compuesto por al menos 3 nodos.

Grafo Conexo: si existe un camino entre cualquier par de nodos.

Representación de los grafos:

Þ     Matriz de Adyacencia: mediante arrays.

Þ     Listas de Adyacencia: mediante estructuras multienlazadas.

Recorrido de un grafo:

v  Recorrido primero en anchura

v  Recorrido primero en profundidad