A Coloração de Grafo

//Alunos: Lauro Ribeiro, Ricardo Thadeu, Veber Stutz

#include <stdio.h>

#include <stdlib.h>

//#include<locale.h>

struct grafo { //cria a struct grafo.

int V;

int A;

int **adj;

};

typedef struct grafo *Grafo; // D� um apelido para struct grafo.

struct no{

int id;

int grau;

int cor;

int colorido;

};

typedef struct no *Vertice;

Vertice criaVertice(int id){

Vertice novoVertice = (Vertice) malloc(sizeof(Vertice));

return novoVertice;

}

//fun��o para ler e atribuir valores da matriz do .txt na nossa matriz G->adj

int **recebeMatriz(Grafo G, FILE *arqEntrada, int qtdVertice){

int valor;

G->adj = (int **) malloc (G->V * sizeof(int *)); //aloca��o din�mica de mem�ria

for (int i = 0; i < G->V; i++){

G->adj[i] = (int *) malloc (G->V * sizeof(int));

}

for (int i = 0; i < G->V ; i++){

for (int j = 0; j < G->V ; j++){

fscanf(arqEntrada, "%d", &valor); //colocando valores do arquivo na matriz

G->adj[i][j]=valor;

}

}

return G->adj;

}

//fun��o para imprimir a matriz

void imprimeMatriz(Grafo G, int **adj, int qtdVertice){

printf("Matriz de Adjacencia:\n");

for (int i = 0; i < G->V ; i++){

printf("\n ");

for (int j = 0; j < G->V ; j++){

printf("%d ", G->adj[i][j]); //imprimindo matriz

}

}

printf("\n\n");

}

//fun��o para encontrar e imprimir a cobertura aproximada de v�rtices

void coberturaAprox(Grafo G, int qtdAresta){

int *cobertura, contador=0;

cobertura = (int*) malloc(G->V * sizeof(int)); //aloca��o din�mica de mem�ria

int **matrizAux; //cria matriz auxiliar para receber c�pia da matriz de adjacencia

matrizAux = (int **) malloc (G->V * sizeof(int *)); //aloca��o din�mica de mem�ria

for (int i = 0; i < G->V; i++){

matrizAux[i] = (int *) malloc(G->V * sizeof(int));

}

for(int i=0; i < G->V; i++){

for(int j=0; j < G->V; j++){

matrizAux[i][j] = G->adj[i][j]; //Faz uma c�pia da matriz de adjac�ncia

}

}

for(int i=0; i < G->V; i++){

for(int j=0; j < G->V; j++){

if(matrizAux[i][j]==1){

cobertura[i]=i+1;