exercicios_grafos

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

EX28/GrafoEstatico.c
#include <stdio.h>
#include <malloc.h>
#define n_v 7
typedef int bool;
typedef struct {
 int m[n_v] [n_v];	
}Graph;
void InicializaGraph(Graph* g){
 int i=0;
 int j=0;
 for(i=0;i<n_v;i++){
 for(j=0;j<n_v;j++){
 	g->m[i][j]=0;
 }	
 }	
}
bool buscaAresta(Graph g, int v1, int v2){
 return (g.m[v1][v2]>0);	
}
bool insereAresta(Graph* g,int v1,int v2){
 //if(!(BuscaAresta(*g,v1,v2)) return 0;
 g->m [v1][v2]=1;
 return 1;	
}
bool excluiAresta(Graph* g,int v1,int v2){
 g->m[v1][v2]=0;
 return 1;	
}
void showGraphEs(Graph g){
 int i,j;
 printf("\nPrint Grafo estatico:\n");
 for(i=0;i<n_v;i++){
 printf("Vertice %i: ",i);	
 for(j=0;j<n_v;j++){
 	if(g.m[i][j]>0)
 	printf("%i ",j);
 }
 printf("\n");	
 }
 printf("\n\n");	
}
EX28/Fila.c
# include <malloc.h>
#include <stdio.h>
#define true 1
#define false 0
typedef int bool;
typedef struct x{
 int v;
 struct x* prox;	
}No;
typedef struct{
 No* inicio;
 No* fim;	
}FILA;
void CriaFila(FILA* f){
 f->inicio=NULL;
 f->fim=NULL;	
}
 	
