Problema com Algoritmo k-coloring recursivo

Programação Java
#1 
public static boolean ePossivelColorir(int tamanho, int contadorVertices, Vertice vertices[], int cores[]){
		int qtd=0, contadorCores;
		System.out.println(contadorVertices + " " + tamanho);
		if(contadorVertices<tamanho){						
			for(contadorCores=0; contadorCores < cores.length; contadorCores++){	
				for(int contadorVizinhos=0; contadorVizinhos<vertices[contadorVertices].vizinhos.size(); contadorVizinhos++){
					if(vertices[contadorVertices].vizinhos.get(contadorVizinhos).cor != cores[contadorCores]){
						qtd++;
					}
				}
				if(qtd==vertices[contadorVertices].vizinhos.size()){				
					vertices[contadorVertices].cor=cores[contadorCores];
					int aux = contadorVertices+=1;
					ePossivelColorir(tamanho, aux, vertices, cores);
				} 
				qtd=0;
			}
			return false;	
		}  else {
			return true;
		}
	}

Esse algoritmo verifica para todos os vizinhos de um vértice se uma determinada cor é utilizada, caso não seja, o vértice recebe essa cor, e o método é chamado novamente com o contadorVertices recebendo a posição do próximo vértice a ser colorido.
O problema é que o primeiro if não é respeitado. Estranhamente
existem casos onde o valor do contadorVertices é igual ao tamanho, e mesmo assim o primeiro for é executado. Detalhe que eu coloquei algumas mensagens de debug após o primeiro if, e apenas as mensagens após o primeiro for são executadas, mensagens colocadas entre o if e o primeiro for não são executadas.

Alguma ideia do que pode estar acontecendo?

#2

coloque o código que chama o método para eu debugar, com os vertices e cores ja populados

#3

[quote=wsch] public static boolean ePossivelColorir(int tamanho, int contadorVertices, Vertice vertices[], int cores[]){ int qtd=0, contadorCores; System.out.println(contadorVertices + " " + tamanho); if(contadorVertices<tamanho){ for(contadorCores=0; contadorCores < cores.length; contadorCores++){ for(int contadorVizinhos=0; contadorVizinhos<vertices[contadorVertices].vizinhos.size(); contadorVizinhos++){ if(vertices[contadorVertices].vizinhos.get(contadorVizinhos).cor != cores[contadorCores]){ qtd++; } } if(qtd==vertices[contadorVertices].vizinhos.size()){ vertices[contadorVertices].cor=cores[contadorCores]; int aux = contadorVertices+=1; ePossivelColorir(tamanho, aux, vertices, cores); } qtd=0; } return false; } else { return true; } }

Esse algoritmo verifica para todos os vizinhos de um vértice se uma determinada cor é utilizada, caso não seja, o vértice recebe essa cor, e o método é chamado novamente com o contadorVertices recebendo a posição do próximo vértice a ser colorido.
O problema é que o primeiro if não é respeitado. Estranhamente
existem casos onde o valor do contadorVertices é igual ao tamanho, e mesmo assim o primeiro for é executado. Detalhe que eu coloquei algumas mensagens de debug após o primeiro if, e apenas as mensagens após o primeiro for são executadas, mensagens colocadas entre o if e o primeiro for não são executadas.

Alguma ideia do que pode estar acontecendo?
[/quote]

Eu queria ajudar mas preciso que me envie o código completo para eu analisar.
Se quiser pode passar por MP
aí eu olho e te dou uma ajuda se possível.

Desculpa não ajudar de cara, pois ainda não tenho porte para esse tema em específico.

#4 
import java.util.ArrayList;


public class Vertice {	
	public int ID;
	public int cor;
	public ArrayList<Vertice> vizinhos;	
	
	
	public Vertice(int ID){
		this.ID = ID;
		this.cor = -1;
		this.vizinhos = new ArrayList<Vertice>();
		
	}
	
	public void addVizinho(Vertice vizinho){
		this.vizinhos.add(vizinho);
	}
	
	public void mostraVizinhos(){
		for(int contador=0; contador<vizinhos.size(); contador++){
			System.out.print(vizinhos.get(contador).ID + "; ");
		}
		System.out.println();
	}
	
