Grafos y Árboles en JAVA

Grafos

Un grafo es un tipo abstracto de datos que consiste en un grupo de nodos y uno de arcos, los cuales establecen una relación entre nodos.

Un ejemplo seria el de una ruta de trenes; las estaciones o paradas serian los nodos y los recorridos entre las estaciones son los arcos.

Pueden ser dirigidos y no dirigidos. Los dirigidos son aquellos cuyos pares (m,n) se ordenan por una flecha que va desde el nodo m al nodo n.

Los no dirigidos son los que se unen por medio de lineas que no tienen dirección.

Tipos de grafos:

• Grafo regular: Es aquel que tiene el mismo grado en sus vértices.

• Grafo Bipartito: Cuando los vértices pueden formar dos conjuntos de manera que no existan adyacencias entre los vértices que pertenecen a un mismo conjunto.

• Grafo Completo: Es el que tiene aristas en cada par de los vértices. Uno completo con n vértices es notado como Kn.

• Grafo nulo: Se genera un grafo nulo cuando los vértices no están conectados o son vértices aislados.

• Grafo Isomorfos: Son aquellos que tienen una correspondencia biunívoca, entre los vértices; es decir uno a uno de tal forma que se unen por una arista en común.

• Grafos Platónicos: Son los que están formados por vértices y aristas de cinco sólidos rectangulares, como lo son el cubo, el tetraedro, icosaedro, octaedro y el dodecaedro.

• Grafos Eulerianos: (Camino Euleriano es aquel que contiene todos los arcos del grafo). Son aquellos que contienen caminos euleriano.

• Grafos Conexos: Es el que no esta dirigido de modo que para cualquier par de nodos existe por lo menos un camino que los une

Representación por matrices:

 Se pueden representar por medio de matrices en donde la N es el numero de vertices en el grafo, la matriz seria:

Implementación:

Se crea una clase grafo en la cual van cuatro miembros:

1. Nodos: los cuales indicaran la cantidad de nodos.
2. Vació: Se le da un valor verdadero si el nodo esta vació. 
3. Información: La información la que cada nodo puede acceder.
4. Adyacente: Representa a lo que es la matriz en donde la celda va desde un nodo i a uno j si el valor es cero es que no existe arco.

El constructor creara un grafo con un numero de nodos que se predispone e inicia liza la matriz a cero.

Ejemplo de Árbol