Foro de elhacker.net

Hola buenas, tengo que hacer un grafo para la universidad en c, y la verdad es que estoy bastante atascado..

He estado buscando pero no encuentro nada que me sirva.. alguien podria ayudarme?

Tengo que realizar un grafo, sin ponderar y sin dirigir, bien sencillito.

Para empezar he puesto 5 nodos, y he creado la matriz de adyacencia, hasta ahi bien.

El problema es que no se como hacer para buscar los vecinos y buscar el camino minimo, es decir, que te digan el origen y el destino y tu indiques el camino minimo... ahi estoy atascado...

Por lo que tengo entendido hay que crear una cola ciruclar, pero no se como, estoy bastante liado..

alguna ayuda?

Para encontrar la ruta mas corta entre dos vértices en un grafo no dirigido puedes utilizar el algoritmo de Dijkstra (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm).

Un saludo

No me dejan utilizarlo, me hacen hacerlo con una cola

Debe ser algún algoritmo matemático conocido, pero implementado mediante colas, ¿no?

Bueno, estoy conjeturando ... :rolleyes:

La verdad es que no tengo ni idea, no nos ha dicho nada mas... para la vuelta de navidad traed un grafo que busque el camino mas corto entre los nodos mediante colas...

Ahora mismo tengo esto para buscar los vecinos, pero no funciona..

void inicializarGrafo(struct grafo *grafo) {
	grafo->numNodos = 5;
	strcpy(grafo->nombres[0], "Centro");
	strcpy(grafo->nombres[1], "Ensanche");
	strcpy(grafo->nombres[2], "Fuenfresca");
	strcpy(grafo->nombres[3], "San Leon");
	strcpy(grafo->nombres[4], "San Julian");
 
	grafo->matriz[0][0]=0;
	grafo->matriz[0][1]=1;
	grafo->matriz[0][2]=0;
	grafo->matriz[0][3]=1;
	grafo->matriz[0][4]=1;
	grafo->matriz[1][1]=0;
	grafo->matriz[1][0]=1;
	grafo->matriz[1][2]=1;
	grafo->matriz[1][3]=0;
	grafo->matriz[1][4]=1;
	grafo->matriz[2][2]=0;
	grafo->matriz[2][0]=0;
	grafo->matriz[2][1]=1;
	grafo->matriz[2][3]=1;
	grafo->matriz[2][4]=1;
	grafo->matriz[3][3]=0;
	grafo->matriz[3][0]=1;
	grafo->matriz[3][1]=0;
	grafo->matriz[3][2]=1;
	grafo->matriz[3][4]=1;
	grafo->matriz[4][0]=1;
	grafo->matriz[4][1]=1;
	grafo->matriz[4][2]=1;
	grafo->matriz[4][3]=1;
	grafo->matriz[4][4]=0;
}
 
void buscarVecinos(struct grafo *grafo, int indiceNodo, char Nodo) {
	int nodo_origen, i;
	char nodo_origenl, nodo;
	printf("Selecciona un nodo: \n 0.-Centro\n1.-Ensanche\n2.-Fuenfresca\n3.-San Leon\nSan Julian\n");
	scanf("%d", &nodo_origen);
	for (i=0;i==4;i++) {
			if (grafo->matriz[nodo_origen][i]==1) {
				nodo = *grafo->nombres[i];
				nodo_origenl = *grafo->nombres[nodo_origen];
				printf("%d es vecino de %d",nodo_origenl, nodo);
			}
	}
}

He hecho una matriz de adyacencia que marca 1 si estan conectados y 0 si no lo estan, luego pido un nodo de origen, y hago un for para que recorra toda la matriz de adyacencia y si encuentra uno que sea 1 que lo escriba en pantalla, pero no funciona...

Eso es para buscar los vecinos, no para el camino..

Alguna ayuda?

La idea debe ser buscar recursivamente, por ensayo y error, hasta encontrar el punto final de la ruta.

Te paras en el primer nodo, y luego entre todos los (n-1) nodos restantes hay algunos que se conectan con el primero (y otros que quizá no). Digamos que hay M1 nodos que se conectan con el primero, entonces debes explorar todas estas M1 posibilidades. Cada un de ellos a su vez genera nuevas posibilidades de conectarse con un tercer nodo y así sucesivamente.

Pero a mí esta idea se me va pareciendo más a un árbol de búsqueda de múltiples ramas, que a una cola ....

Es cuestión de hacer un algoritmo en papel, ejecutarlo "a mano", y luego pasarlo a código de programación. Al final, tendrás un cierto número de soluciones al problema (suponiendo que hay una al menos), y elegirás la trayectoria con menos nodos como la más corta.

Voy a ver si al final de este día te preparo algo mejor y te lo envío. Ten en cuenta también que quizá tenemos zonas horarias diferentes tú y yo.

Y como comparo y guardo los nodos que estan conectados?

He ido probando cosas pero nada... alguna ayuda?

Una duda, como se pasan los structs por referencia?

Hola Marrison, estuve leyendo sobre el tema del algortimo Dijkstra y me pareció muy interesante. Voy a publicar hoy un post sobre el tema y te invitaré a consultarlo.