	public static boolean ePossivelColorir(int tamanho, int contadorVertices, Vertice vertices[], int cores[]){
		int qtd=0, contadorCores;
		System.out.println(contadorVertices + " " + tamanho);
		if(contadorVertices<tamanho){	
		
			for(contadorCores=0; contadorCores < cores.length; contadorCores++){	
			
				for(int contadorVizinhos=0; contadorVizinhos<vertices[contadorVertices].vizinhos.size(); contadorVizinhos++){
					if(vertices[contadorVertices].vizinhos.get(contadorVizinhos).cor != cores[contadorCores]){
						qtd++;
					}
				}
				if(qtd==vertices[contadorVertices].vizinhos.size()){				
					vertices[contadorVertices].cor=cores[contadorCores];
					int aux = contadorVertices+=1;
					ePossivelColorir(tamanho, aux, vertices, cores);
				} 
				qtd=0;
			}
			return false;	
		}  else {
			return true;
		}
	}
	
	
	public static void main(String args[]){
	
	/*
	 * Nesse algoritmo foi utilizado uma matriz de adjacências, onde as posições X e Y representam os vértices, e o valor 1 uma ligação entre vértices
	 * Por exemplo, na coordenada X = 0 e Y = 1 (segundo elemento da matriz da esquerda para a direita, de cima para baixo) existe um valor 1.
	 * Assim, entre os vértices 0 e 1 há uma ligação.
	 */
		
	/*****************************INÍCIO CONFIGURAÇÃO DO AMBIENTE****************************/	
		int numeroVertices = 5;
							    //    0,1,2,3,4
		int grafo[][] =        {/*0*/{0,1,1,1,1}, //vértices ligados ao vértice 0: 1,2,3,4
							    /*1*/{1,0,0,0,1}, //vértices ligados ao vértice 1: 0,4
							    /*2*/{1,0,0,0,0}, //vértices ligados ao vértice 2: 0
							    /*3*/{1,0,0,0,1}, //vértices ligados ao vértice 3: 0,4
							    /*4*/{1,1,0,1,0}  //vértices ligados ao vértice 4: 0,1,3
					   	       };
		
		//As cores são representadas por inteiros de 0 a 3, como por exemplo:
		//0 - Azul
		//1 - Preto
		//2 - Branco
		//3 - Cinza
		int cores[] = new int[4];
		for(int contador=0; contador<4; contador++){
			cores[contador]=contador;
		}
		
		/*
		 * Com base na matriz de adjacências cria um objeto Vertice (composto por um int (ID),
		 * um int (cor), e um ArrayList de int (vizinhos) para cada elemento do grafo, 
		 * e os adiciona a um vetor.
		 */
		
		Vertice vertices[] = new Vertice[numeroVertices];
		Vertice vertice = null;
		for(int linha=0; linha<numeroVertices; linha++){
			vertice = new Vertice(linha);			
			vertices[linha] = vertice;
		}
		
		
		for(int linha=0; linha<numeroVertices; linha++){			
			for(int coluna=0; coluna<numeroVertices; coluna++){				
				if(grafo[linha][coluna]!=0){
					vertices[linha].addVizinho(vertices[coluna]);
				}
			}
			
		}
				
		
		for(int contador=0; contador<numeroVertices; contador++){
			System.out.print("ID: "+vertices[contador].ID + "\n");			
			System.out.print("Cor: "+vertices[contador].cor + "\n");		
			System.out.print("Vizinhos: ");		
			vertices[contador].mostraVizinhos();
			System.out.println();
			
		}		
		
		Vertice.ePossivelColorir(numeroVertices, 0, vertices, cores);
	/*****************************FIM CONFIGURAÇÃO DO AMBIENTE****************************/
		
	
	}
	
	
}
#5

o if esta sendo respeitado.

o problema é de lógica.

estou analisando.

#6

montei um código aqui, porém não usei recursão…:

veja se clareia um pouco as idéias e veja também se o resultado esta correto:

Classe Vertice:

[code]package v.coloring;

import java.util.ArrayList;

public class Vertice {

public int ID;
public int cor;
public ArrayList<Vertice> vizinhos;

public Vertice(int ID) {
    this.ID = ID;
    this.cor = -1;
    this.vizinhos = new ArrayList<Vertice>();

}

public void addVizinho(Vertice vizinho) {
    this.vizinhos.add(vizinho);
}

public void mostraVizinhos() {
    for (int contador = 0; contador < vizinhos.size(); contador++) {
        System.out.print("ID: " + vizinhos.get(contador).ID + " - cor: " + vizinhos.get(contador).cor + "; " );
    }
    System.out.println();
}

}[/code]

Código Main

[code]package v.coloring;

import java.util.ArrayList;

public class VColoring {

public static Vertice[] ColorirGrafo(Vertice Vertices[],int cores[]) {
    
    for(int i=0;i<Vertices.length;i++){
        
        Vertices[i] = ColorirVertice(Vertices[i],cores);
        
    }
    
    return Vertices;
}

public static Vertice ColorirVertice(Vertice verticeAtual, int cores[]) {

    Integer corDisponivel = null;

    for (int i = 0; i < cores.length; i++) {

        if (CorDisponivel(i, verticeAtual.vizinhos)) {
            verticeAtual.cor = i;
        }

    }
    return verticeAtual;
}

public static Boolean CorDisponivel(int cor, ArrayList<Vertice> vizinhos) {

    Boolean disponivel = true;

    for (Vertice vizinho : vizinhos) {

        if (vizinho.cor == cor) {

            disponivel = false;
        }

    }
    return disponivel;
}

public static void main(String args[]) {

    int numeroVertices = 5;

    int grafo[][] = {/*0*/{0, 1, 1, 1, 1}, //vértices ligados ao vértice 0: 1,2,3,4   
        /*1*/ {1, 0, 0, 0, 1}, //vértices ligados ao vértice 1: 0,4   
        /*2*/ {1, 0, 0, 0, 0}, //vértices ligados ao vértice 2: 0   
        /*3*/ {1, 0, 0, 0, 1}, //vértices ligados ao vértice 3: 0,4   
        /*4*/ {1, 1, 0, 1, 0} //vértices ligados ao vértice 4: 0,1,3   
    };

    int cores[] = new int[4];
    for (int contador = 0; contador < 4; contador++) {
        cores[contador] = contador;
    }

    Vertice vertices[] = new Vertice[numeroVertices];
    Vertice vertice = null;
    for (int linha = 0; linha < numeroVertices; linha++) {
        vertice = new Vertice(linha);
        vertices[linha] = vertice;
    }


    for (int linha = 0; linha < numeroVertices; linha++) {
        for (int coluna = 0; coluna < numeroVertices; coluna++) {
            if (grafo[linha][coluna] != 0) {
                vertices[linha].addVizinho(vertices[coluna]);
            }
        }

    }

    for (int contador = 0; contador < numeroVertices; contador++) {
        System.out.print("ID: " + vertices[contador].ID + "\n");
        System.out.print("Cor: " + vertices[contador].cor + "\n");
        System.out.print("Vizinhos: ");
        vertices[contador].mostraVizinhos();
        System.out.println();

    }
    
     System.out.println("-------------------------------------------------");

    //processamento aqui
    Vertice VerticesPintados[] = ColorirGrafo(vertices, cores);

    for (int contador = 0; contador < numeroVertices; contador++) {
        System.out.print("ID: " + VerticesPintados[contador].ID + "\n");
        System.out.print("Cor: " + VerticesPintados[contador].cor + "\n");
        System.out.print("Vizinhos: ");
        VerticesPintados[contador].mostraVizinhos();
        System.out.println();

    }
}

}[/code]

Resultado:

ID: 0
Cor: 3
Vizinhos: ID: 1 - cor: 2; ID: 2 - cor: 2; ID: 3 - cor: 2; ID: 4 - cor: 1;

ID: 1
Cor: 2
Vizinhos: ID: 0 - cor: 3; ID: 4 - cor: 1;

ID: 2
Cor: 2
Vizinhos: ID: 0 - cor: 3;

ID: 3
Cor: 2
Vizinhos: ID: 0 - cor: 3; ID: 4 - cor: 1;

ID: 4
Cor: 1
Vizinhos: ID: 0 - cor: 3; ID: 1 - cor: 2; ID: 3 - cor: 2;

#7

Cara preciso resolver este problema utilizando recursão

Mas Obrigado pela tentativa.

#8