Busca em profundidade [ RESOLVIDO ]

27 de maio de 2010 13 respostas

lpfx 27 de maio de 2010

pessoal…
nao estou conseguindo imprimir o percurso da busca em profundidade
eu preciso que mostre o percurso completo (com as repetiçoes)

por exemplo:
eu tenho uma arvore com 5 vertices cuja raiz é o vertice 2
o vertice 2 só tem o filho 0 (vertice 0): 2->0
o vertice 0 tem os filhos 1, 3, e 4

entao a arvore ficaria assim:
2->0
0->1
0->3
0->4

represento essa arvore por uma matriz de adjacencia

o que eu quero fazer é imprimir todo o percurso da busca
no caso apresentado ficaria assim:
2->0->1->0->3->0->4->0->2

só que do jeito q eu fiz não imprime a volta na raiz
fica assim: 2->0->1->3->4

public void buscaProfundidade(Grafo grafo, int raiz) {

        percArv.add(raiz);  // array para guardar os vertices, dps só imprimo esse array

        visitados[raiz] = true;  // ja foi inicializado com false em td posiçao

        int i;
        for (i = 0; i < grafo.numV; i++) {
            if (grafo.matrizAdj[raiz][i] != 0 && visitados[i] == false) {
                buscaProfundidade(grafo, i);
            }
        }
    }

dps eu tentei assim:

public void buscaProfundidade(Grafo grafo, int raiz) {

        percArv.add(raiz);

        visitados[raiz] = true;

        int i;
        for (i = 0; i < grafo.numV; i++) {
            if (grafo.matrizAdj[raiz][i] != 0 && visitados[i] == false) {
                buscaProfundidade(grafo, i);
            }
        }
        percArv.add(raiz);  // qnd n tem + pra onde ir guarda a raiz anterior
    }

o problema é como vou guardar a raiz anterior?
pra qnd chegar no 1, por ex, ver q nao tem mais filhos e guardar o 0, que é pai de 1
e fazer isso com todos

alguem pode ajudar?

13 Respostas

guisantogui 27 de mai. de 2010

Tenho muitos problemas com grafos, vou acompanhar o tópico!

pmlm 27 de mai. de 2010

O que é esse percArv?

CarvalR2 27 de mai. de 2010

Este rascunho ajudaria?

public class Teste {

public static void main(String args[]) {
	No f1 = new No("2");
	No f2 = new No("2.0");
	f1.filhos.add(f2);
	
	No f3 = new No("2.0.1");
	No f4 = new No("2.0.2");
	No f5 = new No("2.0.3");		
	f2.filhos.add(f3);
	f2.filhos.add(f4);
	f2.filhos.add(f5);
	
	f4.filhos.add(new No("2.0.2.1"));
	
	buscaProfundidade(f1);
	
}

private static void buscaProfundidade(No base) {
	if (base.filhos.isEmpty()) {
		System.out.println(base.valor);
	}
	for (No filho : base.filhos) {
		System.out.println(base.valor);
		buscaProfundidade(filho);
	}
}

}

class No {

public String valor;

public List<No> filhos = new ArrayList<No>();

public No(String valor) {
	this.valor = valor;
}

}

CarvalR2 27 de mai. de 2010

Este rascunho ajudaria?

public class Teste {

public static void main(String args[]) {
	No f1 = new No("2");
	No f2 = new No("2.0");
	f1.filhos.add(f2);
	
	No f3 = new No("2.0.1");
	No f4 = new No("2.0.2");
	No f5 = new No("2.0.3");		
	f2.filhos.add(f3);
	f2.filhos.add(f4);
	f2.filhos.add(f5);
	
	f4.filhos.add(new No("2.0.2.1"));
	
	buscaProfundidade(f1);
	
}

private static void buscaProfundidade(No base) {
	if (base.filhos.isEmpty()) {
		System.out.println(base.valor);
	}
	for (No filho : base.filhos) {
		System.out.println(base.valor);
		buscaProfundidade(filho);
	}
}

}

class No {

public String valor;

public List<No> filhos = new ArrayList<No>();

public No(String valor) {
	this.valor = valor;
}

}

Abdon 27 de mai. de 2010

Vc já ouvio falar em DFS??

A tecnica consiste, a grosso modo, em um colocar o primeiro vertice em uma pilha, quando vc retira-lo, coloque os filhos dele na fila.

Assim vc não precisa guardar o vertice anterior.

O oposto se da utilizando a estrutura de fila e se chama Breadth-first search

Basicamente a idéia é a mesma e o algoritmo é bem simples

lpfx 27 de mai. de 2010

é um array que guarda o vertice visitado
percArv = percurso da arvore

lpfx 27 de mai. de 2010

CarvalR2:

Este rascunho ajudaria?

public class Teste {

public static void main(String args[]) {
	No f1 = new No("2");
	No f2 = new No("2.0");
	f1.filhos.add(f2);
	
	No f3 = new No("2.0.1");
	No f4 = new No("2.0.2");
	No f5 = new No("2.0.3");		
	f2.filhos.add(f3);
	f2.filhos.add(f4);
	f2.filhos.add(f5);
	
	f4.filhos.add(new No("2.0.2.1"));
	
	buscaProfundidade(f1);
	
}

private static void buscaProfundidade(No base) {
	if (base.filhos.isEmpty()) {
		System.out.println(base.valor);
	}
	for (No filho : base.filhos) {
		System.out.println(base.valor);
		buscaProfundidade(filho);
	}
}

}

class No {

public String valor;

public List<No> filhos = new ArrayList<No>();

public No(String valor) {
	this.valor = valor;
}

}

não entendi direito esse codigo não :?

lpfx 27 de mai. de 2010

ovelha:
Vc já ouvio falar em DFS??

A tecnica consiste, a grosso modo, em um colocar o primeiro vertice em uma pilha, quando vc retira-lo, coloque os filhos dele na fila.

Assim vc não precisa guardar o vertice anterior.

O oposto se da utilizando a estrutura de fila e se chama Breadth-first search

Basicamente a idéia é a mesma e o algoritmo é bem simples

wikipedia:

Enqueue the root node.

Dequeue a node and examine it.
* If the element sought is found in this node, quit the search and return a result.
* Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.

If the queue is empty, every node on the graph has been examined ? quit the search and return “not found”.

Repeat from Step 2.

não tem como guardar o vertice anterior?

pmlm 27 de mai. de 2010

é um array que guarda o vertice visitado
percArv = percurso da arvore

Array, não é de certeza. List, Set?

lpfx 27 de mai. de 2010

é um array que guarda o vertice visitado
percArv = percurso da arvore

Array, não é de certeza. List, Set?

ArrayList de inteiros

lpfx 28 de mai. de 2010

acho q resolvi, ainda tem uns errinhos, mas ta quase… fiz assim:

int k = 0; // variável global

        buscaProfundidade(arvGeradora, raiz); // chama o metodo

        // dps de chamar o método, faz a ultima posiçao = a primeira
        percArv.add(k, percArv.get(0));

        // metodo
        public void buscaProfundidade(Grafo grafo, int raiz) {

        ciclo.add(raiz);
        percArv.add(k, raiz);

        visitados[raiz] = true;

        int i;
        for (i = 0; i < grafo.numV; i++) {
            if (grafo.matrizAdj[raiz][i] != 0 && visitados[i] == false) {
                k++;
                buscaProfundidade(grafo, i);
            }
        }
        k++;
        percArv.add(k, percArv.get(k - 2));  // qnd n tem + filhos guarda a raiz anterior
    }

lpfx 28 de mai. de 2010

lpfx:

acho q resolvi, ainda tem uns errinhos, mas ta quase… fiz assim:

int k = 0; // variável global

        buscaProfundidade(arvGeradora, raiz); // chama o metodo

        // dps de chamar o método, faz a ultima posiçao = a primeira
        percArv.add(k, percArv.get(0));

        // metodo
        public void buscaProfundidade(Grafo grafo, int raiz) {

        ciclo.add(raiz);
        percArv.add(k, raiz);

        visitados[raiz] = true;

        int i;
        for (i = 0; i < grafo.numV; i++) {
            if (grafo.matrizAdj[raiz][i] != 0 && visitados[i] == false) {
                k++;
                buscaProfundidade(grafo, i);
            }
        }
        k++;
        percArv.add(k, percArv.get(k - 2));  // qnd n tem + filhos guarda a raiz anterior
    }

é… desse jeito não funciona tb =\

lpfx 29 de mai. de 2010

Resolvido! \o/

public void buscaProfundidade(Grafo grafo, int raiz) {  
  
    percArv.add(raiz);  
  
    visitados[raiz] = true;  
  
    int i;  
    for (i = 0; i < grafo.numV; i++) {  
        if (grafo.matrizAdj[raiz][i] != 0 && visitados[i] == false) {  
            buscaProfundidade(grafo, i); 
            percArv.add(raiz); 
        }  
    }  
}

Criado 27 de maio de 2010

Ultima resposta 29 de mai. de 2010

Respostas 13

Participantes 5

13 Respostas

Topicos relacionados