Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <stdio.h>
- #include "grafo.h"
- #include "listapesos.h"
- struct grafo{
- int nro_vertices;
- int nro_arestas;
- Aresta **arestas;
- int grau_max;
- Listap *lpesos;
- };
- struct aresta{
- int vertice_dest;
- int peso;
- Aresta *prox;
- };
- Grafo *Cria_Grafo(int n_vert){
- int i;
- Grafo *Gr = (Grafo *) malloc(sizeof(Grafo));
- Gr->nro_vertices = n_vert;
- Gr->nro_arestas = 0;
- Gr->grau_max = n_vert - 1;
- Gr->lpesos = criaLista();
- Gr->arestas = (Aresta **) malloc(n_vert*sizeof(Aresta));
- for(i=0;i<n_vert;i++) Gr->arestas[i] = NULL;
- return Gr;
- }
- void deletaGrafo(Grafo *g)
- {
- Aresta *aux,*ant;
- int i;
- for(i=0;i<g->nro_vertices;i++)
- {
- aux = g->arestas[i];
- while(aux != NULL)
- {
- ant = aux;
- aux = aux->prox;
- free(ant);
- }
- }
- free(g->arestas);
- // free(g->grau);
- }
- void Insere_aresta(Grafo *G,int vertice_orig, int vertice_dest, int peso, int eh_digrafo){
- if(vertice_dest > G->nro_vertices || vertice_orig > G->nro_vertices) return;
- if(existeAresta(G,vertice_orig,vertice_dest)) return;
- Aresta *aresta = (Aresta*) malloc(sizeof(Aresta));//alocando nova aresta
- if(aresta == NULL) return;
- aresta->vertice_dest = vertice_dest;
- aresta->peso = peso;
- aresta->prox = NULL;
- //G->grau[vertice_orig] = G->grau[vertice_orig] + 1; //aumentando grau
- if((G->arestas[vertice_orig]) == NULL)//lista vazia
- {
- G->arestas[vertice_orig] = aresta;
- }
- else //inserção na cabeça
- {
- aresta->prox = G->arestas[vertice_orig];
- G->arestas[vertice_orig] = aresta;
- }
- if(eh_digrafo == 1)
- {
- G->lpesos = insereOrdenado(G->lpesos,vertice_orig,vertice_dest,peso);
- G->nro_arestas++;
- Insere_aresta(G,vertice_dest, vertice_orig, peso, 0);
- }
- }
- void buscaProfundidade_Grafo(Grafo *g,int ini, int visitados[],int caminho[]){ //Função principal
- int i, cont = 0,cont2 = 0;
- for (i=0 ; i < g->nro_vertices ; i++) visitados[i] = 0;
- if(caminho != NULL) for (i=0 ; i < g->nro_vertices ; i++) caminho[i] = -1;
- buscaProfundidade(g,ini, visitados,caminho, &cont,&cont2);
- }
- void buscaProfundidade(Grafo *g,int ini, int visitados[],int caminho[], int *cont,int *cont2){ //Função auxiliar
- Aresta *aux;
- //if(caminho != NULL) printf("CONT: %d | INI: %d\n",*cont,ini);
- visitados[ini] = *cont; //vertice visitado
- *cont += 1;
- aux = g->arestas[ini];
- while(aux != NULL)
- {
- if(visitados[aux->vertice_dest] == 0) //Se o vertice ainda nao foi visitado
- {
- if(caminho != NULL)
- {
- caminho[(*cont2)] = aux->vertice_dest;
- *cont2 +=1;
- }
- buscaProfundidade(g,aux->vertice_dest, visitados,caminho, cont,cont2); //visitando o proximo vertice
- }
- else
- {
- aux = aux->prox;
- }
- }
- }
- int eh_conexo(Grafo *g)
- {
- if(g->nro_vertices == 1) return 1;
- int i,visitados[g->nro_vertices];
- buscaProfundidade_Grafo(g,1,visitados,NULL);
- for(i=0;i<g->nro_vertices;i++)
- {
- if(visitados[i] == 0)
- {
- return 0;
- }
- }
- return 1;
- }
- void salvaGrafo(Grafo *g,char arq[])
- {
- int i;
- Aresta *aux;
- FILE *out = fopen(arq,"w+");
- if(out == NULL) return;
- fprintf(out,"%d \n",g->nro_vertices);
- for(i=0;i<g->nro_vertices;i++)
- {
- aux = g->arestas[i];
- while(aux != NULL)
- {
- fprintf(out,"%d %d %d\n",i+1,aux->vertice_dest+1,aux->peso);
- aux = aux->prox;
- }
- }
- fclose(out);
- }
- Grafo *abreGrafo()
- {
- int origem,destino,pes,nvert;
- FILE *in = fopen("in.txt","r");
- if(in == NULL) return NULL;
- fscanf(in,"%d\n",&nvert);
- Grafo *g = Cria_Grafo(nvert);
- while(!feof(in))
- {
- fscanf(in,"%d %d %d\n",&origem,&destino,&pes);
- Insere_aresta(g,origem-1,destino-1,pes,1);
- }
- fclose(in);
- return g;
- }
- int eh_arvore(Grafo *g)
- {
- if((g->nro_vertices == 1) || (eh_conexo(g) && (g->nro_arestas == g->nro_vertices -1))) return 1;
- else return 0;
- }
- Grafo *geraArvore(Grafo *g)
- {
- Grafo *arvore = Cria_Grafo(g->nro_vertices);
- int i,j=0;
- int comp[g->nro_vertices];
- for(i=0;i<arvore->nro_vertices;i++) //Inicialmente cada vertice tem seu proprio componente conexo
- {
- comp[i] = i;
- }
- //imprimePesos(g->lpesos);
- //printf("\nArestas sendo inseridas:\n");
- while(j<g->nro_arestas) //enquanto tivermos arestas vemos tentar gerar a arvore
- {
- int v1,v2,peso;
- getelemento(g->lpesos,j,&v1,&v2,&peso); //Pega a aresta de posição J na lista de pesos ordenados;
- //Se o componente do vertice 1 for diferente do vertice 2, não temos inserção de ciclo. Podemos assim inserir a aresta.
- if(comp[v1] != comp[v2])
- {
- Insere_aresta(arvore,v1,v2,peso,1);
- //printf("A aresta(%d %d %d) foi inserida.\n",v1+1,v2+1,peso);
- //compara o valor, para pegar o menor componente conexo e fazer a troca
- if(comp[v1] < comp[v2]) diminuiComponente(comp,v1,v2,arvore->nro_vertices);
- else diminuiComponente(comp,v2,v1,arvore->nro_vertices);
- }
- if(eh_arvore(arvore))
- {
- return arvore;
- }
- j++;
- }
- return NULL; //Ocorreu algum erro e a arvore não foi gerada.
- }
- void diminuiComponente(int *comp,int v1,int v2,int tam) //coloca v1 e v2 no mesmo componente conexo
- {
- int i = 0;
- int maior = comp[v2]; //a ser retirado
- for(i=0;i<tam;i++)
- {
- if(comp[i] == maior) comp[i] = comp[v1];
- }
- }
- /*----------------------------------------T2----------------------------------------------*/
- int getPeso(Grafo *g, int org, int dest) //Pega o peso da aresta (ORIG,DEST)
- {
- Aresta *aux = g->arestas[org];
- while(aux != NULL)
- {
- if(aux->vertice_dest == dest) return aux->peso;
- aux = aux->prox;
- }
- return -1;
- }
- int existeAresta(Grafo *g, int org, int dest) //Pega o peso da aresta (ORIG,DEST)
- {
- Aresta *aux = g->arestas[org];
- while(aux != NULL)
- {
- if(aux->vertice_dest == dest) return 1;
- aux = aux->prox;
- }
- return 0;
- }
- void ExchangeCharacters(int str[], int p1, int p2) // troca as posicoes do array
- {
- int tmp;
- tmp = str[p1];
- str[p1] = str[p2];
- str[p2] = tmp;
- }
- //troca os items, fixando uma posição(K) e trocando as outras posições
- void RecursivePermute( int array[], int k,int len,int arraymin[], int *pesomin,Grafo *g)
- {
- int i;
- if (k == len) {
- int cont = 0;
- int somapeso = 0;
- while(cont < len)// Somando todos os pesos da sequencia de vertices em STR
- {
- if(cont+1 == len) // Ultima aresta
- {
- somapeso += getPeso(g,array[cont],array[0]);
- }
- else
- {
- somapeso += getPeso(g,array[cont],array[cont+1]);
- }
- cont++;
- }
- if(somapeso < *pesomin)// Temos uma nova sequencia com peso min
- {
- *pesomin = somapeso;
- //Fazer copia ARRAYMIN
- for(cont = 0; cont < len;cont ++)
- {
- arraymin[cont] = array[cont];
- }
- }
- }
- else
- {
- for (i = k; i < len; i++) {
- ExchangeCharacters( array, k, i);
- RecursivePermute( array, k + 1,len,arraymin,pesomin,g);
- ExchangeCharacters( array, i, k);
- }
- }
- }
- Grafo *encontra_caminho(Grafo *g)
- {
- int nvert = g->nro_vertices;
- int array[nvert];
- int arraymin[nvert]; //Responsavel por guardar o menor caminho
- int pesomin = 99999999; //Menor peso
- int i;
- for(i=0;i<nvert;i++) //Preenchendo array com os vertices
- {
- array[i] = i;
- }
- RecursivePermute(array,0,nvert,arraymin,&pesomin,g);
- printf("Sequencia de vertices minima: ");
- for(i=0;i<nvert;i++)
- {
- printf("%d",arraymin[i]+1);
- }
- //printf("\nPESO MIN: %d\n",pesomin);
- //Gerando um novo grafo com a sequencia minima:
- Grafo *h = Cria_Grafo(nvert);
- for(i=0;i<nvert;i++)
- {
- if(i+1 == nvert)
- {
- Insere_aresta(h,arraymin[i],arraymin[0],getPeso(g,arraymin[i],arraymin[0]),1);
- }
- else
- {
- Insere_aresta(h,arraymin[i],arraymin[i+1],getPeso(g,arraymin[i],arraymin[i+1]),1);
- }
- }
- printf("\nCiclo gerado.(Forca bruta)\n");
- return h;
- }
- /*---------------------------Aproximado-----------------------------------------*/
- Grafo *encontra_caminho2(Grafo *g)
- {
- //Gerando a Arvore.
- Grafo *h = geraArvore(g);
- if(h == NULL)
- {
- printf("Ocorreu um erro ao gerar a arvore.");
- deletaGrafo(g);
- return NULL;
- }
- int i,visitados[h->nro_vertices];
- int caminho[h->nro_vertices];
- buscaProfundidade_Grafo(h,0,visitados,caminho);
- Grafo *ciclo = Cria_Grafo(g->nro_vertices);
- //Inserindo as arestas do ciclo.
- for(i=0;i<g->nro_vertices;i++)
- {
- if(i+1 == g->nro_vertices)
- {
- Insere_aresta(ciclo,caminho[i],caminho[0],getPeso(g,caminho[i],caminho[0]),1);
- }
- else
- {
- Insere_aresta(ciclo,caminho[i],caminho[i+1],getPeso(g,caminho[i],caminho[i+1]),1);
- }
- }
- //for(i=0;i<g->nro_vertices;i++) printf("Caminho[%d]: %d\n",i,caminho[i]+1);
- printf("Ciclo gerado.(Aproximado)\n");
- return ciclo;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement