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); } } }