RE:Como implementar un grafo
De manera sencilla no hay muchas opciones, pero para hacerlo más o menos bien lo mejor que puedes usar son punteros.
Primero haces una estructura (struct) que represente un nodo y luego, dentro de ese nodo, hay punteros a otros nodos que son las aristas. Tienes que hacer todas las funciones de añadir, borrar y buscar, pero ten cuidado no pierdas ningún nodo.
Cuando yo lo implementé mi solución fue enlazar todos los nodos a un nodo "root" pero no intervenía en los cálculos de caminos. Sólo era para no perder ningún nodo.
Saludos.