No* CriaNoFila(int v){
 No* novo=(No*)malloc(sizeof(No));
 novo->v=v;
 novo->prox=NULL;
 return novo;	
}
bool inserirFila(FILA* f,int v){
 No* novo=CriaNoFila(v);
 if(f->inicio==NULL){
 f->inicio=novo;
 f->fim=novo;
 novo->prox=NULL;
 return true;	
 }
 f->fim->prox=novo;
 f->fim=novo;
 return true;	
}
int removerPrimeiro(FILA* f){
 if(f->inicio==NULL) return -1;
 No* removido=f->inicio;
 f->inicio=removido->prox;
 int v=removido->v;
 free(removido);
 if(f->inicio==NULL) f->fim=NULL;
 return v;
}
void DestroiFila(FILA* f){
 No* atual=f->inicio;
 No* removido;
 while(atual){
 removido=atual;
 atual=atual->prox;
 free(removido);	
 }
 free(f);	
}
void removeNos(FILA* f){
 No* atual=f->inicio;
 No* removido;
 while(atual){
 removido=atual;
 atual=atual->prox;
 free(removido);	
 }
 f->fim=NULL;
 f->inicio=NULL;	
}
void showFila(FILA* f){
 No* atual=f->inicio;
 printf("\nFila: ");
 while(atual){
 printf("%i ",atual->v);
 atual=atual->prox;	
 }
 printf("\n");	
}
EX28/grafoDinamico.c
#include <malloc.h>
#include "Fila.c"
#include <stdio.h>
# define true 1
#define false 0
//Representação dinamica de grafo
typedef int bool;
typedef struct aux{
 int v;
 int c;
 struct aux* prox;
} NO;
typedef struct{
 NO* inicio;	
}LISTA;
typedef struct{
 NO* inicio;
 int n;
 int flag;
 int tipo; //hotel, restaurante e etc	
}Vertice;
typedef struct{
 Vertice* vertices;
 int tamanho;	
}Grafo;
bool inicializar(Grafo* g, int nVert){
 g->tamanho=nVert;
 g->vertices=(Vertice*) malloc(sizeof(Vertice)*nVert);
 int i=0;
 for(i=0;i<nVert;i++){
 g->vertices[i].n=i;
 g->vertices[i].inicio=NULL;
 g->vertices[i].tipo=0;	
 }	
}
NO* BuscaAresta(Grafo* g, int v1,int v2, NO** ant){ // busca se existe aresta que sai do vertice v1 em direção a v2
 NO* atual= g->vertices[v1].inicio;
 *ant= NULL;
 while(atual){
 if(atual->v==v2) return atual;
 *ant=atual;
 atual=atual->prox;	
 }
 return NULL;
}
NO* CriaNo(int v1,int c){
 NO* atual=(NO*) malloc (sizeof(NO));
 atual->v=v1;
 atual->c=c;
 return atual;	
}
bool inserir(Grafo* g, int v1, int v2){ //cria aresta entre o vertice v1 e v2 e de v2 a v1. Grafo é não dirigido
 NO* ant;
 NO* aux;
 if(v2>g->tamanho-1 || v1>g->tamanho-1) return 0;
 if(BuscaAresta(g,v1,v2,&ant)!=NULL) return 0;
 //if(aux!=NULL && aux->c==c) return 0; //permite a insercao de arestas iguais.Desde que os valores c sejam diferentes 
 NO* novo1=CriaNo(v2,0);
 novo1->prox=g->vertices[v1].inicio;
 g->vertices[v1].inicio=novo1;
 return 1;
}
void TrocaOcupacao(Grafo* g,int oc,int v){
 g->vertices[v].tipo=oc;	
}
bool excluir(Grafo* g,int v1,int v2){//remove a aresta que parte de v1 em direção a v2
 NO* ant;
 NO* exclui=BuscaAresta(g,v1,v2,&ant);
 if(exclui==NULL) return 0;
 if(ant) ant->prox=exclui->prox;
 else g->vertices[v1].inicio=exclui->prox;
 free(exclui);
 return 1;	
}
void showGraph(Grafo g){
 int i,j;
 NO* atual;
 printf("Print do grafo dinamico: \n");
 for(i=0;i<g.tamanho;i++){
 atual=g.vertices[i].inicio;
 printf("\nVertice %i tipo: %i : ",i,g.vertices[i].tipo);
 while(atual){
 printf("%i ",atual->v);
 atual=atual->prox;	
 }
 }
 printf("\n\n");	
} 
int contaLacos(Grafo g){
 int cont=0;
 int i=0;
 NO* ant;
 for(i=0;i<g.tamanho;i++){
 if(BuscaAresta(&g,i,i,&ant)!=NULL) cont++;	
 }
 return cont;	
}
void removerLacos(Grafo* g){
 int i=0;
 for(i=0;i<g->tamanho;i++){
 excluir(g,i,i);	
 }
}
void DestroiArestas(Grafo* g){
 NO* atual;
 NO*remove;
 int i=0;
 for(i=0;i<g->tamanho;i++){
 atual=g->vertices[i].inicio;
 g->vertices[i].inicio=NULL;
 while(atual){
 remove=atual;
 atual=atual->prox;
 free(remove);	
 }	
 }	
}
void DestroiGrafo(Grafo* g){
 DestroiArestas(g);
 free(g->vertices);
 free(g);	
}
/*Grafo* Transposto(Grafo* g){
 Grafo* transp=(Grafo*)malloc(sizeof(Grafo));
 NO* atual;
 inicializar(transp,g->tamanho);
 int i=0;
 for(i=0;i<transp->tamanho;i++){
 atual=g->vertices[i].inicio;
 while(atual){
 inserir(transp,atual->v,i);
 atual=atual->prox;	
 } 	
 }
 return transp;	
}*/
int GrauDeSaida(Grafo* g, int i){// retorna o grau de saida do vertice i
 int cont=0;
 NO* atual=g->vertices[i].inicio;
 while(atual){
 cont++;
 atual=atual->prox;	
 }
 return cont;	
}
bool ApontaPraTodos(Grafo* g,int i){
 NO* atual=g->vertices[i].inicio;
 //int cont=0;
 int j=0;
 NO* ant;
 for(j=0;j<g->tamanho;j++){
 if(j!=i)
 if(BuscaAresta(g,i,j,&ant)==NULL) return false;	
 }
 return true;	
}
bool IsArvoreEnraizada(Grafo* g){
 int i;
 int j=0;
 NO* raiz;
 //Vetice* V_atual;
 NO* atual;
 for(i=0;i<g->tamanho;i++){
 atual=g->vertices[i].inicio;
 if(ApontaPraTodos(g,i)==true){
 raiz=atual;	
 for(j=0;j<g->tamanho;j++){
 	 if(j!=i){
 	 if(GrauDeSaida(g,j)>0) break;
 	 return true;
	 }
 }	
 }	
 }
 return false; 	
 }	 
