Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - helppppppp GRAFI
Forum - C/C++ - helppppppp GRAFI

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
hawks (Normal User)
Newbie


Messaggi: 11
Iscritto: 10/11/2012

Segnala al moderatore
Postato alle 22:05
Lunedì, 12/11/2012
Ciao a tutti  sto studiando i grafi ed e un argomento un po ostico adesso non so se ho avuto un approccio sbagliato ma forse si comunque ho dei problemi .
Per la parte teorica no problem ma quando passiamo ala pratica no ci siamo.
sappiamo che ci sono due modi per rappresentare un grafo matrici e liste.
Io sto affrontando le liste ma ho un sacco di dubbi intanto in linea generale cioe se abbiamo un grafo generico composto da n nodi e dobbiamo rappresentarlo con le liste posto un allegato(1) per rendere l'idea.
Poi nel caso particolare cioe' quando ho una traccia specifica che  posto anche riesco ad individuare le classi in gioco pero ho delle difficolta su come costruire le strutture. allegato (2)


hawks ha allegato un file: ESEMPIO GRAFO allegato1.jpg (62099 bytes)
Clicca qui per guardare l'immagine
PM Quote
Avatar
hawks (Normal User)
Newbie


Messaggi: 11
Iscritto: 10/11/2012

Segnala al moderatore
Postato alle 22:13
Lunedì, 12/11/2012
spero di essere stato chiaro nell'esposizione spero che mi darete delle dritte grazie a tutti in anticipo

PM Quote
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Segnala al moderatore
Postato alle 10:38
Martedì, 13/11/2012
In effetti, no, non sei stato molto chiaro. Magari potresti usare la punteggiatura ogni tanto e, chessç, forse terminare le frasi :D :D

Tu stai usando la rappresentazione di Cormen, con un array indicizzato per vertice in cui ogni cella contiene una lista singolarmente linkata di tutti i vertici (nodi) vicini. E la tua implementazione è più o meno corretta, quindi non riesco a capire quale sia il tuo dubbio, dato che non hai formualto nessuna domanda esplicita.

Codice sorgente - presumibilmente C++

  1. #define N <dimensione del grafo>
  2.  
  3. struct Node {
  4.     Computer data;
  5.     struct Node* next;
  6. }
  7.  
  8. typedef struct Node* NodeList;
  9.  
  10. NodeList graph[N];
  11. int nodeIndex = 0;
  12.  
  13. NodeList addNode(Computer data) {
  14.     if (nodeIndex >= N) { return NULL; }
  15.  
  16.     nodeIndex++;
  17.     graph[nodeIndex] = (NodeList)malloc(sizeof(Node));
  18.     graph[nodeIndex]->data = data;
  19.     graph[nodeIndex]->next = NULL;
  20.     return graph[nodeIndex];
  21. }
  22.  
  23. void addArc(NodeList n1, NodeList n2) {
  24.     if (n1 == NULL || n2 == NULL) return;
  25.     n1->next = listInsert(n1->next, n2);
  26. }
  27.  
  28. int arcExists(NodeList n1, NodeList n2) {
  29.     if (n1 == NULL || n2 == NULL) return 0;
  30.  
  31.     for (NodeList temp = n1->next; temp != NULL; temp = temp->next) {
  32.         if (temp == n2) return 1;
  33.     }
  34.     return 0;
  35. }


Ultima modifica effettuata da Il Totem il 13/11/2012 alle 10:41
PM Quote
Avatar
hawks (Normal User)
Newbie


Messaggi: 11
Iscritto: 10/11/2012

Segnala al moderatore
Postato alle 17:55
Mercoledì, 14/11/2012
ciao sicuramente mi sono espresso male vedro' di rimediare.
Allora diciamo che ho cercato anche in rete del materiale per capire come si implementano i grafi, ma senza successo nel senso che, mi sono incasinato sempre di piu.
Ti posto questo sito http://www.etantonio.it/IT/Universita/2anno/FondamentiInfo ...
qui con tutti quei arc_node, arc_list etc... non ci ho capito niente.
Come individuo nella mia traccia a parte i nodi che sono i pc ma le altre cose come archi etc...????
Come devo procedere??Tu che sei un esperto dammi una mano per favore

