prim em c

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

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
////////////////////////////////////////////////
// CEFET/RJ UnED Petrópolis //
// Bernardo Costa //
// Estrutura de Dados II //
// Prim	 								 //					
// Professora Laura Assis		 //
////////////////////////////////////////////////
int **MatrizAdjacencia(int v);
void LerDadosMatrizAdjacencia(int a, int **ma, int *origem, int *destino, int *prioridade);
void ImprimirMatrizAdjacencia(int v, int **ma);
void prim(int **agm, int v, int a, int **ma, int *origem, int *destino, int *usados, int inicio, int *prioridade);
int testePrioridade(int *prioridade, int a);
int contador;
int main()
{
	int i, j, k;
	int v, a, inicio;
	inicio = 0;
	int op;
	int **ma, **agm; //ponteiro para matriz adjacencia
	ma = NULL;
		
				scanf("%d %d %d", &v, &a, &inicio);
				int prioridade[a];
				for(i = 0; i<a;i++){
					prioridade[i] = INT_MAX;
				}
				int usados[v];
				int origem [a];
				int destino [a];
				ma = MatrizAdjacencia(v);
				agm = MatrizAdjacencia(v);
				LerDadosMatrizAdjacencia(a, ma, origem, destino, prioridade);
				printf("\n\nGrafo Inicial \n");
				printf("___________________\n\n");
				ImprimirMatrizAdjacencia(v, ma);
				printf("___________________\n\n");
				prim(agm, v, a, ma, origem, destino, usados, inicio, prioridade);
				
		
return 0;
}
int **MatrizAdjacencia(int v)
{
	int **ma;	
	int i;
	
	ma = (int **) calloc(v, sizeof(int*));
	if(ma == NULL)
	{
		printf("\nErro ao reservar memória\n");
		exit(0);	
	}
	for(i = 0; i<v;i++)
	{
		ma[i] = calloc(v, sizeof(int));
		if(ma[i] == NULL)
		{
			printf("\nErro ao reservar memória para ma[%d]\n", i);
			exit(1);		
		}
	}
	
return ma;
}
void LerDadosMatrizAdjacencia(int a, int **ma, int *origem, int *destino, int *prioridade)
{
	int i, j, k, peso;
	
	for(k = 0;k < a; k++)
	{
		scanf("%d %d %d", &i, &j, &peso);
		prioridade[k] = peso;
		origem[k] = i-1;
		destino[k] = j-1;
		if(i == j)
		{
			ma[i-1][j-1] = peso;	
			ma[j-1][i-1] = peso;
		}
		else
		{
			ma[i-1][j-1] = peso;	
			ma[j-1][i-1] = peso;	
		}
	}
	
}
void ImprimirMatrizAdjacencia(int v, int **ma)
{
	int i, j;
	
	for(i=0;i<v;i++)
	{
		for(j=0;j<v;j++){
			printf(" %d ", ma[i][j]);
		}	
		printf("\n");
	}
}
void prim(int **agm, int v, int a, int **ma, int *origem, int *destino, int *usados, int inicio, int *prioridade){
	int i, j, k, c;
	c =0;
	int pai[v];
	int menor = INT_MAX;
	if (inicio == 0){
		inicio = 1;
	}
	inicio --;
	for(i = 0; i < v; i++){
		pai[i] = -1;
	}
	k = 0;
	pai[inicio] = -2; //inicio não tem pai
	for(i = 0; i < v; i++){
		usados[i] = 0;
	}
	
	usados[inicio] = 1; // vai ser o incio, então ele está automaticamente usado!
	
	printf("\n\nAGM Resultante\n");
	printf("___________________\n\n");	
	
	while(testePrioridade(prioridade, a)) {
	
	
		menor = INT_MAX;
		for(i = 0; i < a; i++){
			if( (prioridade[i] < menor)&& ( (usados[destino[i]] ==1 ) || (usados[origem[i]] ==1 ) ) ) {
				menor = prioridade[i];
				k = i;
			}
		}
		
		agm[origem[k]][destino[k]] = menor;
		agm[destino[k]][origem[k]] = menor;
		pai[destino[k]] = origem[k];
		usados[destino[k]] = 1;
		usados[origem[k]] = 1;
		ma[origem[k]][destino[k]] = 0;
		ma[destino[k]][origem[k]] = 0;
		for(i = 0; i < a; i++){
			if((usados[destino[i]] == 1)&&(usados[origem[i]] == 1))
				prioridade[i] = INT_MAX;
		}
		
		c++;
		prioridade[k] = INT_MAX;
		
		printf("(%d,%d) ", origem[k]+1, destino[k]+1);
		
	}
	printf("\n___________________\n\n");
}
int testePrioridade(int *prioridade, int a){
	int i, b = 0;
	for(i = 0; i< a; i++){
		if (prioridade[i] != INT_MAX){
			b++;
		}
	}
	//printf("\nA %d e B %d\n", a, b);
	if (b)
		return 1;
	else{
		return 0;
	}
}