codice:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define TRUE 1
#define FALSE 0
typedef short int Bool;
//------GRAFO----------
typedef struct vert
{
int vertice;
struct vert *next;
}Vert;
typedef Vert* pVert;
pVert *Grafo;
Bool *Visitato;
int CreaGrafoOrientato();
void Distanze(int n);
int AmpiezzaModificata(int v,int buf[]);
//---------------------
//-----------CODA--------------
typedef struct ele
{
int vertice;
struct ele *next;
}Ele;
typedef Ele* pEle;
void AddCoda(pEle *davanti,pEle* dietro,int item);
int DelCoda(pEle *davanti,pEle* dietro);
//-----------------------------
//FUNZIONI AUSILIARIE
void FreeMem(int n); //libera la memoria delle liste di adiacenza
pVert Inserisci(pVert t); //inserisce un lato orientato
void *myalloc(int n);
int Menu();
main()
{
int n=0,choice;
do
{
choice=Menu();
if(choice=='1'||choice=='2'||choice=='3')
switch(choice)
{
case '1': //crea
clrscr();
if(n) FreeMem(n);
n=CreaGrafoOrientato();
Visitato=(Bool*)myalloc(n*sizeof(Bool));
printf("\nPremi un tasto.");
getch();
break;
case '2': //Nodi a distanza massima per ogni nodo
clrscr();
if(n) Distanze(n);
else printf("Crea il grafo prima!!!");
printf("\nPremi un tasto.");
getch();
break;
default: //termina
clrscr();
printf("Arrivederci!!");
}
}while(choice!='3');
if(n) FreeMem(n);
free(Grafo);
fflush(stdin);
getchar();
}
int Menu()
{
//stampa il menu'
clrscr();
printf("\n\t\t\tMENU");
printf("\n\n\t\t(1)Crea il grafo orientato\n\n");
printf("\t\t(2)Nodi a distanza massima\n\n");
printf("\t\t(3)Termina\n");
return getch();
}
void *myalloc(int n)
{
void *p=malloc(n);
if(!p)
{
printf("\nErrore malloc!!");
fflush(stdin);
getchar();
}
return p;
}
pVert Inserisci(pVert list,int i)
{
//inserisce un vertice nella lista di adiacenza di un'altro se esso non è già presente
pVert temp,prev,t;
prev=t=list;
while(t&&t->vertice!=i)//cerca il vertice memorizzando il precedente
{
prev=t;
t=t->next;
}
if(!t) //non c'era quindi possiamo inserire
{
temp=(pVert)myalloc(sizeof(Vert));
temp->next=NULL;temp->vertice=i;
if(!list) list=temp;//la lista era vuota
else prev->next=temp;//c'era almeno un elemento
}
return list;
}
int CreaGrafoOrientato(void)
{
//E' uguale a quella usata per creare i lati nei grafi non orintati dell'eserc precedente
//con la differenza che i lati sono orientati quindi la funzione inserisci viene
//chiamata una sola volta (per inserire il secondo vertice nella lista del primo)
int a,b,n,i;
do
{
printf("Introduci il numero di vertici del grafo (minimo uno),verranno "
"creati tutti i vertici con etichetta da zero al numero che hai specificato - 1:\n");
scanf("%d",&n);
}while(n<1);
Grafo=(pVert *)myalloc(n*sizeof(pVert));
for(i=0;i<n;i++) Grafo[i]=NULL;
printf("\nOra introduci i lati del grafo come coppie ordinate di vertici (prima il vertice di partenza dell'arco)\nPremi un tasto");
getch();
clrscr();
while(1)
{
clrscr();
printf("Introduci due interi separati da uno spazio"
"(uno dei valori uguale a -1 termina):\n");
scanf("%d %d",&a,&b);
if(a==-1||b==-1) break; //si vuole smettere di inserire lati
else if(a<0||a>n-1||b<0||b>n-1)//una coppia deve essere di vertici validi
{
printf("Uno o entrambi i vertici della coppia non appartengono al grafo!\n"
"Premi un tasto");
continue;
}
Grafo[a]=Inserisci(Grafo[a],b);//crea un lato orientato
}
return n;
}
void Distanze(int n)
{
//per ogni vertice stampa i vertici a distanza massima.Le distanze dei vertici da quello
//di partenza (ruolo svolto a tutno da tutti i vertici) sono memorizzate in 'buf' dalla
//funzione ampiezza modificata che rende anche il valore della distanza massima
int i,j,maxdist; //maxdist riceve il valore corrispondente alla distanza massima
int *buf=(int*)myalloc(n*sizeof(int));//viene riempito con le distanze
for(i=0;i<n;i++)
{
for(j=0;j<n;j++) {Visitato[j]=FALSE;buf[j]=-1;}//reinizializzazione dei vettori di supporto
maxdist=AmpiezzaModificata(i,buf);
if(maxdist) printf("Nodi a distanza massima(cioe' %d) da %d :\n",maxdist,i);
else printf("Nessun vertice e' raggiungibile da %d",i);
for(j=0;j<n;j++) if(buf[j]==maxdist) printf("%d ",j);//stampa i vertici dell'ultimo livello
printf("\n\n");
}
}
int AmpiezzaModificata(int v,int buf[])
{
/*Effettua una visita in ampiezza ma senza stampare nulla, soltanto classificando i nodi
visitati per distanza da v e memorizzando tali distanze in buf.la distanza massima+1
rimane memorizzata nella variabile livello alla fine della visita.
La divisione dei nodi per livello è realizzata dal ciclo while più interno.
Il primo livello è costiuito dai noi della lista di adiacenza di v,il secondo dai
nodi delle liste di adiacenza di ognuno di essi non ancora visitati,il terzo dai nodi
delle liste di adiacenza di questi ultimi non ancora visitati,e così via...
L'idea è di tenere aggionata una variabile aux che memorizzi l'ultimo vertice del
livello corrente.La prima volta aux coincide col vertice di partenza,la seconda con
l'ultimo vertice della sua lista di adiacenza,la terza con l'ultimo vertice della lista
di adiacenza dell'aux precedente,e così via..
Nel test del ciclo interno aux viene confrontato con 'v',cioè con l'ultimo vertice
estratto dalla coda (che non vi si trova più quindi).in altre parole il ciclo while
interno non fa che ritardare l'incremento di 'livello' a quando dalla coda viene
estratto aux,quando ciò avviene aux viene aggiornato con 'dietro->vertice',che è proprio
l'ultimo vertice non visitato della lista di aux (perchè v==aux è già stato estratto e i
suoi vertici adiacenti già accodati).
Il problema del primo confronto,che deve sempre avere v!=aux (altrimenti non si comincia
il ciclo) viene risolto dando a v un valore non accettabile per l'immissione dei vertici
del grafo quando lo si crea,cioè -1.
OSSERVAZIONE:'livello' viene incrementato una volta in più perchè l'algoritmo non
può sapere a priori di trovarsi all'ultimo livello,cioè che per l'ultimo aux estrarrà
dalla coda solo vertici con liste di adiacenza già visitate.
*/
pEle davanti,dietro;
int aux,livello=0;
pVert w;
davanti=dietro=NULL;
Visitato[v]=TRUE;
AddCoda(&davanti,&dietro,v);
v=-1;
while(davanti)//finchè la coda non è vuota
{
aux=dietro->vertice;//ultimo vertice del livello
livello++;
while(v!=aux)//finchè non hai estratto l'ultimo vertice del livello
{
v=DelCoda(&davanti,&dietro);
for(w=Grafo[v];w;w=w->next)
if(!Visitato[w->vertice])
{
buf[w->vertice]=livello;// memorizza il livello attuale
Visitato[w->vertice]=TRUE;//contrassegna come visitato
AddCoda(&davanti,&dietro,w->vertice);//accoda
}
}
}
return livello-1;//perchè livello viene necessariamente incrementato una volta in più
}
void FreeMem(int n)
{
//libera la memoria di tutte le liste di adiacenza
pVert temp,t;int i;
for(i=0;i<n;i++)
{
t=Grafo[i];
while(t)
{
temp=t;
t=t->next;
free(temp);
}
Grafo[i]=NULL;
}
}
void AddCoda(pEle *davanti,pEle* dietro,int item)
{
//Aggiunge a una coda implementata con una lista concatenata
//la coda con questa implementazione non ha limiti di spazio (tutta la memoria al limite)
pEle p=(pEle)myalloc(sizeof(Ele));
p->next=NULL;
p->vertice=item;
if(!*davanti) *davanti=p; //la coda era vuota
else (*dietro)->next=p;//c'era almeno un elemento
(*dietro)=p; //si aggiorna sempre dietro
}
int DelCoda(pEle *davanti,pEle* dietro)
{
//cancella da una coda implementata con una lista concatenata
int item;pEle temp;
if(!*davanti) return -1; //coda vuota
item=(*davanti)->vertice;
temp=(*davanti);
*davanti=(*davanti)->next;//cancellazione in testa
free(temp);
if(!*davanti) *dietro=NULL;//non è strettamente necessario perchè l'inserimento
//aggiorna sempre *dietro senza controllarlo
return item;
}
Rispondi quotando
