Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
- #define NumNodi 5
- struct lista
- {
- int val;
- struct lista *next;
- };
- typedef struct lista Lista;
- typedef Lista *TipoPila;
- struct coda
- {
- struct lista *primo;
- struct lista *ultimo;
- };
- typedef struct coda TipoCoda;
- typedef int TipoNodo;
- typedef TipoNodo TipoElemPila;
- typedef TipoNodo TipoElemCoda;
- struct Grafo
- {
- bool matr_adiacenza[NumNodi][NumNodi];
- };
- typedef struct Grafo *TipoGrafo;
- TipoGrafo InitGrafo()
- {
- TipoNodo i,j;
- TipoGrafo grafo;
- grafo = malloc(sizeof(struct Grafo));
- for(i = 0; i < NumNodi ; i++)
- for(j = 0 ; j < NumNodi ; j++)
- grafo->matr_adiacenza[i][j]=false;
- return grafo;
- }
- TipoGrafo DistruggeGrafo(TipoGrafo grafo)
- {
- free(grafo);
- return NULL;
- }
- TipoGrafo SvuotaGrafo(TipoGrafo grafo)
- {
- TipoNodo i, j;
- for(i = 0; i < NumNodi ; i++)
- for(j = 0 ; j < NumNodi ; j++)
- grafo->matr_adiacenza[i][j]=false;
- return grafo;
- }
- bool TestEsisteArco(TipoGrafo grafo, TipoNodo i, TipoNodo j)
- {
- return grafo->matr_adiacenza[i][j];
- }
- TipoGrafo InserArco(TipoGrafo grafo, TipoNodo i, TipoNodo j)
- {
- grafo->matr_adiacenza[i][j] = true;
- return grafo;
- }
- TipoGrafo ElimArco(TipoGrafo grafo, TipoNodo i, TipoNodo j)
- {
- grafo->matr_adiacenza[i][j]=false;
- return grafo;
- }
- void StampaGrafo(TipoGrafo grafo)
- {
- TipoNodo i,j;
- for(i=0;i<NumNodi;i++)
- {
- printf("%2d: ",i);
- for(j=0;j<NumNodi;j++)
- {
- if(TestEsisteArco(grafo,i,j))
- printf(" -> %d",j);
- }
- printf("\n");
- }
- }
- bool TestPilaVuota(TipoPila p)
- {
- if(p==NULL)
- return true;
- else
- return false;
- }
- void Push(TipoPila *p,TipoElemPila v)
- {
- TipoPila paux;
- paux = malloc(sizeof(struct lista));
- paux->val=v;
- paux->next=(*p);
- *p=paux;
- }
- void Pop(TipoPila *p,TipoElemPila* v)
- {
- TipoPila paux;
- if(TestPilaVuota(*p))
- printf("ERRORE: PILA VUOTA\n");
- else
- {
- *v = (*p)->val;
- paux = *p;
- *p = (*p)->next;
- free(paux);
- }
- }
- void InitPila(TipoPila *p,TipoElemPila v)
- {
- *p = malloc(sizeof(struct lista));
- (*p)->val=v;
- (*p)->next=NULL;
- }
- void Analizza(TipoNodo i)
- {
- printf("%d ",i);
- }
- void VisitaInProfondita(TipoGrafo grafo, TipoNodo nodo_iniz)
- {
- TipoNodo i,j;
- TipoPila pila;
- bool nodi_visti[NumNodi];
- for(i=0;i<NumNodi;i++)
- nodi_visti[i] = false;
- InitPila(&pila,nodo_iniz);
- while(!TestPilaVuota(pila))
- {
- Pop(&pila,&i);
- if(!nodi_visti[i])
- {
- Analizza(i);
- nodi_visti[i] = true;
- for(j=NumNodi-1; j>=0; j--)
- if(TestEsisteArco(grafo,i,j)&& !nodi_visti[j])
- Push(&pila,j);
- }
- }
- }
- void InitCoda(TipoCoda *coda)
- {
- coda->primo=NULL;
- coda->ultimo=NULL;
- }
- bool TestCodaVuota(TipoCoda coda)
- {
- if(coda.primo==NULL)
- return true;
- else
- return false;
- }
- void InCoda(TipoCoda *coda, TipoElemCoda v)
- {
- if(TestCodaVuota(*coda))
- {
- coda->primo = malloc(sizeof(struct lista));
- coda->ultimo = coda->primo;
- }
- else
- {
- coda->ultimo->next = malloc(sizeof(struct lista));
- coda->ultimo=coda->ultimo->next;
- }
- coda->ultimo->val = v;
- coda->ultimo->next = NULL;
- }
- void OutCoda(TipoCoda *coda, TipoElemCoda *v)
- {
- Lista* paux;
- if(TestCodaVuota(*coda))
- printf("ERRORE: CODA VUOTA\n");
- else
- {
- *v = coda->primo->val;
- paux = coda->primo;
- coda->primo = coda->primo->next;
- free(paux);
- if(coda->primo==NULL)
- coda->ultimo = NULL;
- }
- }
- void VisitaInAmpiezza(TipoGrafo grafo, TipoNodo nodo_iniz)
- {
- TipoNodo i, j;
- TipoCoda coda;
- bool nodi_visti[NumNodi];
- for(i = 0; i < NumNodi;i++)
- nodi_visti[i] = false;
- InitCoda(&coda);
- InCoda(&coda,nodo_iniz);
- while(!TestCodaVuota(coda))
- { ///prendi il prossimo nodo i da visitare
- OutCoda(&coda,&i);
- ///analizza il nodo i e lo pone tra i nodi visti
- if(!nodi_visti[i])
- {
- Analizza(i);
- nodi_visti[i] = true;
- for( j=0; j < NumNodi; j++)
- if(TestEsisteArco(grafo,i,j)&& !nodi_visti[j])
- InCoda(&coda,j);
- }
- }
- }
- int main()
- {
- TipoGrafo grafo;
- TipoNodo i,j;
- char flag;
- grafo = InitGrafo();
- while(flag!='n'){
- printf("Dimmi quali vertici vuoi collegare\n");
- printf("Inserisci vertice da: ");scanf("%d",&i);
- printf("Inserisci vertice a: ");scanf("%d",&j);
- printf("\n");
- grafo=InserArco(grafo,i,j);
- printf("Vuoi continuare? s/n: ");fflush(stdin);scanf("%c",&flag);
- }
- StampaGrafo(grafo);
- VisitaInProfondita(grafo,0);
- printf("\n");
- VisitaInAmpiezza(grafo,0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement