Grafos

Grafos
El origen de la palabra grafo es griego y su significado etimológico es "trazar". aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían serlos siguientes:un gráfico de una serie de tareas a realizar indicando su secuenciación  (un organigrama), grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red deenlaces ferroviarios o aéreos o la red eléctrica de una ciudad, (ver la figura 1). En cada caso es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (nodos ovértices) con líneas conectándolos (arcos).

De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir,un conjunto de puntosy un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices. 
Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica, u estudiopodría dividirse en dos grandes bloques; grafos dirigidos y grafos no dirigidos

Hay dos formas de representar un grafo en memoria:



Matricial: Usamos una matriz cuadrada de boolean en laque las filas representan los nodos origen, y las columnas, los nodos destinos. De esta forma, cada intersección entre fila y columna contiene un valor booleano que indica si hay o no conexión entrelos nodos a los que se refiere. Si se trata de un grafo con pesos, en lugar de usar valores booleanos, usaremos los propios pesos de cada enlace y en caso de que no exista conexión entre dos nodos,rellenaremos esa casilla con un valor que represente un coste es decir, con el valor Natural’Last. A esta matriz se le llama Matriz de Adyacencia
Dinámica: Usamos listas dinámicas. De esta manera, cadanodo tiene asociado una lista de punteros hacia los nodos a los que está conectado. Por simplicidad, nosotros vamos a representar los grafos por el método matricial.
Recorrido de un grafo:
Lo que...