Advertisement
Guest User

Untitled

a guest
May 25th, 2015
266
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.80 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "grafo.h"
  4. #include "listapesos.h"
  5.  
  6. struct grafo{
  7. int nro_vertices;
  8. int nro_arestas;
  9. Aresta **arestas;
  10. int grau_max;
  11. Listap *lpesos;
  12.  
  13. };
  14.  
  15. struct aresta{
  16. int vertice_dest;
  17. int peso;
  18. Aresta *prox;
  19. };
  20.  
  21.  
  22. Grafo *Cria_Grafo(int n_vert){
  23.  
  24. int i;
  25. Grafo *Gr = (Grafo *) malloc(sizeof(Grafo));
  26.  
  27. Gr->nro_vertices = n_vert;
  28. Gr->nro_arestas = 0;
  29. Gr->grau_max = n_vert - 1;
  30.  
  31. Gr->lpesos = criaLista();
  32.  
  33. Gr->arestas = (Aresta **) malloc(n_vert*sizeof(Aresta));
  34. for(i=0;i<n_vert;i++) Gr->arestas[i] = NULL;
  35.  
  36.  
  37. return Gr;
  38. }
  39. void deletaGrafo(Grafo *g)
  40. {
  41. Aresta *aux,*ant;
  42. int i;
  43.  
  44. for(i=0;i<g->nro_vertices;i++)
  45. {
  46. aux = g->arestas[i];
  47. while(aux != NULL)
  48. {
  49. ant = aux;
  50. aux = aux->prox;
  51. free(ant);
  52. }
  53. }
  54. free(g->arestas);
  55. // free(g->grau);
  56.  
  57. }
  58. void Insere_aresta(Grafo *G,int vertice_orig, int vertice_dest, int peso, int eh_digrafo){
  59.  
  60. if(vertice_dest > G->nro_vertices || vertice_orig > G->nro_vertices) return;
  61. if(existeAresta(G,vertice_orig,vertice_dest)) return;
  62.  
  63. Aresta *aresta = (Aresta*) malloc(sizeof(Aresta));//alocando nova aresta
  64. if(aresta == NULL) return;
  65.  
  66. aresta->vertice_dest = vertice_dest;
  67. aresta->peso = peso;
  68. aresta->prox = NULL;
  69.  
  70. //G->grau[vertice_orig] = G->grau[vertice_orig] + 1; //aumentando grau
  71.  
  72. if((G->arestas[vertice_orig]) == NULL)//lista vazia
  73. {
  74. G->arestas[vertice_orig] = aresta;
  75. }
  76. else //inserção na cabeça
  77. {
  78. aresta->prox = G->arestas[vertice_orig];
  79. G->arestas[vertice_orig] = aresta;
  80. }
  81.  
  82.  
  83.  
  84. if(eh_digrafo == 1)
  85. {
  86. G->lpesos = insereOrdenado(G->lpesos,vertice_orig,vertice_dest,peso);
  87. G->nro_arestas++;
  88. Insere_aresta(G,vertice_dest, vertice_orig, peso, 0);
  89. }
  90. }
  91. void buscaProfundidade_Grafo(Grafo *g,int ini, int visitados[],int caminho[]){ //Função principal
  92.  
  93. int i, cont = 0,cont2 = 0;
  94.  
  95. for (i=0 ; i < g->nro_vertices ; i++) visitados[i] = 0;
  96. if(caminho != NULL) for (i=0 ; i < g->nro_vertices ; i++) caminho[i] = -1;
  97.  
  98. buscaProfundidade(g,ini, visitados,caminho, &cont,&cont2);
  99.  
  100. }
  101.  
  102. void buscaProfundidade(Grafo *g,int ini, int visitados[],int caminho[], int *cont,int *cont2){ //Função auxiliar
  103.  
  104. Aresta *aux;
  105.  
  106.  
  107. //if(caminho != NULL) printf("CONT: %d | INI: %d\n",*cont,ini);
  108.  
  109. visitados[ini] = *cont; //vertice visitado
  110. *cont += 1;
  111.  
  112. aux = g->arestas[ini];
  113.  
  114. while(aux != NULL)
  115. {
  116. if(visitados[aux->vertice_dest] == 0) //Se o vertice ainda nao foi visitado
  117. {
  118. if(caminho != NULL)
  119. {
  120. caminho[(*cont2)] = aux->vertice_dest;
  121. *cont2 +=1;
  122. }
  123. buscaProfundidade(g,aux->vertice_dest, visitados,caminho, cont,cont2); //visitando o proximo vertice
  124. }
  125. else
  126. {
  127. aux = aux->prox;
  128. }
  129. }
  130. }
  131. int eh_conexo(Grafo *g)
  132. {
  133. if(g->nro_vertices == 1) return 1;
  134. int i,visitados[g->nro_vertices];
  135.  
  136. buscaProfundidade_Grafo(g,1,visitados,NULL);
  137.  
  138. for(i=0;i<g->nro_vertices;i++)
  139. {
  140. if(visitados[i] == 0)
  141. {
  142. return 0;
  143. }
  144. }
  145. return 1;
  146. }
  147. void salvaGrafo(Grafo *g,char arq[])
  148. {
  149. int i;
  150. Aresta *aux;
  151. FILE *out = fopen(arq,"w+");
  152. if(out == NULL) return;
  153.  
  154. fprintf(out,"%d \n",g->nro_vertices);
  155.  
  156. for(i=0;i<g->nro_vertices;i++)
  157. {
  158. aux = g->arestas[i];
  159. while(aux != NULL)
  160. {
  161. fprintf(out,"%d %d %d\n",i+1,aux->vertice_dest+1,aux->peso);
  162. aux = aux->prox;
  163. }
  164. }
  165. fclose(out);
  166. }
  167. Grafo *abreGrafo()
  168. {
  169. int origem,destino,pes,nvert;
  170. FILE *in = fopen("in.txt","r");
  171. if(in == NULL) return NULL;
  172.  
  173. fscanf(in,"%d\n",&nvert);
  174. Grafo *g = Cria_Grafo(nvert);
  175.  
  176. while(!feof(in))
  177. {
  178. fscanf(in,"%d %d %d\n",&origem,&destino,&pes);
  179. Insere_aresta(g,origem-1,destino-1,pes,1);
  180.  
  181. }
  182. fclose(in);
  183. return g;
  184. }
  185.  
  186. int eh_arvore(Grafo *g)
  187. {
  188. if((g->nro_vertices == 1) || (eh_conexo(g) && (g->nro_arestas == g->nro_vertices -1))) return 1;
  189. else return 0;
  190. }
  191. Grafo *geraArvore(Grafo *g)
  192. {
  193. Grafo *arvore = Cria_Grafo(g->nro_vertices);
  194.  
  195. int i,j=0;
  196.  
  197. int comp[g->nro_vertices];
  198. for(i=0;i<arvore->nro_vertices;i++) //Inicialmente cada vertice tem seu proprio componente conexo
  199. {
  200. comp[i] = i;
  201. }
  202.  
  203. //imprimePesos(g->lpesos);
  204.  
  205. //printf("\nArestas sendo inseridas:\n");
  206. while(j<g->nro_arestas) //enquanto tivermos arestas vemos tentar gerar a arvore
  207. {
  208.  
  209.  
  210. int v1,v2,peso;
  211. getelemento(g->lpesos,j,&v1,&v2,&peso); //Pega a aresta de posição J na lista de pesos ordenados;
  212.  
  213. //Se o componente do vertice 1 for diferente do vertice 2, não temos inserção de ciclo. Podemos assim inserir a aresta.
  214. if(comp[v1] != comp[v2])
  215. {
  216. Insere_aresta(arvore,v1,v2,peso,1);
  217. //printf("A aresta(%d %d %d) foi inserida.\n",v1+1,v2+1,peso);
  218.  
  219. //compara o valor, para pegar o menor componente conexo e fazer a troca
  220. if(comp[v1] < comp[v2]) diminuiComponente(comp,v1,v2,arvore->nro_vertices);
  221. else diminuiComponente(comp,v2,v1,arvore->nro_vertices);
  222. }
  223. if(eh_arvore(arvore))
  224. {
  225. return arvore;
  226. }
  227. j++;
  228. }
  229.  
  230. return NULL; //Ocorreu algum erro e a arvore não foi gerada.
  231. }
  232.  
  233. void diminuiComponente(int *comp,int v1,int v2,int tam) //coloca v1 e v2 no mesmo componente conexo
  234. {
  235. int i = 0;
  236. int maior = comp[v2]; //a ser retirado
  237. for(i=0;i<tam;i++)
  238. {
  239. if(comp[i] == maior) comp[i] = comp[v1];
  240. }
  241. }
  242. /*----------------------------------------T2----------------------------------------------*/
  243.  
  244. int getPeso(Grafo *g, int org, int dest) //Pega o peso da aresta (ORIG,DEST)
  245. {
  246. Aresta *aux = g->arestas[org];
  247.  
  248. while(aux != NULL)
  249. {
  250. if(aux->vertice_dest == dest) return aux->peso;
  251. aux = aux->prox;
  252. }
  253. return -1;
  254. }
  255. int existeAresta(Grafo *g, int org, int dest) //Pega o peso da aresta (ORIG,DEST)
  256. {
  257. Aresta *aux = g->arestas[org];
  258.  
  259. while(aux != NULL)
  260. {
  261. if(aux->vertice_dest == dest) return 1;
  262. aux = aux->prox;
  263. }
  264. return 0;
  265. }
  266.  
  267. void ExchangeCharacters(int str[], int p1, int p2) // troca as posicoes do array
  268. {
  269. int tmp;
  270. tmp = str[p1];
  271. str[p1] = str[p2];
  272. str[p2] = tmp;
  273. }
  274. //troca os items, fixando uma posição(K) e trocando as outras posições
  275. void RecursivePermute( int array[], int k,int len,int arraymin[], int *pesomin,Grafo *g)
  276. {
  277. int i;
  278.  
  279. if (k == len) {
  280.  
  281.  
  282. int cont = 0;
  283. int somapeso = 0;
  284.  
  285. while(cont < len)// Somando todos os pesos da sequencia de vertices em STR
  286. {
  287. if(cont+1 == len) // Ultima aresta
  288. {
  289. somapeso += getPeso(g,array[cont],array[0]);
  290. }
  291. else
  292. {
  293. somapeso += getPeso(g,array[cont],array[cont+1]);
  294. }
  295. cont++;
  296. }
  297.  
  298. if(somapeso < *pesomin)// Temos uma nova sequencia com peso min
  299. {
  300. *pesomin = somapeso;
  301. //Fazer copia ARRAYMIN
  302. for(cont = 0; cont < len;cont ++)
  303. {
  304. arraymin[cont] = array[cont];
  305. }
  306. }
  307. }
  308. else
  309. {
  310. for (i = k; i < len; i++) {
  311. ExchangeCharacters( array, k, i);
  312. RecursivePermute( array, k + 1,len,arraymin,pesomin,g);
  313. ExchangeCharacters( array, i, k);
  314. }
  315. }
  316. }
  317.  
  318. Grafo *encontra_caminho(Grafo *g)
  319. {
  320. int nvert = g->nro_vertices;
  321. int array[nvert];
  322. int arraymin[nvert]; //Responsavel por guardar o menor caminho
  323. int pesomin = 99999999; //Menor peso
  324. int i;
  325.  
  326. for(i=0;i<nvert;i++) //Preenchendo array com os vertices
  327. {
  328. array[i] = i;
  329. }
  330.  
  331. RecursivePermute(array,0,nvert,arraymin,&pesomin,g);
  332.  
  333. printf("Sequencia de vertices minima: ");
  334. for(i=0;i<nvert;i++)
  335. {
  336. printf("%d",arraymin[i]+1);
  337. }
  338. //printf("\nPESO MIN: %d\n",pesomin);
  339.  
  340. //Gerando um novo grafo com a sequencia minima:
  341.  
  342. Grafo *h = Cria_Grafo(nvert);
  343.  
  344. for(i=0;i<nvert;i++)
  345. {
  346. if(i+1 == nvert)
  347. {
  348. Insere_aresta(h,arraymin[i],arraymin[0],getPeso(g,arraymin[i],arraymin[0]),1);
  349. }
  350. else
  351. {
  352. Insere_aresta(h,arraymin[i],arraymin[i+1],getPeso(g,arraymin[i],arraymin[i+1]),1);
  353. }
  354. }
  355. printf("\nCiclo gerado.(Forca bruta)\n");
  356. return h;
  357. }
  358. /*---------------------------Aproximado-----------------------------------------*/
  359. Grafo *encontra_caminho2(Grafo *g)
  360. {
  361. //Gerando a Arvore.
  362. Grafo *h = geraArvore(g);
  363. if(h == NULL)
  364. {
  365. printf("Ocorreu um erro ao gerar a arvore.");
  366. deletaGrafo(g);
  367. return NULL;
  368. }
  369.  
  370.  
  371. int i,visitados[h->nro_vertices];
  372. int caminho[h->nro_vertices];
  373.  
  374. buscaProfundidade_Grafo(h,0,visitados,caminho);
  375.  
  376. Grafo *ciclo = Cria_Grafo(g->nro_vertices);
  377.  
  378. //Inserindo as arestas do ciclo.
  379. for(i=0;i<g->nro_vertices;i++)
  380. {
  381. if(i+1 == g->nro_vertices)
  382. {
  383. Insere_aresta(ciclo,caminho[i],caminho[0],getPeso(g,caminho[i],caminho[0]),1);
  384. }
  385. else
  386. {
  387. Insere_aresta(ciclo,caminho[i],caminho[i+1],getPeso(g,caminho[i],caminho[i+1]),1);
  388. }
  389. }
  390.  
  391. //for(i=0;i<g->nro_vertices;i++) printf("Caminho[%d]: %d\n",i,caminho[i]+1);
  392. printf("Ciclo gerado.(Aproximado)\n");
  393. return ciclo;
  394. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement