Verified answer

1. Manera simple: Pide el número de vértices y luego para cada vértice número i preguntas cuáles son los vértices adyacentes a i. Manera elegante: Leerlo desde un archivo en un formato más o menos fácil de entender; por ejemplo, que cada renglón número i contenga una lista de los vértices adyacentes a i separados por una coma. Manera profesional: leerlo desde un archivo DOT (http://en.wikipedia.org/wiki/DOT_language )

2. Conforme los vas leyendo los vas almacenando en el list<int> que corresponde con el vértice número i (http://www.cplusplus.com/reference/stl/list/ )

3. Es muy difícil dibujar un grafo en una consola de texto. Más bien quieres simplemente escribir la representación como lista de adyacencia. Solamente necesitas iterar sobre arreglo de listas y escribir cada lista separada por comas.

4. Los algoritmos de Prim y de Dijkstra (y en general casi todo algoritmo que opere con gráficas ponderadas) son muy difíciles de implementar eficientemente usando listas de adyacencia; en su lugar conviene que uses la representación matricial del grafo. Una vez que entiendes cómo funciona el algoritmo de Dijkstra su implementación es realmente fácil: Comienzas con un conjunto que al principio contiene solamente al vértice inicial, y en cada iteración te fijas en la arista que cruza este conjunto y que tiene peso mínimo.

5. Pues... ¿has visto el pseudocódigo de esos algoritmos? ¡es igualito! Aunque puedes evitar la recursión usando un montón de trucos interesantes.

Te recomiendo que leas:

• Capítulos 3 y 4 de "Algorithms" http://www.cs.berkeley.edu/~vazirani/algorithms.ht...

• Capítulos 23 y 24 de la tercera edición de "Introduction to algorithms" de Cormen y compañía (no conozco ningún link de descarga)