grafos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

#include <stdlib.h>
#include <stdio.h>
#include "grafos.h"
Grafo_L *cria_grafo(int nv){
 int i;
 Grafo_L *g = (Grafo_L*)malloc(sizeof(Grafo_L));
 g->mat = (Lista**) malloc(nv * sizeof(Lista*));
 for(i = 0; i <= nv; i++){
 g->mat[i] = NULL;
 }
 g->nv = nv;
 return g;
}
void libera_grafo(Grafo_L *g){
 int i;
 for(i = 0; i < g->nv; i++){
 Lista *aux = g->mat[i];
 while(aux != NULL){
 Lista *l = aux->prox;
 free(aux);
 aux = l;
 }
 }
 free(g);
}
void cria_aresta(Grafo_L *g, int v1, int v2){
 if(v1 > 0 && v2 > 0 && v1 <= g->nv && v2 <= g->nv){
 Lista *aux = (Lista*)malloc(sizeof(Lista));
 aux->info = v2;
 aux->prox = g->mat[v1];
 g->mat[v1] = aux;
 }
 else{
 printf("Vertices fora dos limites.");
 }
}
void remove_aresta(Grafo_L *g, int v1, int v2){
 if(v1 > 0 && v2 > 0 && v1 <= g->nv && v2 <= g->nv){
 Lista *p = g->mat[v1];
 Lista *a = NULL;
 while(p != NULL && p->info != v2){
 a = p;
 p = p->prox;
 }
 if(p == NULL){
 printf("Aresta nao existente.");
 }
 if(a == NULL){
 g->mat[v1] = p->prox;
 }
 else{
 a->prox = p->prox;
 }
 free(p);
 }
 else{
 printf("Vertices fora dos limites.");
 }
}
void imprime_grafo(Grafo_L *g){
 int i;
 Lista *l;
 for(i = 1; i < g->nv; i++){
 l = g->mat[i];
 printf("Vertice %d -> ", i);
 while(l != NULL){
 printf("%d ", l->info);
 l = l->prox;
 }
 printf("\n");
 }
}
Resultado *cria_resultado(int nv){
 Resultado *r = (Resultado*)malloc(sizeof(Resultado));
 r->cor = (int*)malloc(nv * sizeof(int));
 r->predecessor = (int*)malloc(nv * sizeof(int));
 r->distancia = (int*)malloc(nv * sizeof(int));
 int i;
 for(i = 0; i < nv; i++){
 r->cor[i] = 0;
 r->predecessor[i] = -1;
 r->distancia[i] = 0;
 }
 return r;
}
Resultado *BFS(Grafo_L *g, int origem){
 if(origem > 0 && origem > 0 && origem <= g->nv && origem <= g->nv){
 Resultado *r = cria_resultado(g->nv);
 r->cor[origem] = 1;
 Fila *f = fila_cria();
 fila_insere(f, origem);
 while(f->ini != NULL){
 int atual = retira_inicio(f);
 Lista *l = g->mat[atual];
 while(l != NULL){
 if(r->cor[l->info] == 0){
 r->cor[l->info] = 1;
 fila_insere(f, l->info);
 r->predecessor[l->info] = atual;
 r->distancia[l->info] = 1 + r->distancia[atual];
 }
 l = l->prox;
 }
 r->cor[atual] = 2;
 }
 return r;
 }
 else{
 printf("\nVertices fora dos limites.");
 }
}
void imprime_resultado(int nv, Resultado *r){
 int i;
 printf("\nVertice:\tPredecessor:\t\tCor:\t\tDistancia:");
 for(i = 1; i < nv; i++){
 printf("\n%d->\t\t%d\t\t\t%d\t\t%d", i, r->predecessor[i], r->cor[i], r->distancia[i]);
 }
}
Fila *fila_cria(void){
 Fila *f= (Fila *)malloc(sizeof(Fila));
 f->ini = f->fim = NULL;
 return f;
}
void fila_insere(Fila *f, int origem){
 Lista *l = (Lista*)malloc(sizeof(Lista));
 l->info = origem;
 l->prox = NULL;
 if(f->fim != NULL){
 f->fim->prox = l;
 }
 else{
 f->ini= l;
 }
 f->fim = l;
}
int retira_inicio(Fila *f){
 Lista *no = f->ini;
 int aux;
 aux = f->ini->info;
 f->ini = f->ini->prox;
 if(f->ini == NULL){
 f->fim = NULL;
 }
 free(no);
 return aux;
}