graphin.c

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <limits.h>

#define N 5

void cabecalho(){
    system("cls");
    printf("Grafos - ED II - Profa. Roberta\nFeito por: Luiz Fernando Cieslak - RA: 131022776\n\n\n");
}

int menu(){
     cabecalho();
     int op;
     printf("Menu\n1: Inserir Arestas");
     printf("\n2: Mostrar vertices");
     printf("\n3: Percurso em largura");
     printf("\n4: Ordenacao topologica");
     printf("\n5: Busca em profundidade");
     printf("\n6: Caminho minimo (Djikstra)");
     printf("\n8: Sair.\n\n");
     scanf("%d",&op);
     return op;
 }

struct node{
    int dest;
    float peso;
    struct node *prox;
};

struct reg{
    int x;
    struct reg *prox;
};

typedef struct node* no;
typedef struct reg* noFila;

void iniciaGrafo(no grafo[],int grau[]){
    int i=0;
    for(i=0;i<N;i++){
        grafo[i] = NULL;
        grau[i] = 0;
    }
}

void inserirAresta(no grafo[], int grau[], int orig,int dest, float peso){
    no p,q;
    char soun;

        p = (no) malloc(sizeof(struct node));
        if(orig < N && dest < N){
            p->dest = dest;
            p->peso = peso;
            p->prox = NULL;

            //printf("%d %d %.1f",orig,p->dest,p->peso);

            grau[dest]++;

            if(grafo[orig]==NULL)
                grafo[orig] = p;
            else
            {
                q = grafo[orig];

                while(q->prox != NULL)
                    q = q->prox;

                q->prox = p;
            }
        }
        else
        {
            printf("\nNumero inserido excedeu o numero maximo de grafos (%d)",N);
            getch();
            return -1;
        }
}

void mostrarGrafo(no grafo[], int grau[]){
    int i;
    no p;
    for(i=0;i<N;i++)
    {
        printf("\nVertice %d: ",i);
        p=grafo[i];
        while(p){
            printf("%d:(%.1f) ",p->dest,p->peso);
            p=p->prox;
        }
    }
    getch();
}

int addNoFinal(noFila *lista,int x, int m[]){
    if(m[x]==1)
        return 0;
    noFila p = (no) malloc(sizeof(struct reg));
    noFila q = *lista;
    //(*p).info
    p->x = x;
    if(*lista == NULL){
        p->prox = *lista;
        *lista = p;
    }
    else{
        while(q->prox!=NULL){
            q = q->prox;
        }
        q->prox = p;
        p->prox = NULL;
    }
    m[x]=1;
    return 1;
}

int removeNoComeco(noFila *lista){
    if(*lista == NULL)
        return 0;

    int retorno;
    noFila p = *lista;

    *lista = p->prox;
    retorno = p->x;
    free(p);

    return retorno;
}

void largura(no grafo[]){
    int i;
    int m[N];
    for(i=0;i<N;i++)
        m[i]=0;
    noFila fila;
    no p;
    fila = NULL;

    addNoFinal(&fila,1,m);

    while(fila){
        //remover vertice do inicio da fila
        int x = removeNoComeco(&fila);
        printf("%d ",x);

        p = grafo[x];
        while(p){
            addNoFinal(&fila,p->dest,m);
            p = p->prox;
        }

    }
}

int topologica(no grafo[],int grau[]){
    int grauZero,i;
    int pGrau[N];
    for(i=0;i<N;i++)
        pGrau[i]=grau[i];
    while(1){
        grauZero=-1;
        for(i=0;i<N;i++){
            if(pGrau[i]==0)
                grauZero=i;
        }
        if(grauZero==-1) return -1;
        printf("%d ",grauZero);
        pGrau[grauZero] = -1;
        no p=grafo[grauZero];
        while(p){
            pGrau[p->dest]--;
            p=p->prox;
        }
    }
}

int profundidade(no grafo[],int x,int aux[]){
	no p;
	p=grafo[x];
    printf("%d %d",x,aux[x]);
	if(aux[x] != 1){

		aux[x] = 1;
		printf("%d",p->dest);
		profundidade(grafo,p->dest,aux);

	}else{

		p = p->prox;

		if(p!=NULL)
			profundidade(grafo,p->dest,aux);
		else
			return 1;
	}
}

