Help grafi

di il
4 risposte

Help grafi

Come posso fare per implementare un grafo per rappresentare n citta ognuna con delle relative informazioni_?grazie

4 Risposte

  • Re: Help grafi

    Potresti crearti un array che memorizzerà i nodi del grafo, i quali consisteranno in oggetti che memorizzano informazioni relativi alla citta è un puntatore alla loro lista di adiacenza: cioè dato un oggetto x dell'array hai il puntatore ad una lista di oggetti, ognuno dei quali contiene un puntatore ad un nodo y (tale che c'è un arco da x a y ed ovviamente è contenuto nell'array dei nodi) e un puntatore al successivo oggetto della lista.

    Oppure puoi rappresentare l'insieme dei nodi sempre in un array mentre per memorizzare la struttura del grafo ti appoggi ad una matrice, dove le intestazioni di riga e colonna rappresentano i nodi e un marcatore in una casella indica la presenza di un arco tra i due nodi rappresentati.

    (A livello di efficienza è molto meglio la prima)

    Spero di averti dato una idea chiara
  • Re: Help grafi

    Io ho provato a fare questo tipo di implementazione xhe prevede ,oltre a cio che hai detto tu, anche un vettore di record che contiene le informazioni(nome,tempo,soldi) di ogni citta..secondo te questo tipo di implementazione e efficiente, considerando il fatto che devo fare molte operazioni su queste citta(aggiunta\rimozione di collegamenti,aggiunta\rimozione di citta etc..) .In pratica ogni volta che in input do il nome di una citta, devo effettuare una ricerca in questo vettore di record per cercare la sua chiave corrispondente,perche nella lista delle adiacenze non avro i nomi delle citta ma degli interi che sono appunto le chiavi di queste citta..grazie

    typedef struct {
    char *nome;
    int soldi;
    int tempo;
    }rec;

    typedef struct edge {
    int key;
    int peso;
    struct edge *next;
    } edge;

    typedef struct graph {
    int nv; /* numero di vertici del grafo */
    edge **adj; /* vettore con le liste delle adiacenze */
    rec *A ; //vettore di record che contiene le informazioni
    } graph;



    graph *crea_grafo(int n)
    {
    graph *G; int i;
    G = (graph*)malloc(sizeof(graph));

    if (G==NULL) printf("\n ERRORE: impossibile allocare memoria per il grafo \n");
    else
    {
    G->adj = (edge**)malloc(n*sizeof(edge*));
    G->A=(rec*)malloc(n*sizeof(rec));
    if ((G->adj==NULL) && (n>0))
    {
    printf("\n ERRORE: impossibile allocare memoria per la lista del grafo \n");
    free(G);
    G=NULL;
    }
    else
    {
    G->nv = n;
    for (i=0; i<n; i++)
    G->adj=NULL;
    for (i=0; i<n; i++)
    {
    printf("\n Inserire il nome della %d citta'",i+1);
    scanf("%s",&G->A.nome);
    }
    }
    }
    return(G);
    }
  • Re: Help grafi

    nella lista delle adiacenze non avro i nomi delle citta ma degli interi che sono appunto le chiavi di queste citta
    Io nelle liste di adiacenza metterei oggetti con 2 attributi: citta' e next;

    citta': sara' un puntatore all'oggetto corrispondente (cioe' alla citta');
    next : puntatore all'oggetto successivo nella lista.

    eviterei quindi di mettere nelle liste di adiacenza degli interi che fungano da chiave per effettuare poi la ricerca nell'array, nel modo che ti illustrato hai direttamente l'accesso all'oggetto citta', senza fare poi una ricerca nell'array
  • Re: Help grafi

    Salve.qualcuno potrebbe dirmi come fare a inserire a cancellare un nodo da un grafo rappresentato con liste di adiacenza?il prof ha detto ke dobbiamo usare realloc per decrementare il numero dei nodi e poi bisogna aggiustare tutti i collegamenti..purtroppo non mi e molto chiaro il funzionamento della realloc e come va fatta tutta questa operazione...grazie
Devi accedere o registrarti per scrivere nel forum
4 risposte