Precedente :: Successivo |
Autore |
Messaggio |
NotFound Comune mortale
Registrato: 09/01/16 16:27 Messaggi: 1
|
Inviato: 09 Gen 2016 16:30 Oggetto: Creazione Matrice di Adiacenza da Grafo in C |
|
|
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 |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11568 Residenza: Tokelau
|
Inviato: 11 Gen 2016 11:37 Oggetto: |
|
|
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 |
|
|
|
|
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
|
|