[c] Grafi,matrici di adiacenza e percorsi

[Darecon]

Salve a tutti, ho un piccolo problema.

Ho una matrice di adiacenza creata da un grafo, nel formato:


0 1 0 0 0
0 1 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 1

(ovviamente questo e' solo un esempio, ne ho molte altre)
e vorrei verificare se 2 nodi sono connessi, anche se non direttamente, esempio, il nodo 1 e' connesso al 2, il nodo 2 e' connesso al 3, di conseguenza indirettamente il nodo 1 e' connesso al nodo 3.

Come fare a verificare questo?

Grazie mille.

[fero86]

assolutamente non testato:

const int MatrixSize = 5;
bool Matrix[MatrixSize][MatrixSize];

bool Connected(int iSource, int iDestination)
{
if (Matrix[iSource][iDestination])
{
return true;
}
for (int i = 0; i < MatrixSize; i++)
{
if (Matrix[iSource][i])
{
if (Connected(i, iDestination))
{
return true;
}
}
}
return false;
}

[:.Blizzard.:]

Puoi utilizzare la DFS-Visit a partire da uno dei due nodi ed esprimi il codice in funzione del secondo nodo immesso in input. Così facendo sai se sono connessi fra di loro e ne conosci anche il cammino minimo necessario per raggiungerlo.



http://en.wikipedia.org/wiki/Depth-first_search

Qui invece un po' di materiale in italiano :

http://www.cs.unicam.it/merelli/algoritmi06/%5B13%5DalgoritmiSuGrafi.pdf

[british]

Ti propongo un'idea alternativa, non so se sia corretta nè eventualmente migliore ma mi stuzzicava.

Potresti considerare la matrice come generata da una relazione binaria e farne la chiusura transitiva. A questo punto per controllare se tra due nodi (i,j) del grafo originario esisteva un qualche percorso dovresti solo controllare che ci sia un uno nella posizione (i,j) della matrice transitiva.

ciao!

british

[Darecon]

Alla fine ho risolto usando: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

che mi ha semplificato la vita per quello che dovevo fare io, grazie a tutti dei consigli.. :)