void ZeraFlags(Grafo* g){
 int i;
 for(i=0;i<g->tamanho;i++){
 g->vertices[i].flag=0;	
 }	
}
void RemoveCiclosAux(Grafo* g,int i, int j){
 g->vertices[i].flag=1;
 NO* atual=g->vertices[i].inicio;
 while(atual){
 if(g->vertices[atual->v].flag==1 && j!=atual->v) {
 NO* aux=atual;
 atual=atual->prox;
	printf("Aresta [%i %i] removida\n",i,aux->v);
	excluir(g,aux->v,i);
 	//return;
 }
 else if(g->vertices[atual->v].flag==0) {
 	RemoveCiclosAux(g,atual->v,i);
 	 atual=atual->prox;
 }
 else atual=atual->prox;
 	
 }
 g->vertices[i].flag=2;
}
void RemoveCiclos(Grafo* g){
 ZeraFlags(g);
 int i;
 bool resp;
 for(i=0;i<g->tamanho;i++){
 RemoveCiclosAux(g,i,i);
 }	
}
void BuscaProfAux(Grafo* g,int a,int b,int j, bool* resp,int* cont,int* menor){
 *cont=*cont+1;
 //printf("a: %i j: %i cont: %i\n",a,j,*cont); 
 g->vertices[a].flag=1;
 NO* atual=g->vertices[a].inicio;
 while(atual){
 if(atual->v==b && j!=atual->v){
 *resp=true;
	if(*cont<*menor)
	 *menor=*cont;
 //printf("Achei menor: %i\n ",*menor);	
 }	
 if(g->vertices[atual->v].flag==0 && atual->v!=j) BuscaProfAux(g,atual->v,b,a,resp,cont,menor);
 atual=atual->prox;
 }
 *cont=*cont-1;
 //if(j=!a) 
 g->vertices[a].flag=0;
 //else {
 //g->vertices[a].flag=2;	
}
int BuscaCaminhoAB(Grafo* g,int a,int b){
 if(a<0 || a>g->tamanho-1 || b<0 || b>g->tamanho-1) {
 printf("Um dos vertices nao existe");
 return -1;	
 }
 ZeraFlags(g);
 bool resp=false;
 int cont=0;
 int menor=g->tamanho*15;
 BuscaProfAux(g,a,b,a,&resp,&cont,&menor);
 if(resp==true) return menor;
 printf("Não existe caminho entre os vertices A B\n");
 return -1;	
}
void CompletaGrafo(Grafo* g){
 int i,j;
 for(i=0;i<g->tamanho;i++){
 for(j=0;j<g->tamanho;j++){
 	if(j!=i)
 	 inserir(g,i,j);
 }	
 }	
}
bool isCompleteGraph(Grafo* g){
 int i,j,aux;
 aux=0;
 NO*
ant;
 for(i=0;i<g->tamanho;i++){
 for(j=aux;j<g->tamanho;j++){
 if(j!=i)	
 if(BuscaAresta(g,i,j,&ant)==NULL) return false;	
 }
 aux++;	
 }
 return true;
}
Grafo* Complemento(Grafo* g){
 Grafo* comp=(Grafo*)malloc(sizeof(Grafo));
 inicializar(comp,g->tamanho);
 NO* atual;
 int i,j,aux;
 aux=0;
 for(i=0;i<comp->tamanho;i++){
 for(j=0;j<comp->tamanho;j++){
 if(i!=j)	
 if(BuscaAresta(g,i,j,&atual)==NULL) inserir(comp,i,j);	
 }	
 }
 return comp;	
}
int BuscaLargura(Grafo* g, int a,int x ){
 FILA f;
 CriaFila(&f);
 ZeraFlags(g);
 NO* atual;
 inserirFila(&f,a);
 g->vertices[a].flag=1;
 while(f.inicio){	
 atual=g->vertices[removerPrimeiro(&f)].inicio;
 while(atual){
 if(g->vertices[atual->v].tipo==x && g->vertices[atual->v].flag==0 ){
 	DestroiFila(&f);
 	return atual->v;
 }	
 if(g->vertices[atual->v].flag==0){
	g->vertices[atual->v].flag=1;
 inserirFila(&f,atual->v);
	}
	atual=atual->prox;
 }	
 }
 }
