Mensajes

Amigo no tienes las primeras dos ediciones? Gracias!

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.

Usar un BFS me servirá si se trata de un grafo no dirigido?

[Ganimedes]

Prueba así:

Código (c) [Seleccionar] Expandir

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.

Si se me había ocurrido esa idea pero me lanza lo mismo! lo que me imprime es esto:

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

y pense en eso que me dijiste porque contando hasta la palabra Ganimedes hay exactamente 21, y puse 42 en el archivo y si me los lee completo pero necesito ese n intacto, que sera?

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.

Claro, pero el algoritmo de Dijkstra me retornara el camino mínimo, pero yo no necesito el camino mínimo, de hecho no tengo porque tomar en cuenta los pesos, únicamente necesito el camino en el que para llegar a un Y desde X utilize el menor numero de escalas(aristas)

[n]

Este es el caso, tengo un archivo de esta forma:

Código [Seleccionar] Expandir

21
Shukra P
Io L
Aisa A
Sirio S
Mangala P
Alfa_Centauri S
Europa L
Guru P
Beta_Crucis S
Laquesis A
Ganimedes L
Cloto A
Vega S
Capella S
Atropos A
Shani P
Rigel S
Calisto L
Afrodita_Urania A
Budha P
Alfa_Crucis S

Leo el numero de cuerpos n que en este caso es 21 e inicio este ciclo para guardarlos en un vector de registro:

Código [Seleccionar] Expandir

fscanf(pf,"%d",&n); 

for (i=1;i<=n;i++){   

fscanf(pf,"%s",planet_info[i-1].nombre);
fscanf(pf,"%c",planet_info[i-1].cod);

}

Donde planet_info es un vector de tipo cuerpos y cuerpos es un registro que contiene dos elementos, una cadena nombre y un char cod. El problema es que solo me almacena hasta Ganimedes y no me llega hasta el final. y la verdad no entiendo cual pueda ser el problema! el archivo abre y cierra perfectamente y el vector esta declarado para 200 posiciones. si me echan una mano seria de gran ayuda, saludos!

Es que no tengo ningún pseudo! solo lo he leído ya listo para compilar en C++ y en Java y ni idea de como traducirlos a C. Gracias!

Tengo que hacer un ejercicio para mi facultad y me necesito dos algoritmos de grafos, uno es el conocido algoritmo de kruskal para el árbol recubridor mínimo, he googleado pero la verdad solo lo he visto en Java y en C++ y solo domino lenguaje C. Y el otro es un algoritmo que me calcule el camino mas corto entre un par de vértices pero no en cuanto al peso, sino en cuanto a la cantidad de aristas o arcos que recorre y la verdad de este si no he conseguido nada. De verdad se los agradecería mucho!!