Grafos en Java

Desde un punto de vista intuitivo un grafo es un conjunto de nodos unidos por un conjunto de arcos. Un ejemplo de grafo que podemos encontrar en la vida real es el de un plano de trenes. El plano de trenes está compuesto por varias estaciones (nodos) y los recorridos entre las estaciones (arcos) constituyen las líneas del trazado.

Veremos a continuación una definición más formal de grafos. Un grafo G=(V,E) consiste en un conjunto V de nodos (vértices) y un conjunto E de aristas (arcos). Cada arista es un par (v,w), siendo v y w un par de nodos pertenecientes al conjunto V de nodos. Podemos distinguir entre grafos dirigidos y no dirigidos. En un grafo dirigido los pares (v,w) están ordenados, traduciéndose la arista en una flecha que va desde el nodo v al nodo w.

En el caso de un grafo no dirigido, los nodos están unidos mediante líneas sin indicación de dirección.

Por último se puede definir una función que asocie a cada arco un coste: coste(arco)

Estudiaremos a continuación algo de terminología común en los grafos.

Hablaremos de dos vértices adyacentes cuando estén unidos por un arco. El número de vértices adyacentes de un nodo constituye el grado del mismo. En el ejemplo los vértices adyacentes al nodo 3 son el 1, 4 y 5, siendo éste por tanto un nodo de grado tres por tener tres vértices adyacentes.

Un camino entre dos vértices, es una secuencia de vértices tal que dos vértices consecutivos son adyacentes. En el siguiente ejemplo el camino entre el vértice a y el vértice e será la secuencia de vértices abecde.

Cuando este camino no tiene vértices repetidos se dice que es simple. Salvo en el caso de que el primer y último vértice del camino sean el mismo, en cuyo caso hablaremos de un ciclo

La siguiente clasificación, aunque no es completa, presenta las principales características que nos podemos encontrar en los grafos:

• Grafo conexo: Cuando entre cada dos nodos del grafo hay un camino.
  
  
• Bosque: Es un grafo sin ciclos.
  
  
• Arbol libre: es un bosque conexo.
  
  

La representación más extendida de los grafos es mediante lo que se llaman Matrices de adyacencia. Si el número de vértices del grafo es N, la matriz de adyacencia es un una matriz tal que:

Mediante esta representación, la matriz de adyacencia del ejemplo sería

La implementación de un grafo valorado en una clase de java, representado mediante una matriz de adyacencia sería:

La clase grafo está compuesta de cuatro miembros:

• Adyacentes: Representa la matriz de adyacencia donde cada celda Adyacentes[i][j] representará el valor del arco que va desde el nodo i al nodo j. Si el valor es 0, consideraremos que no existe arco alguno.
  
  
• Información: Representa la información accesible a cada nodo.
  
  
• nodos: que indica el número de nodos.
  
  
• vacio: con valor true si el grafo está vacío.
  
  

El constructor creará un grafo con un número de nodos igual a numeroNodos. Inicializará la matriz de adyacencia a cero.