Teoria dos grafos

#include <stdio.h>

#include <stdlib.h>

typedef struct aresta

{

int v1;

int v2;

int peso;

} Aresta;

typedef struct grafo

{

Aresta *aresta;

} Grafo;

int min(int i, int j)

{

if(i > j)

return j;

return i;

}

int max(int i, int j)

{

if(i < j)

return j;

return i;

}

int main()

{

int i,

num_ares; //numero de arestas

char ver;

char v1, v2;

int peso;

int *v; //vetor pra contar as componentes conexas

int n_vertices; //numero de vertices

int k; //contador do vetor de arestas da arvore

int j;

Aresta aux;

Grafo g, arvore;

FILE *fp;

fp = fopen("grafo.txt", "r");

if(!fp)

{

printf("Erro na abertura do arquivo.");

exit(1);

}

//lendo numero de vertices e de arestas

fscanf(fp, "%d %d ", &n_vertices, &num_ares);

v = (int *) malloc (n_vertices*sizeof(int)); //alocando o vetor de componentes conexas

for (i = 0; i<n_vertices; i++)

v[i] = i;

//aloca o vetor de arestas

g.aresta = (Aresta*)malloc(num_ares*sizeof(Aresta)); //alocando o vetor de arestas

arvore.aresta = (Aresta*)malloc((n_vertices-1)*sizeof(Aresta)); //alocando o vetor de arvore

//lendo arestas e imprimindo o grafo

i = 0;

printf("Grafo: \n");

while(!feof(fp))

{

fscanf(fp, "%c,%c,%d ", &v1,&v2,&peso);

g.aresta[i].v1 = v1;

g.aresta[i].v2 = v2;

g.aresta[i].peso = peso;

printf("Vertice: %c ------- Vertice: %c | Peso: %d\n", g.aresta[i].v1, g.aresta[i].v2, g.aresta[i].peso);

i++;

}

//ordenar o vetor de arestas, peso

for(i=0; i < num_ares; i++)

{

for (j=0; j<num_ares - i - 1; j++)

{

if (g.aresta[j].peso > g.aresta[j+1].peso)

{

aux = g.aresta[j];