Kruskal si lees y entiendes cómo funciona no es para nada complicado. Mira qué hace el algoritmo y una vez lo entiendas lo podrás programar. La única parte algo más complicada es si quieres hacer eficientemente el paso de comprobar si dos nodos están unidos directa o indirectamente, que lo puedes programar con un MFSet.

Respecto al segundo problema, como ya te han dicho se reduce a un problema de caminos mínimos. Ignora los costes originales de las aristas y ponles a todas coste 1. Es evidente que el camino mínimo entre dos nodos será con estos nuevos costes aquel que use un menor número de aristas. En lo que discrepo es con la recomendación de usar Dijkstra. Cuando todas las aristas tienen el mismo coste, puede calcularse la mínima distancia de un nodo al resto usando simplemente un BFS estándar, dado que este recorre el grafo por niveles. Y BFS es más eficiente que Dijkstra.

Prueba así:

fscanf(pf,"%d",&n);  
	for (i=1;i<=n;i++)
		fscanf(pf,"%s %c",planet_info[i-1].nombre, planet_info[i-1].cod);
 

La explicación de por qué falla es que con cafa fscanf() avanzas una línea, así que ibas avanzando de dos en dos.

21
Shukra P
Io L
Aisa A
Sirio S
Mangala P
Alfa_Centauri S
Europa L
Guru P
Beta_Crucis S
Laquesis A
Ganimedes

Para el camino más corto lee sobre dijkstra: http://en.wikipedia.org/wiki/Dijkstra's_algorithm . Y sobre los pesos como dice Akai debería funcionarte.