Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
Creazione Matrice di Adiacenza da Grafo in C
Nuovo argomento   Rispondi    Indice del forum -> Programmazione
Precedente :: Successivo  
Autore Messaggio
NotFound
Comune mortale
Comune mortale


Registrato: 09/01/16 16:27
Messaggi: 1

MessaggioInviato: 09 Gen 2016 16:30    Oggetto: Creazione Matrice di Adiacenza da Grafo in C Rispondi citando

Salve a tutti. Sviluppando un progetto in linguaggio C, ho creato la lista di adiacenza del grafo per poterci poi lavorare su. Andando avanti mi sono accorto che necessito anche della matrice di adiacenza (al fine di utilizzare l'algoritmo di Floyd Warshall). Ho cercato tra le discussioni passate ma niente mi ha chiarito le idee. Come è strutturata la funzione per la creazione della matrice di adiacenza? Ho bisogno di definire nuovi tipi di dati? Posso eventualmente "tramutare" la mia funzione per la lista di adiacenza e renderla utile per l'acquisizione della matrice di adiacenza?

In due parole il funzionamento di questa parte del programma è che la prima funzione che vi posto, riconosce se abbiamo la necessità di inserire in lista uno oppure due vertici del grafo e agisce di conseguenza invocando la funzione giusta ("inserimento singolo" oppure "inserimento doppio"), reitera fino alla fine dell'inserimento del grafo nella lista. L'ultima funzione è quella per l'inserimento del grafo. Posto anche le definizioni dei tipi di dati che ho implementato.

So di chiedervi tanto,ho rimurginato parecchio sulla situazione ma non ne vengo a capo. Spero qualcuno possa aiutarmi! Grazie!

Codice:
/*Definizione del tipo di dato per i vertici del grafo*/
typedef struct vertice_grafo
{
   char nome[DIM_NOME];               /*Nome del vertice*/
   struct vertice_grafo *vertice_succ_p;         /*Puntatore al vertice successivo*/
   struct arco_grafo *lista_archi_p;         /*Puntatore alla testa della lista degl'archi*/
   colore_t colore;               /*Variabile contenente il colore del vertice*/
   int distanza,                  /*Variabile contenente la distanza del vertice dalla sorgente*/
       inizio,                  /*Variabile per la visita in profondità*/
       fine;                  /*Variabile per la visita in profondità*/
   struct vertice_grafo *padre_p;            /*Puntatore al vertice padre*/
} vertice_t;

/*Definizione tipo di dato per gli archi*/
typedef struct arco_grafo
{
   struct vertice_grafo *vertice_adiac_p;            /*Puntatore al vertice di destinazione puntato dall'arco*/
   struct arco_grafo *arco_succ_p;               /*Puntatore all'arco successivo*/
} arco_t;

/*Definizione tipo di dato per gli elementi della coda (per la visita in ampiezza)*/
typedef struct elem_coda
{
   struct vertice_grafo *elem;         /*Puntatore all'elemento del grafo*/
   struct elem_coda *elem_succ_p;         /*Puntatore all'elemento successivo della coda*/
} elem_coda_t;

/*Definizione del nuovo tipo di dato per gli elementi della pila (per visita in profondità e per memorizzare i padri)*/
typedef struct elem_pila
{
   char nome[DIM_NOME];               /*Nome del vertice (vertice padre)*/
   struct elem_pila *elem_succ_p;            /*Puntatore all'elemento successivo*/
} elem_pila_t;



Codice:
/*Definizione della funzione per la ricerca della presenza o meno dei vertici*/
vertice_t *ricerca_vertici(vertice_t *p,
            char nome_vertice_origine[DIM_NOME],
            char nome_vertice_destinazione[DIM_NOME])
{
   /*Definizione delle variabili locali della funzione*/
   int origine = 1;
   char evento = 'b';                        /*Variabile che indicherà l'evento*/
   vertice_t *vertice_origine = NULL,                  /*Puntatore all'elemento d'origine*/
            *vertice_destinazione = NULL,            /*Puntatore all'elemento di destinazione*/
            *temp;                     /*Puntatore d'appoggio temporaneo*/

   /*Legenda "evento"
   'a' = entrambi i vertici sono presenti in lista
   'b' = nessuno dei due vertici è presente in lista
   'c' = solo il vertice d'origine è presente in lista
   'd' = solo il vertice di destinazione è presente in lista*/   

   /*Memorizzo la testa della lista*/
   temp = p;

   /*Se la lista non è vuota*/
   if (p != NULL)
   {
      /*Istruzione While che scorre la lista*/
      while ((p != NULL) &&
            (evento == 'b'))
      {
         /*Controllo se l'elemento corrente risulta essere la vertice d'origine*/
         if (strcmp(p->nome, nome_vertice_origine) == 0)
         {
            /*Memorizzo la vertice d'origine*/
            vertice_origine = p;
            /*Cambio di evento*/
            evento = 'c';
            /*Vado alla ricerca della vertice di destinazione*/
            while ((p != NULL) &&
                  (evento == 'c'))
            {
               if (strcmp(p->nome, nome_vertice_destinazione) == 0)
               {
                  /*Memorizzo il vertice di destinazione*/
                  vertice_destinazione = p;
                  /*Cambio evento*/
                  evento = 'a';
               }
               else
                  /*Aggiorno il puntatore e scorro la lista*/
                  p = p->vertice_succ_p;
            }
         }
         /*Altrimenti controllo se l'elemento corrente risulta essere il vertice di destinazione*/
         else if (strcmp(p->nome, nome_vertice_destinazione) == 0)
         {
            /*Memorizzo il vertice di destinazione*/
            vertice_destinazione = p;
            /*Cambio di evento*/
            evento = 'd';
            /*Vado alla ricerca del vertice d'origine*/
            while ((p != NULL) &&
                  (evento == 'd'))
            {
               if (strcmp(p->nome, nome_vertice_origine) == 0)
               {
                  /*Memorizzo il vertice d'origine*/
                  vertice_origine = p;
                  /*Cambio di evento*/
                  evento = 'a';
               }
               else
                  /*Aggiorno il puntatore e scorro la lista*/
                  p = p->vertice_succ_p;
            }
         }
         /*Se non è nessuna deli due*/
         else
            /*Aggiorno il puntatore e scorro la lista*/
            p = p->vertice_succ_p;
      }
   }
   /*Sezione di controllo dell evento ed invocazione della corrispettiva funzione*/
   switch (evento)
   {
      case 'a':
      /*Invoco la funzione creazione dell'arco */
      inserimento_arco(vertice_origine,
               vertice_destinazione);

      break;
      
      case 'b':
      temp = inserimento_doppio(temp,
               nome_vertice_origine,
               nome_vertice_destinazione);
      break;

      case 'c':
      origine = 1;
      temp = inserimento_singolo(temp,
               vertice_origine,
               nome_vertice_destinazione,
               origine);
      break;

      case 'd':
      origine *= 0;
      temp = inserimento_singolo(temp,
               vertice_destinazione,
               nome_vertice_origine,
               origine);
      break;
   }
   return (temp);
}


Codice:
/*Definizione della funzione per l'inserimento di un solo elemento nella lista dei vertici*/
vertice_t *inserimento_singolo(vertice_t *p,
               vertice_t *elem_trovato,
               char nome_vertice[DIM_NOME],
               int origine)
{
   /*Definizione delle variabili locali della funzione*/
   vertice_t *nuovo_p,                     /*Puntatore al nuovo elemento*/
         *corr_p;                  /*Puntatore d'ausilio per scorrere la lista*/

   nuovo_p = corr_p = p;
   /*Scorro la lista fino ad arrivare all'ultimo elemento*/
   while (nuovo_p != NULL)
   {
      corr_p = nuovo_p;
      nuovo_p = nuovo_p ->vertice_succ_p;
   }
   /*Alloco spazio per il nuovo elemento*/
   nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
   /*Inserisco il nome*/
   strcpy(nuovo_p->nome, nome_vertice);
   nuovo_p->lista_archi_p = NULL;
   /*Concateno il nuovo elemento col resto della lista*/
   corr_p->vertice_succ_p = nuovo_p;
   /*Invoco la funzione per la creazione degli archi per il grafo*/
   inserimento_arco(elem_trovato,
            nuovo_p);
   return (p);
}


Codice:
/*Definizione della funzione per l'inserimento di entrambi i vertici nella lista dei vertici*/
vertice_t *inserimento_doppio(vertice_t *p,
            char nome_vertice_origine[DIM_NOME],
            char nome_vertice_destinazione[DIM_NOME])
{
   /*Definizione delle variabili locali della funzione*/
   vertice_t *nuovo_p,                     /*Puntatore al nuovo elemento*/
            *seguente_p,               /*Puntatore all'elemento seguente*/
            *corr_p;               /*Puntatore d'ausilio per scorrere la lista*/

   /*Se la lista dovesse esser vuota*/
   if (p == NULL)
   {
      /*Creo la testa della lista*/
      nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
      /*Inserisco il nome*/
      strcpy(nuovo_p->nome, nome_vertice_origine);
      nuovo_p->lista_archi_p = NULL;
      /*Il nuovo elemento è la testa*/
      p = nuovo_p;
      /*Creo l'elemento seguente*/
      seguente_p = (vertice_t *)malloc(sizeof(vertice_t));
      /*Inserisco il nome*/
      strcpy(seguente_p->nome, nome_vertice_destinazione);
      seguente_p->lista_archi_p = NULL;
      /*Concateno l'elemento seguente*/
      p->vertice_succ_p = seguente_p;
   }
   /*Se non vuota*/
   else
   {
      nuovo_p = corr_p = p;
      /*Scorro la lista fino ad arrivare all'ultimo elemento*/
      while (nuovo_p != NULL)
      {
         corr_p = nuovo_p;
         nuovo_p = nuovo_p->vertice_succ_p;
      }
      /*Creo il nuovo elemento*/
      nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
      /*Inserisco il nome*/
      strcpy(nuovo_p->nome, nome_vertice_origine);
      nuovo_p->lista_archi_p = NULL;
      /*Concateno il nuovo elemento col resto della lista*/
      corr_p->vertice_succ_p = nuovo_p;

      /*Creo l'elemento seguente*/
      seguente_p = (vertice_t *)malloc(sizeof(vertice_t));
      /*Inserisco il nome*/
      strcpy(seguente_p->nome, nome_vertice_destinazione);
      seguente_p->lista_archi_p = NULL;
      /*Concateno l'elemento seguente*/
      nuovo_p->vertice_succ_p = seguente_p;
   }

   /*Invoco la funzione per la creazione degl'archi per il grafo)*/
   inserimento_arco(nuovo_p,
            seguente_p);      
   return (p);
}



Codice:
/*Definizione della funzione per la creazione degli archi*/
void inserimento_arco(vertice_t *vertice_origine,
               vertice_t *vertice_destinazione)
{
   /*Definizione delle variabili locali della funzione*/
   int controllo = 1 ;                  /*Variabile di controllo generale*/
   arco_t *arco,                     /*Puntatore al nuovo arco*/
      *arco_corr;                  /*Puntatore d'ausilio per scorrere la lista degl'archi*/

   if (vertice_origine->lista_archi_p == NULL)
   {
      /*Creo l'arco*/
      arco = (arco_t *)malloc(sizeof(arco_t));
      /*Lo inserisco nella lista secondaria*/
      vertice_origine->lista_archi_p = arco;
      /*Inserisco il vertice adiacente*/
      arco->vertice_adiac_p = vertice_destinazione;
      /*Non ho un arco successivo*/
      arco->arco_succ_p = NULL;

      arco = arco_corr = vertice_origine->lista_archi_p;
      /*Scorro la lista secondaria degl'archi*/
      while ((arco != NULL) &&
            (controllo == 1))
      {
         arco_corr = arco;
         /*Controllo se l'arco che voglio inserire è già presente*/
         if (strcmp(arco->vertice_adiac_p->nome, vertice_destinazione->nome) == 0)
         {
            controllo *= 0;
         }
         /*Altrimenti*/
         else
            /*Scorro la lista*/
            arco = arco->arco_succ_p;
      }
      /*Testo la variabile controllo per constatare se poter inserire o meno l'arco*/
      if (controllo == 1)
      {
         /*Creo l'arco*/
         arco = (arco_t *)malloc(sizeof(arco_t));
         /*Lo inserisco come ultimo elemento*/
         arco_corr->arco_succ_p = arco;
         /*Definisco il vertice adiacente*/
         arco->vertice_adiac_p = vertice_destinazione;
         /*Non ho archi successivi*/
         arco->arco_succ_p = NULL;

      }
   }
}
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 11 Gen 2016 11:37    Oggetto: Rispondi

Se proprio ti è necessario creare la matrice (... hai già la lista...) allora devi semplicemente creare un'array di booleani bidimensionale NxN (dove N è il numero di nodi), mettere a false tutti i valori e scorrere la lista delle adiacenze dall'inizio alla fine, mettendo a true il valore corrispondente per ogni arco.
Top
Profilo Invia messaggio privato HomePage
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Programmazione Tutti i fusi orari sono GMT + 1 ora
Pagina 1 di 1

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi