Bom, como trabalho da faculdade, tenho que criar um algoritmo que, dado certo arquivo com *x* números, seja capaz de verificar qual a maior sequência de números que, em base 6, respeitem as as seguintes regras:

 1. A sequência deve ser crescente
 2. De um número para outro da sequência, somente um dígito pode mudar

Um exemplo seria:

> O arquivo contém os números 782, 229, 446, 527, 874, 19, 829, 70, 830, 992, 430 e 649.

> Ou seja, em base 6: 3342, 1021, 2022, 2235, 4014, 31, 3501, 154, 3502, 4332, 1554 e 3001.

> Portanto, a maior sequência respeitando essas regras seria: 649, 829 e 830, que corresponde a 3001, 3501 e 3502 em base 6.

Certo, os arquivos não são assim tão simples, há arquivos que chegam a ter até 100.000 números, portanto, criei um grafo. Eu tentei tanto com matriz como com lista de adjacências. Adicionar os vértices e as arestas (ou seja, quais são os números que respeitam as regras para um número *x*) não foi um problema, meu problema é caminhar no grafo, pois pesquisando na internet só achei caminhamento mínimo, mas o que eu preciso é: achar o maior caminho.

Tentei com DFS mas o resultado não é o que eu quero.

Meu código é o seguinte:

    import java.io.BufferedReader;
    import java.io.FileNotFoundException;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.*;

    public class DirectedGraphList
    {
    	private class Vertice
    	{
    		private String item;
    		private boolean Visitado;
    		private ArrayList<Vertice> lst = new ArrayList<Vertice>();
    
    		public Vertice(String item) {
    			this.item = item;
    		}
    		public String getItem() {
    			return this.item;
    		}
    		public void setItem(String item) {
    			this.item = item;
    		}
    		public void addAdjacent(Vertice v) {
    			if (!lst.contains(v))
    				lst.add(v);
    		}
    		public ArrayList<Vertice> getAdjacents() {
    			return lst;
    		}
    		public Vertice getAdjacent(int i) {
    			Vertice res = null;
    			if ((i >= 0) && (i < lst.size()))
    				res = lst.get(i);
    			return res;
    		}
    		public int getDegree(){
    			return lst.size(); 
    		}
    	}
    
    	private ArrayList<Vertice> vert;
    
    	public DirectedGraphList() {
    		vert = new ArrayList<Vertice>();
    	}
    
    	private Vertice searchVerticeRef(String item)
    	{
    		Vertice res = null;
    		int i;
    
    		for (i = 0; ((i < vert.size()) && !vert.get(i).getItem().equals(item)); i++);
    
    		if (i < vert.size())
    			res = vert.get(i);
    
    		return res;
    	}
    
    	public void addVertice(String item)
    	{
    		if (searchVerticeRef(item) == null) 
    		{
    			Vertice novo = new Vertice(item);
    			vert.add(novo);
    		}
    	}
    
    	public void addEdge(String strOrig, String strDest)
    	{
    		Vertice vAux1 = searchVerticeRef(strOrig);
    		Vertice vAux2 = searchVerticeRef(strDest);
    
    		if (vAux1 == null)
    			throw new IllegalArgumentException("Aresta origem invalida: " + strOrig);
    		else if (vAux2 == null)
    			throw new IllegalArgumentException("Aresta destino invalida: " + strDest);
    		else
    		{
    			vAux1.addAdjacent(vAux2);
    		}
    	}
    
    	public int getNumVertices() {
    		return vert.size();
    	}
    
    	public int getDegree(String vertice)
    	{
    		int i, j, c = 0;
    		Vertice v = searchVerticeRef(vertice);
    		if (v != null)
    		{
    			// grau de saida
    			c += v.getDegree();
    
    			// grau de entrada
    			for (i = 0; i < vert.size(); i++)
    			{
    				if (!vert.get(i).getItem().equals(vertice))
    				{
    					for (j = 0; j < vert.get(i).getDegree(); j++)
    					{
    						if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
    							c++;
    					}					
    				}
    			}
    		}
    		return c;
    	}
    
    	public ArrayList<String> getAllAdjacents(String vertice)
    	{
    		ArrayList<String> res = null;
    		Vertice v = searchVerticeRef(vertice);
    		if (v != null)
    		{
    			res = new ArrayList<String>();
    			for (int j = 0; j < v.getDegree(); j++)
    				res.add(v.getAdjacent(j).getItem());
    		}
    		return res;
    	}
    
    	public ArrayList<String> getSources()
    	{
    		ArrayList<String> res = new ArrayList<String>();
    		boolean checked;
    		String vertice;
    
    		for (int k=0; k<vert.size(); k++)
    		{
    			vertice = vert.get(k).getItem();
    
    			checked = false;
    			for (int i=0; i<vert.size(); i++)
    			{
    				for (int j=0; j<vert.get(i).getDegree(); j++)
    				{
    					if (vert.get(i).getAdjacent(j).getItem().equals(vertice))
    					{
    						checked = true;
    						break;
    					}
    				}
    			}
    
    			if (!checked)
    				res.add(vertice);
    		}
    		return res;
    	}
    
    	public ArrayList<String> getSinks()
    	{
    		ArrayList<String> res = new ArrayList<String>();
    
    		for (int i=0; i<vert.size(); i++)
    		{
    			if (vert.get(i).getAdjacents().isEmpty())
    				res.add(vert.get(i).getItem());
    		}
    		return res;
    	}
    
    	public void showInfo()
    	{
    		System.out.print("V = { ");
    		for (int i = 0; i < vert.size()-1; i++)
    			System.out.printf("%s, ", vert.get(i).getItem());
    		System.out.printf("%s }\n", vert.get(vert.size()-1).getItem());
    
    		ArrayList<String> arestas = new ArrayList<String>();
    		for (int i = 0; i < vert.size(); i++)
    			for (int j = 0; j < vert.get(i).lst.size(); j++)
    				arestas.add(String.format("(%s, %s)", vert.get(i).getItem(), vert.get(i).getAdjacent(j).getItem()));
    
    		System.out.print("E = {\n");
    		if (!arestas.isEmpty()) {
    			System.out.printf("      %s", arestas.get(0));
    
    			for (int i = 1; i < arestas.size(); i++)
    				System.out.printf(",\n      %s", arestas.get(i));
    		}
    		System.out.println("\n    }");
    	}
    	public static void criaArray(ArrayList<Integer> a,String nome) throws FileNotFoundException{
    		try{
    			FileReader ler= new FileReader(nome);
    			BufferedReader arq=new BufferedReader(ler);
    			int parsedStr;
    			String str=arq.readLine();
    			while(str!=null){
    				parsedStr=Integer.parseInt(str);
    				a.add(parsedStr);
    				str=arq.readLine();
    			}
    		}
    		catch(IOException e){
    			System.out.println("Erro na abertura do arquivo: "+
    					e.getMessage());
    		}
    	}
    	public static int diferente(String a,String b){
    		int diferentes=0;
    		if(a.length()==b.length()){
    			for(int i=0;i<a.length();i++){
    				if(a.charAt(i)!=b.charAt(i))
    					diferentes++;
    			}
    		}
    		else 
    			diferentes=2;
    		return diferentes;
    	}
    
    	public static boolean possibilidades(DirectedGraphList graph,String a,ArrayList<Integer> array){
    		int diferentes=0;
    		for(int i=0;i<array.size();i++){
    			String numero=Integer.toString(array.get(i),6);
    			diferentes=diferente(numero,a);
    			if(diferentes==1){
    				graph.addEdge(a,numero);
    			}	
    		}
    		return true;
    	}
    	
    	public void DFS(Vertice a){
    		a.Visitado=true;
    		for(int i=0;i<a.lst.size();i++){
    			Vertice b=a.lst.get(i);
    			if(!b.Visitado){
    				DFS(b);
    			}
    		}
    	}
    
    	public static void main(String[] args) throws FileNotFoundException
    	{
    		ArrayList<Integer> numeros=new ArrayList<Integer>();
    		criaArray(numeros,"/home/geovane/Documentos/CC/ALPROII/teste5000b");
    		DirectedGraphList g = new DirectedGraphList();
    		HeapSort.heapsort(numeros);
    		for(int j=0;j<numeros.size();j++){
    		g.addVertice(Integer.toString(numeros.get(j),6));
    		}
    		for(int i=0;i<numeros.size();i++){
    			String numer=Integer.toString(numeros.get(i), 6);
    			possibilidades(g,numer,numeros);
    		}
    	}
    }