int tamanho(int vet[]){
    int i,tam;
    tam=0;
    for(i=0;i<N;i++)
        if(vet[i]>0)
            tam++;
    return tam;
}

int menorDist(float dist[],int lista[]){
    int i,ind;
    ind = -1;
    float d=INT_MAX;
    for(i=0;i<N;i++)
        if(dist[i]<d && lista[i]!=-1){
            d=dist[i];
            ind=i;
        }
    return ind;
}

void djikstra(no grafo[]){
    int lista[N],x,w,i;
    float dist[N];
    no p;
    printf("\nx: ");
    scanf("%d",&x);

    for(i=0;i<N;i++)
        lista[i]=i;

    dist[x] = 0;
    for(i=0;i<N;i++)
        if(i!=x)
            dist[i] = INT_MAX;

   //printf("\n%d",tamanho(lista));
    while(tamanho(lista)!= 0){
        //remover da lista o vertice com menor distancia
        w = menorDist(dist,lista);
        lista[w] = -1;

        p = grafo[w];
        //printf("\n%d",w);
        while(p!=NULL){
            //relaxar
            //printf("\n%d %d %.2f %.2f %.2f",w,p->dest,dist[p->dest],dist[w],p->peso);
            if( dist[p->dest] > dist[w] + p->peso){
                dist[p->dest] = dist[w]+ p->peso;
            }
            //printf("\n%d %.2f %.2f %.2f\n\n",p->dest,dist[p->dest],dist[w],p->peso);
            p=p->prox;
        }
    }
    for(i=0;i<N;i++)
        printf("%d\t",i);
    printf("\n");
    for(i=0;i<N;i++)
        if(dist[i] == INT_MAX)
            printf("inf\t");
        else
            printf("%.2f\t",dist[i]);

    getch();
}

int main(){
    no grafo[N];
    int grau[N],aux[N],i,x;
    int orig,dest;
    float peso;
    iniciaGrafo(grafo,grau);

    inserirAresta(grafo,grau,1,2,1);
    inserirAresta(grafo,grau,1,4,8);
    inserirAresta(grafo,grau,2,4,6);
    inserirAresta(grafo,grau,2,3,2);
    inserirAresta(grafo,grau,4,3,5);
    inserirAresta(grafo,grau,2,0,10);
    inserirAresta(grafo,grau,3,0,7);

    /*inserirAresta(grafo,grau,1,2,2);
    inserirAresta(grafo,grau,1,3,8);
    inserirAresta(grafo,grau,1,4,9);
    inserirAresta(grafo,grau,2,0,7);
    inserirAresta(grafo,grau,3,0,12);
    inserirAresta(grafo,grau,3,5,20);
    inserirAresta(grafo,grau,4,3,1);
    inserirAresta(grafo,grau,4,5,5);
    inserirAresta(grafo,grau,0,5,8);*/

    char soun;
    do{
        int op = menu();
        switch(op){
         case 1:
             do{
                printf("\nQual a origem e o destino da aresta?(Ex: 2 5)\n");
                scanf("%d %d",&orig,&dest);
                printf("PESO: ");
                scanf("%f",&peso);
                inserirAresta(grafo,grau,orig,dest,peso);
                printf("Tem mais alguma aresta? (S/N)");
                soun = toupper(getch());
            }while(soun=='S');
            break;
         case 2:
            mostrarGrafo(grafo,grau);
            getch();
            break;
         case 3:
            largura(grafo);
            getch();
            break;
         case 4:
            topologica(grafo,grau);
            getch();
            break;
         case 5:
            for(i=0;i<N;i++)
                aux[i]=0;
            printf("\nVertice inicial: ");
            scanf("%d",&x);
            profundidade(grafo,x,aux);
            getch();
         case 6:
             djikstra(grafo);
             break;
         case 8:
                printf("\nTem certeza que deseja sair? (S/N)");
                fflush(stdin);
                soun = toupper(getch());
                if(soun == 'S'){
                    return 0;
                    break;
                }

                else
                    continue;
            default:
                printf("\nOp��o incorreta.");
                break;
        }
    }while(soun!='S');
    return 1234;

}