heuristica

//Implementação da heuristica

bool colorirGrafo_Heuristica_(Grafo* grafo, int min) {    //pra ser bool tem que adaptar o codigo pra verificar T e F

    // Opt 1 Algoritmo ingenuo
    /*  Supondo uma ordem de percurso dos vértices. Atribuimos uma cor ao primeiro vértice.
    Depois, percorremos sequencialmente todos os vértices. Para cada vértice v visitado,
    consideramos as cores já utilizadas. A primeira cor que não pertence a nenhum dos
    vértices adjacentes a v será escolhida para colorir v. Se os vértices adjacentes
    coloridos já usam todas as cores, o vértice v será colorido com uma nova cor.
    O algoritmo continua assim por diante até a coloração completa do grafo.*/
     //pseudo codigo muito confuso

//  opt 2
//  //enquanto existir vertices nao coloridos em G
//  while(   ){
//        //Entre os vertices sem cor de maior grau
//
//        //Escolha o vertice v com maior grau de coloracao
//
//        //atribua a menor cor k possivel para o vertice v : f(v) = k
//
//    }
//    //retorna a coloracao de vertices f

//opt 3

    int i , j, k;
    int fim = 1;
    int cor = 1;
    int solucoes = 0;

    //percore os vertices do grafo
    for(i = 0; i < (grafo)->n_vertices; i++){
        //se o vertice ainda nao foi colorido
        if ((grafo)->cores[i] == -1) {
            //colore vertice com a menor cor possivel
            (grafo)->cores[i] = 1;
            // verifica se existe adjacente com mesma cor
            for(j=0; j<(grafo)->n_vertices; j++) {
                if((i!=j) && ((grafo)->arestas[i][j] != -1)){
                    // se existe adjacente com mesma cor, pula para prox. cor
                    if((grafo)->cores[i] == (grafo)->cores[j]){
                        (grafo)->cores[i] ++;
                        // se ja encontrou um resultado melhor, poda ramo da arvore
                        if((grafo)->cores[i] >= min){
                            cor = 1;
                            (grafo)->cores[i] = 0;
                            for(k = 0; k < (grafo)->n_vertices; k++){
                                if( (grafo)->cores[k] > cor )
                                    cor = (grafo)->cores[j];
                            }
                            return;
                        }
                        if( cor < (grafo)->cores[i]){
                            cor = (grafo)->cores[i];
                        }
                        j=0;
                        k=0;
                    }
                }
                //repete o processo para os demais vertices nao coloridos
                colorirGrafo_Heuristica_(grafo, min);
                //descolore o vertice para tentar uma nova coloracao
                cor = 1;
                (grafo)->cores[i] = 0;
                for(k = 0; k < grafo->n_vertices; k++){
                    if( (grafo)->cores[k] > cor)
                        cor = (grafo)->cores[k];
                }
                //sinaliza que ainda nao coloriu o grafo inteiro
                fim = 0;
            }
        }
        //se coloriu o grafo inteiro:
        //incrementa o numero de solucoes testadas e atualiza o valor de cores
        if (fim){
            solucoes++;
            if( (min) > cor){
                (min = cor);
            }
        }
    }
}