Algoritmos para grafos (C)

[k3r00t]

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

[Akai]

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

Poniendo las aritas a peso 1 debería solucionarte ese problema.

Para lo otro que pides, mira el pseudocódigo de Kruskal y prográmalo tu.

[k3r00t]

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!

[leogtz]

Ponlo aquí en C++, a ver si se puede pasar a C sin problemas. Saludos.

[Nork]

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.

[k3r00t]

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)

[ghastlyX]

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.

[k3r00t]

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?

[Valkyr]

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.

[ghastlyX]

Eso es falso, el orden de complejidad de Dijkstra es mayor que el de BFS y a la práctica también es más lento. Además, también hay pseudocódigos a patadas de BFS, que además es más fácil de programar que Dijkstra.

Edito:
Respecto a la pregunta anterior, sirve tanto si el grafo es dirigido como no dirigido.