Foro de elhacker.net

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

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.

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!

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

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)

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?

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.

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.

El algoritmo de Dijkstra es un algoritmo voraz (avance rápido) y tiene un orden de complejidad de O(n²), incluso se puede conseguir un O(a·log n) siendo a el número de aristas haciendo una implementación distinta a la que se suele usar. Y los algoritmos de BFS (al menos, los que yo he visto) tienen un orden de O(n²) con matrices de adyacencia, y O(a+n) con listas de adyacencia. Así que tampoco se diferencian tanto los tiempos de ejecución cuando tienes un grafo completo.

Siguiendo tu notación, efectivamente Dijkstra tiene complejidad cuadrática sobre los nodos en su implementación directa. Si lo implementas con colas de prioridad con coste logarítmico, bajas la complejidad a O((n + a)logn), que es la complejidad de BFS con un factor logarítmico extra (programándolo bien, obviamente).

Si el grafo es completo, i.e. a = n², uno quedará O(n²logn) y otro O(n²), que evidentemente es mejor.

Esto hablando de las versiones estándar de cada uno. Si se quiere rizar el rizo y hablar de la versión de Dijkstra con Fibonacci Heaps, que rara vez se usa a la práctica, entonces se acaba teniendo una complejidad teórica (no hablemos ya de las constantes debidas a implementación) de O(a + nlogn), que sigue siendo peor que un BFS.