PDA

Visualizza la versione completa : [C] Calcolo complessitÓ algoritmo che calcola la distanza tra nodi un grafo


Laurettam
05-03-2011, 13:44
Salve, ho cercato in varie discussioni come si calcolasse la complessitÓ di un algoritmo ma non son riuscita a capire la complessitÓ del mio :dh˛:
Il problema era questo: Dato un grafo orientato G di n nodi ed m lati, e due nodi s e u di G. determinare il numero di nodi di G raggiungibili da s che si trovano alla stessa distanza da s e da u. Valutarne la complessitÓ in funzione di n e m.

L'algoritmo Ŕ il seguente:
int main()
{
int u;
int s = u = 0;
listPtr distanceFromS[MAX_GRAPH_SIZE] = {0};
listPtr distanceFromU[MAX_GRAPH_SIZE] = {0};
for(short i = 0; i < MAX_GRAPH_SIZE; ++i)
nodes[i] = -1;
resetRoads();

graphCreateFromEdges();

printf("Insert s and u vertices: ");
scanf("%d %d", &s, &u);
graphPath(s);
for(short i = 0; nodes[i] != -1; ++i)
{
if(nodes[i] != s)
{
graphOrientedPaths(s, s, nodes[i]);
printf("\nDal nodo s:%d al nodo %d\n", s, nodes[i]);
resetSavedArr();
for(short j = 0; j < ROAD_LENGHT && graphRoads[j][0] != -1; ++j)
{
verifyRoad(j, graphRoads[j], s, nodes[i]);
}
unsigned short cont = 0;
for(short k = 0; k < ROAD_LENGHT; ++k)
{
if(savedRoads[k][0] == -1)
continue;
printf("Percorso:");
for(short l = 0; l < ROAD_LENGHT && savedRoads[k][l] != -1; ++l)
{
++cont;
printf(" %d ", savedRoads[k][l]);
//printf("\n");

}
printf("\nDistanza:%d", cont - 1);
listPush(&distanceFromS[nodes[i]], (cont - 1));
cont = 0;
printf("\n");
}

resetRoads();
}
}

for(short i = 0; nodes[i] != -1; ++i)
{
if(nodes[i] != u)
{
graphOrientedPaths(u, u, nodes[i]);
//printRoads();
printf("\nDal nodo u:%d al nodo %d\n", u, nodes[i]);
resetSavedArr();
for(short j = 0; j < ROAD_LENGHT && graphRoads[j][0] != -1; ++j)
{
verifyRoad(j, graphRoads[j], u, nodes[i]);
}
unsigned short cont = 0;
for(short k = 0; k < ROAD_LENGHT; ++k)
{
if(savedRoads[k][0] == -1)
continue;
printf("Percorso:");
for(short l = 0; l < ROAD_LENGHT && savedRoads[k][l] != -1; ++l)
{
++cont;
printf(" %d ", savedRoads[k][l]);
//printf("\n");
}
printf("\nDistanza:%d", cont - 1);
listPush(&distanceFromU[nodes[i]], (cont - 1));
cont = 0;
printf("\n");
}

resetRoads();
}
}

printf("\nNumero di nodi da s e da u: %d.", compareLists(distanceFromS, distanceFromU));

fflush(stdin);
getchar();
return 0;
}

Non riesco proprio a capire come fare :( vi ringrazio in anticipo per l'aiuto..

Loading