int* CaminhoMaisCurtoAPartirDe(Grafo* g,int i){//retorna uma lista contendo o tamanho caminho entre o vertice i e os outros vertices
 int j=0;
 int* resposta=(int*)malloc(sizeof(int)*g->tamanho);
 for(j=0;j<g->tamanho;j++){
 if(j!=i)
 resposta[j]=BuscaCaminhoAB(g,i,j); 	
 }
 resposta[i]=0;
 return resposta;	
}
void showVetor(int* v,int tamanho){
 int i;
 printf("\nLista de Resposta: \n");
 for(i=0;i<tamanho;i++){
 printf("%i %i\n",i, v[i]);	
 }
 printf("\n");	
}
EX28/UsaGrafo.c
#include "grafoDinamico.c"
#include "GrafoEstatico.c"
int ask(char s [1000]){
 int answer=0;
 printf(s);
 scanf("%i",&answer);
 return answer;	
}
void adiciona(Grafo* g,Graph* ES){
 int v1=0;
 int v2=0;
 do{
 v1=ask("Digite o vertice de partida (v1): ");
 v2=ask("Digite o vertice de destino (v2): ");
 inserir(g,v1,v2);	
 printf("\n");
 }while(ask("Digite 1 para adicionar mais 1: ")==1);
 showGraph(*g);
 
}
void busca(Grafo* g,Graph* ES){
 showGraph(*g);	
 int v1=ask("Digite o vertice de partida (v1): ");
 NO* ant;
 NO* encontrado= BuscaAresta(g,v1,ask("Digite o vertice de destino (v2): "),&ant);
 if(encontrado) printf("Aresta [%i, %i] encontrada\n", v1, encontrado->v);
 else printf("Aresta nao encontrada\n");	
}
void remover(Grafo* g,Graph* ES){
 int v1=0;
 if(ask("\nDigite 1 para manipular o grafo dinamico\n2 para manipular o estatico")==1){
 do{
 v1=ask("Digite o vertice de partida (v1): ");
 excluir(g,v1,ask("Digite o vertice de destino (v2): "));	
 showGraph(*g);
 printf("\n");
 }while(ask("Digite 1 para remover mais 1: ")==1);
 }
 else{
 do{
 v1=ask("Digite o vertice de partida (v1): ");
 excluiAresta(ES,v1,ask("Digite o vertice de destino (v2): "));	
 showGraphEs(*ES);
 printf("\n");
 }while(ask("Digite 1 para remover mais 1: ")==1);	
 }
}
bool checaSubGrafo(Graph* g1,Grafo* g2){//checa se o grafo g2 e subgrafo de g1
 NO* atual;
 int i=0;
 if(g2->tamanho>n_v) return false;
 for(i=0;i<g2->tamanho;i++){
 atual=g2->vertices[i].inicio;
 while(atual){
 if(!(buscaAresta(*g1,i,atual->v))) return false;
 atual=atual->prox;	
 }	
 }
 return true;	
}
int MaiorGrafo(Grafo* g1, Graph* g2 ){
 if(g1->tamanho>n_v) return g1->tamanho;
 else return n_v;	
} 
void options(){
 printf("Comandos:\n1 para adicionar arestas\n2 para excluir arestas\n3 para buscar arestas\n4 para contar lacos\n5 para remover os lacos\n6 para destruir o grafo\n8 para visualizar os dois grafos");
 printf("\n10 para verficar se e uma arvore enraizada");
 printf("\n11 para excluir os ciclos");
 printf("\n12 para ver se existe caminho entre dois vertices");
 printf("\n13 para completar o grafo");
 printf("\n14 para verificar se o grafo e completo");
 printf("\n15 para transformar o grafo em seu complemento");
 printf("\n 16 para alterar a ocupacao de uma sala");
 printf("\n18 para ver os caminhos mais curtos a partir de um dado vertice");
 printf("\n19 para ver o local do tipo especificado mais proximo");
}
void interagir(Grafo* g,Graph* ES){
 int answer=0;
 Grafo* gN;
 LISTA* lista;
 do{
 options();	
 answer=ask("\nsua resposta: ");
 printf("%p\n",g);
 switch(answer){
 	case 1: adiciona(g,ES); break;
 	case 2: remover(g,ES); break;
 	case 3: busca(g,ES); break;
 	case 4: printf("Numero de lacos: %i\n", contaLacos(*g)); break;
 	case 5: removerLacos(g); showGraph(*g); break;
 	case 6: DestroiArestas(g); showGraph(*g); break;
 	case 8: showGraph(*g); showGraphEs(*ES); printf("O dinamico e subgrafo do estatico: %i\n",checaSubGrafo(ES,g)); break;
 	case 10: printf("Arvore Enraizada: %i\n",IsArvoreEnraizada(g)); break;
 	case 11: RemoveCiclos(g); break;
 case 12: printf("Numero de vertices entre A ate B: %i\n",BuscaCaminhoAB(g,ask("Digite o A: "),ask("Digite o B: "))); break;;
 case 13: CompletaGrafo(g); showGraph(*g); break;
 case 14: printf("O grafo e completo: %i\n",isCompleteGraph(g)); break;
 case 15: gN=Complemento(g); DestroiGrafo(g); g=gN; showGraph(*g); break;
 case 16: TrocaOcupacao(g,ask("Digite a ocupacao: "),ask("Digite o vertice: ")); showGraph(*g); break;
 case 18: showVetor(CaminhoMaisCurtoAPartirDe(g,ask("Digite o vertice de partida: ")),g->tamanho);
 case 19: printf("Local do tipo x mais proximo: %i\n",BuscaLargura(g,ask("Digite o vertice de partida a: "),ask("Digite o tipo X: "))); break;
 	default: printf("\nComando invalido\n");
 }	
 }while(ask("Digite 1 para continuar: ")==1);
}
int main(){
 Grafo g1;
 Graph ES;
 inicializar(&g1,ask("Digite o numero de vertices do grafo: "));
 inserir(&g1,0,1);
 inserir(&g1,0,4);
 inserir(&g1,1,0);
 inserir(&g1,1,4);
 inserir(&g1,2,4);
 inserir(&g1,2,1);
 inserir(&g1,3,6);
 inserir(&g1,3,6);
 inserir(&g1,4,3);
 inserir(&g1,4,5);
 inserir(&g1,5,2);
 inserir(&g1,6,5);
 inserir(&g1,6,7);
 inserir(&g1,6,8);
 inserir(&g1,6,4);
 inserir(&g1,7,5);
 inserir(&g1,8,5);
 inserir(&g1,8,7);
 inserir(&g1,8,2);
 TrocaOcupacao(&g1,1,0);
 TrocaOcupacao(&g1,1,5);
 TrocaOcupacao(&g1,1,3);
 TrocaOcupacao(&g1,2,1);
 TrocaOcupacao(&g1,2,2);
 TrocaOcupacao(&g1,2,6);
 TrocaOcupacao(&g1,3,4);
 TrocaOcupacao(&g1,3,8);
 TrocaOcupacao(&g1,1,7);
 InicializaGraph(&ES);
 interagir(&g1,&ES);
 //printf("%i\n",ApontaPraTodos(&g1,0));
 //printf("%i\n",ApontaPraTodos(&g1,1));	
}
EX28/UsaGrafo.exe