PDA

Visualizza la versione completa : [C] dfs per matrice adiacenza


MrX87
16-01-2009, 18:38
Ciao ragazzi, stavo cercando un modo per implementare la funzione per la gestione della visita in profondità in un grafo orientato pesato; ho visto alcune implementazioni di questa funzione ma sono tutte basate su liste di adiacenza ricorsive! mentre a me serviva usarla sulla matrice di adiacenza!
grazie

PeppePes88
16-01-2009, 20:39
n un grafo orientato pesato


che intendi con grafo orientato PESATO?

MrX87
16-01-2009, 22:12
bhè grafo orientato pesato è un grafo orientato dove ogni arco ha un peso particolare!
http://home.dei.polimi.it/malucell/didattica/esercizi/figure/12-04-3.gif

PeppePes88
17-01-2009, 00:19
Scusa non puoi semplicemente scorrere la matrice di incidenza ,in modo da ottenere per ogni nodo con quale nodo è collegato??
dove al posto degli uno hai messo il peso dell'arco???

PeppePes88
17-01-2009, 12:31
guarda un po se il codice che posto è quello che ti interessa a te, o almeno ti puo dare una mano...



#include <stdio.h>
#include <stdlib.h>

#define n_nodi 3

void stampa ( int matrice_incidenza [][n_nodi]);

int main () {

int matrice_incidenza[n_nodi][n_nodi] ={0};

matrice_incidenza[0][1] = 1; // metto gli archi e il loro valori
matrice_incidenza[0][2] = 2;
matrice_incidenza[1][2] = 3;
matrice_incidenza[1][0] = 4;
matrice_incidenza[2][0] = 5;
matrice_incidenza[2][1] = 6;

stampa(matrice_incidenza);

return 0;

}


void stampa( int matrice_incidenza[][n_nodi]) {

int i = 0;
int j = 0;

printf("Matrice incidenza pesata: \n");

for (j = 0; j <n_nodi; j++) {
for (i = 0; i < n_nodi; i++)
printf("[%d] ", matrice_incidenza[i][j]);
printf("\n");
}

printf("Grafo :\n");

for (j = 0; j <n_nodi; j++) {
printf("[%d]\n", j);
for (i = 0; i < n_nodi; i++)
if ( matrice_incidenza[j][i] != 0)
printf("-- %d --> [%d]\n", matrice_incidenza[j][i], i);
printf("\n");
}
}


l'output di questo codice è :

Matrice incidenza pesata:
[0] [4] [5]
[1] [0] [6]
[2] [3] [0]

Grafo :
[0] //nodo da cui partono gli archi
-- 1 --> [1]
-- 2 --> [2]

[1]
-- 4 --> [0]
-- 3 --> [2]

[2]
-- 5 --> [0]
-- 6 --> [1]

MrX87
17-01-2009, 12:53
si okay...questo è il codice per caricare una matrice di ADIACENZA con gli archi pesati, e va bene, ma a me interessava una funzione che fosse in grado di effettuare una visita in profondità (dfs) su una matrice di adiacenza!

Loading