Grafos

Estructura de Datos: Grafos

Un Grafo no es mas que un conjunto de nodos o vértices que se encuentran relacionados con unas aristas. Ademas los vértices tienen un valor y en ocasiones lasaristas también y se le conoce como el costo.

Representación Gráfica de un Grafo



Como se puede ver los puntos son los nodos o vértices, y las lineas son las aristas, en el caso de la imagen esla representación gráfica de un grafo dirigido ya que las aristas tienen un único sentido, ya que de A a D se puede ir pero de D a A no. Si el grafo fuera no dirigido se podría ya que las aristas notienen dirección.

Aplicación

La teoría de Grafos se aplica hoy en día en muchos campos, tales como en Internet, ya que cada computador es un vértice y la conexión entre ellos son las aristas, ademas seusa para hallar la ruta mas corta en empresas de transporte, y en muchas otras áreas.


TERMINOLOGIA DE GRAFOS
Terminología de grafos:
¾ Vértice : Nodo.

¾ Enlace : Conexión entre dosvértices (nodos).

¾ Adyacencia : Se dice que dos vértices son adyacentes si entre ellos hay un
enlace directo.

¾ Vecindad : Conjunto de vértices adyacentes a otro.

¾ Camino : Conjunto devértices que hay que recorrer para llegar desde
un nodo origen hasta un nodo destino.

¾ Grafo conectado : Aquél que tiene camino directo entre todos los nodos.

¾ Grafo dirigido : Aquél cuyosenlaces son unidireccionales e indican hacia
donde están dirigidos.

¾ Gafo con pesos : Aquél cuyos enlaces tienen asociado un valor. En general en
este tipo de grafos no suele tener sentido queun nodo se
apunte a sí mismo porque el coste de este enlace sería nulo.

OPERACIONES BÁSICAS SOBRE GRAFOS
En los grafos, como en todas las estructuras de datos, las dos operaciones básicas soninsertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas.

Insertar vértice

La operación de inserción de un nuevo...