Grafos

Un grafo es una representación gráfica de datos y la forma en que podemos acceder y manejar a los datos. Un grafo es un conjunto de vértices o nodos los cuales son objetos que se relacionan mediante aristas o arcos, que es el camino o la forma en que estas se comunican.
Los grafos se pueden representar como G = (V, A) siendo V las vértices y A las aristas.
Los grafos constan de caminos ydimensiones o grado.
El grado dependen del número de vértices siendo V el grado de G esto es GV .
Los grafos como ya aviamos establecido constan de caminos los cuales pueden ser simple, ciclos (circuitos) o eulerianos. Un camino simple es aquel el cual todos las aristas que abarca son distintas y aparte puede ser elemental cuando no utiliza el mismo vértice 2 veces. “Por tanto todo caminoelemental es simple y el recíproco no es cierto”. Los circuitos son aquellos los cuales empiezan en un vértice y terminan en el mismo, se llaman circuitos simples cuando todas las aristas por las que pasa son distintas y elemental cuando todos los vertices por los que pasa son distintos (claro exceptuando el punto final). Y el euleriano el cual se forma cuando el camino es simple y aparte pasa por todaslas aristas del grafo.
Un grafo se denomina simple si no contiene bucles (bucles) y aparte no existe mas de un camino para unir 2 nodos.
Los grafos se pueden clasificar como dirigidos o no dirigidos. El grafo se denomina dirigido cuando los caminos (aristas) son en un solo sentido y son no dirigidos cuando los caminos de comunicación son en ambos lados.
Aquí unos ejemplo:

Los grafos sepueden representar de 2 formas distintas:
-Como una matriz
-Como una lista

-Como una matriz:

Es la forma más directa y usual de representar los grafos. Siendo la matriz M de dimensiones v x v, siendo v el número de nodos o de datos. Esta forma aunque muy buena para poder contar las aristas entre los nodos es muy ineficiente en el caso de que el grafo sea muy poco poblado o poco denso.Esto es cuando se tienen muchos vértices pero pocas aristas. Al hacerlo de esta forma, solo se desperdiciaría memoria. Lo ideal es usarlo cuando el grafo está completamente poblado o frondoso.

-matriz de adyacencia
Es cuando la matriz es ordenada de acuerdo a los vértices que tengan que ver con las aristas, esto es se toman las distintas aristas y se observa donde chocan con un vértice. A estamatriz también se le llama matriz de bits o booleana.
-matriz de caminos
Es aquella la cual cuenta el número de aristas recorridas desde un vértice a otro. Ya que esta matriz lo que hace es; si existe un camino de b a b1 esto quiere decir que hay un camino simple entre estos elementos el cual es registrado en la matriz.

-Como una lista
La representación de grafos por listas es el darle oasociar cada vértice con una lista la cual contiene las diferentes aristas con las cuales este tiene contacto. Entonces el grafo se convierte en un vector de listas las cuales apuntan a cada vértice. Esto es muy eficiente a la hora de ahórranos espacio, la desventaja es que puede tomar mucho tiempo el determinar si un vértice tiene conexión con otro y esto es por los n vértices que puede llegar ahaber.
Ejemplo de grafos por lista.

Otra cosa que hay que recordar de las listas es que como se les puede dar un valor ya sea numérico o de otros tipos a los vértices y a las aristas (a esto se llama etiquetar), entonces hay que hacer un apartado o una lista aparte para los valores.
Como hemos visto a pesar de las 2 posibilidades sigue habiendo inconvenientes los cuales se pueden corregirjuntando las características de los 2, ósea juntando las características de los grafos como matrices y la de los grafos como lista.
Esto es posible haciendo una lista de listas con lo cual se pueden juntar las 2 opciones anteriores y aparte agregar o eliminar ya sea aristas o vértices de forma eficiente. Cabe resaltar, lo cual no se podía hacer en las dos anteriores ya que no se pueden eliminar ya...