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!!

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!

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.

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.

Sinceramente yo usaría el algoritmo de Dijkstra, porque tiene el mismo orden de complejidad que una BFS, y existen pseudocódigos que puedes traducir directamente a C.

Saludos.