Skip to content

Instantly share code, notes, and snippets.

@MartinAngeloni
Created August 8, 2017 03:35
Show Gist options
  • Save MartinAngeloni/4eca19d81332712828b1a892f7e3e1d7 to your computer and use it in GitHub Desktop.
Save MartinAngeloni/4eca19d81332712828b1a892f7e3e1d7 to your computer and use it in GitHub Desktop.
Algoritmo para recorrer un grafo orientado
public class Grafos {
public static void main(String ... args){
Nodo nodo0 = new Nodo(0);
Nodo nodo1 = new Nodo(1);
Nodo nodo2 = new Nodo(2);
Nodo nodo3 = new Nodo(3);
Nodo nodo4 = new Nodo(4);
Nodo nodo5 = new Nodo(5);
Nodo nodo6 = new Nodo(6);
Nodo nodo7 = new Nodo(7);
Nodo nodo8 = new Nodo(8);
Nodo nodoBuscado = new Nodo(0);
nodo0.brazos.add(nodo1);
nodo0.brazos.add(nodo4);
nodo0.brazos.add(nodo3);
nodo1.brazos.add(nodo2);
nodo1.brazos.add(nodo5);
nodo1.brazos.add(nodo4);
nodo2.brazos.add(nodo5);
nodo3.brazos.add(nodo6);
nodo4.brazos.add(nodo7);
nodo4.brazos.add(nodo6);
nodo5.brazos.add(nodo7);
nodo6.brazos.add(nodo8);
nodo7.brazos.add(nodo8);
recorrido(nodo0, nodoBuscado);
}
public static void recorrido(Nodo nodo, Nodo nodoBuscado){
nodo.valorAnalizado = nodoBuscado.valor;
if (nodo.equals(nodoBuscado)){
System.out.println(nodo.valor);
nodoBuscado.valor++;
}
boolean way = true;
while(way){
way = false;
for(Nodo brazo:nodo.brazos){
if((nodoBuscado.valor >= brazo.valor) && (brazo.valorAnalizado != nodoBuscado.valor)){
recorrido(brazo,nodoBuscado);
way = true;
}
}
}
}
}
public class Nodo {
public Nodo(int valor) {
this.valor = valor;
}
public int valor;
public int valorAnalizado;
public List<Nodo> brazos = new ArrayList<>(3);
@Override
public String toString() {
return valor + "";
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Nodo nodo = (Nodo) o;
return valor == nodo.valor;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment