|
|||||||
|
|
|
 |
|
|
Strumenti |
10-02-2006, 08:22
|
#1 |
|
Senior Member
Iscritto dal: May 2003
Messaggi: 1113
|
[C] Grafi - Trovare un cammino
raga qualcuno di voi ha un algoritmo per verificare se esiste un cammino tra due nodi di un grafo?
magari un algoritmo che si possa applicare ad un grafo costruito con matrice di adiacenza e/o con lista di adiacenza..
__________________
| Athlon XP Barton 3000+ | CoolerMaster HAC-V81 | ASUS A7N8X DELUXE v2.0 | 2*256 PC3200 + 1*512 PC3200 = 1GB DDR400| ATI Radeon 9250 | HD 80Gb Maxtor SATA | Ali Q-TEC 550W Dual Fan GOLD PFC |
|
|
|
10-02-2006, 09:08
|
#2 |
|
Member
Iscritto dal: May 2005
Messaggi: 80
|
Prova a cercare su google "algoritmo di chiusura transitiva", che in inglese dovrebbe essere "transitive enclosure".
Lavora su matrici nelle quali m[i][j]==1 significa che c'è un arco tra il nodo i e il nodo j (sono le matrici di adiacenza?). Non te lo posso scrivere perché non me lo ricordo  Ciao |
|
|
|
|
10-02-2006, 09:48
|
#3 |
|
Senior Member
Iscritto dal: Nov 2004
Città: $HOME
Messaggi: 1213
|
io lo avevo fatto da zero tramite liste di adiacenza (in modo da avere una simil-matrice completamente dinamica) e alla fine della "scansione" visualizzava il cammino esistente.
l'algoritmo e' piuttosto grezzo..lho fatto in 1h e 30min durante l'esame di algoritmi e strutture dati lab! se riesco a recupararlo lo posto.
__________________
Last.fm: My Profile / GamerTag XBL: Martcus / Flickr / deviantArt iBook 12'' / MacBook Pro 13'' / iPhone 3G 16GB Black / iPod 5G 30GB / iPod Nano 2G 4GB |
|
|
|
|
|
| Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 17:01.
