Clase PAP 2017 Melanie https://git.exactas.uba.ar/ltaravilse/pap-alumnos/blob/master/clases/clase03-grafos/grafos.pdf

Un grafo es un conjunto de objetos, llamados vértices o nodos, unidos mediantes líneas llamadas aristas. Se los usa para representar muchas cosas, por ejemplo en arquitectura, los nodos pueden representar habitaciones o espacios, y las aristas pueden significar que los espacios unidos comparten una pared.

También se los usa para analizar redes, donde los nodos son computadores y una arista representa que las computadoras que une están conectadas.

Se los usa para entender y analizar muchíisimas cosas en la vida real, y hay muchos problemas de programación que ilustran situaciones posiblemente reales para los cuales usaremos grafos.

Los grafos sirven para representar relaciones entre distintas “cosas”. Esas “cosas”, nuestros nodos, pueden ser cualquier cosa, comidas, personas, ciudades... y hasta puede haber algunos nodos que representen un tipo de cosa, y otros nodos que representen otro tipo, por ejemplo nodos que representen personas, y otros que representen comidas, y que la relación sea “a la persona $A$ le gusta la comida $B$”. Las relaciones las representamos con aristas. Hay veces que además de saber que dos nodos están relacionados, nos importa cómo. Las aristas pueden tener un número que indique su distancia por ejemplo, indicando qué tan lejos están esos nodos. También podrían estar orientadas, es decir que no sea sólo una línea, sino una flecha. Esto podría indicar por ejemplo que desde la esquina $A$ se puede llegar a la $B$ a través de una arista, que sería la calle, pero si es de una sola mano no podemos ir a través de ella de $B$ a $A$, entonces indicamos ese tipo de relación con una flecha.

Estos son algunos ejemplos de grafos:

Links a BFS y DFS

[Hay que completar todo]