PM Quote
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Segnala al moderatore
Postato alle 19:21
Mercoledì, 14/11/2012
Effettivamente quegli appunti sono scritti da cani, e non mi riferisco solo al codice, ma anche all'italiano stentoreo e pieno di anacoluti. Quindi ti suggerisco ti studiare da qualche altra parte. Purtroppo anche il mio prof di algoritmi e strutture dati era un casinista, quindi non ti posso consigliare i suoi lucidi.

Comunque, dalla pazzia delirante di quel codice sono riuscito a capire l'idea generale. Il punto è che usa il termine "node" sia per indicare i nodi di una lista, sia per indicare i nodi di un grafo. Dato che la rappresentazione del grafo usa le liste di adiacenze, la sovrapposizione dei nomi genera qualche conflitto mentale.
- Arc_Node indica il nodo della lista che contiene gli archi. La classe viene quindi usata anche per rappresentare l'arco stesso. Arc_Destination è la testa dell'arco, mentre Arc_Attribute è l'etichetta applicata all'arco, oppure il suo peso se si tratta di dati numerici. Usare un puntatore a void piuttosto che dei template mi sembra anacronistico.
- Arc_List è una lista linkata i cui elementi sono istanze di Arc_Node. Contiene metodi per inserire, rimuovere e cercare elementi nella lista.
- Vertex_Node indica il nodo della lista che contiene i vertici (o nodi del grafo). Rappresenta il singolo elemento della lista di adiacenza. Contiene quindi la lista di archi che partono da questo vertice (sottoforma di Arc_List), un puntatore al prossimo Vertex_Node nella lista di adiacenza, un contatore di rifermenti e l'etichetta del nodo Vertex_Attribute.
- Graph (o Vertex_List) rappresenta il grafo mediante una lista di adiacenza, ossia un lista di elementi Vertex_Node, i quali contengono i vertici del grafo.

La lista di adiacenza contiene quindi tutti i vertici del grafo. A sua volta, ogni vertice contiene una lista di archi uscenti da esso. Accedendo alla testa di un arco si ottiene il secondo estremo dell'arco.

PM Quote
Avatar
hawks (Normal User)
Newbie


Messaggi: 11
Iscritto: 10/11/2012

Segnala al moderatore
Postato alle 9:58
Giovedì, 15/11/2012
Grazie per la tua spiegazione esaustiva .
Nel caso del mio problema quindi devo individuare una classe computer costituita da un vettore di struCt  unA CLASSE HARD DISK
CHE RAPPRESENTA LA LISTA DEGLI HARD DISK E UNA CLASSE LISTA_ad che rappresenta gli adiacenti ad ogni nodo

PM Quote
Avatar
Bonny (Member)
Expert


Messaggi: 437
Iscritto: 24/04/2009

Segnala al moderatore
Postato alle 10:07
Giovedì, 15/11/2012
Se ti interessa qui ho raccolto una collezione di esempi su l'implementazione e le varie operazioni sui grafi.
http://www.lucabonaldo.it/collezione-esercizi-sui-grafi/

Questo è un progetto molto esaustivo. Il progetto consiste nella realizzazione di un sistema per la gestione e la simulazione di una rete di interconnessioni di una compagnia aerea. Gli aeroporti sono i nodi di un gravo creato mediante liste di adiacenza. Leggi la relazione e vedrai che ti aiuterà a capire. Il codice sorgente è secondario..
http://www.lucabonaldo.it/netairport/

Spero di esserti stato d'aiuto.

PM Quote
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Segnala al moderatore
Postato alle 10:21
Venerdì, 16/11/2012
Non siete molto ferrati con i nomi, eh? Non puoi chiamare HardDisk una classe che rappresenta una lista di hard disk; semmai HardDisk rappresenterà un singolo hard disk, mentre un'altra classe, ad esempio HardDiskList, conterrà la lista.
Io non chiamerei LISTA_ad la lista di adiacenza, perché il nome non indica la funzione ma l'essenza. Sarà piuttosto una lista di vertici, quindi VertexList o ComputerList dato che i vertici contengono computer. Poi la variabile che effettivamente conterrà tale lista la potrai chiamare listaAd.

PM Quote
Avatar
hawks (Normal User)
Newbie


Messaggi: 11
Iscritto: 10/11/2012

Segnala al moderatore
Postato alle 15:59
Venerdì, 16/11/2012
Un compilatore buono e gratuito per c++ che nn sia dev c++

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo