Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

AJBM

[Resolvido] Travessias

Recommended Posts

AJBM

Eu sei que o BFS e travessia em largura, e DFS é em profundidade.

Eu queria saber era qual o resultado do BFS e DFS, no grafo em cima.

Share this post


Link to post
Share on other sites
HappyHippyHippo

depende :

- a implementação da estrutura que guarda o grafo

- da ordem que os nós e arestas estão guardados

- qual a origem

- qual o destino

conclusão, podes saber o que é o BFS e o DFS, mas não sabes para que serve


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
AJBM

Tendo em conta que o BFS, ponto inicial A, porque que da este resultado A B D C E F G I H J K

O meu problema é que eu tive de fazer isto no teste, sem auxilio de computador, ou seja, tinha de saber o resulta fazendo "a mao"


protected Iterator<T> iteratorBFS(int startIndex) throws
		EmptyCollectionException {
Integer x;
	LinkedQueue<Integer> traversalQueue = new LinkedQueue<Integer>();
	ArrayUnorderedList<T> resultList = new ArrayUnorderedList<T>();
	if (!indexIsValid(startIndex)) {
		return resultList.iterator();
	}
	boolean[] visited = new boolean[numVertices];
	for (int i = 0; i < numVertices; i++) {
		visited[i] = false;
	}

	traversalQueue.enqueue(new Integer(startIndex));
	visited[startIndex] = true;
	while (!traversalQueue.isEmpty()) {
		x = traversalQueue.dequeue();
		resultList.addToRear(vertices[x.intValue()]);
		/** Find all vertices adjacent to x that have not been
		visited and queue them up */
		for (int i = 0; i < numVertices; i++) {
			if ((adjMatrix[x.intValue()][i] < Double.POSITIVE_INFINITY)
					&& !visited[i]) {
				traversalQueue.enqueue(new Integer(i));
				visited[i] = true;
			}
		}
	}
	return resultList.iterator();
}

Share this post


Link to post
Share on other sites
pmg

Para onde podes ir a partir do 1 elemento A (A)?: para o B (AB) e para o D (ABD)

Para onde podes ir a aprtir do 2 elemento B?: para o A (ja visitado), para o C (ABDC), para o D (ja visitado) e para o E (ABDCE)

Para onde podes ir a partir do 3 elemento D?: para o A (ja visitado), para o B (ja visitado), para o E (ja visitado), para o F (ABDCEF), e para o G (ABDCEFG)

...


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
AJBM

Porque que ele em vez de ir de AD foi AB???

Porque que ele nao foi de ABDC para I e foi ABDC para E

Share this post


Link to post
Share on other sites
HappyHippyHippo

Porque que ele em vez de ir de AD foi AB???

Porque que ele nao foi de ABDC para I e foi ABDC para E

exactamente ...

eu até pergunto algo ainda antes,

se o ponto inicial é A, o que diz que B é antes de D ?

por outras palavras: se me apresentassem um problema somente com o desenho a perguntar qual o resultado de uma BFS e de uma DFS, eu perguntava ao professor se achava que eu era burro o suficiente para tentar resolver o problema sem informação necessária para poder dar uma resposta concreta.

quanto muito poderia dar uma resposta válida de um conjunto de várias respostas válidas

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pmg

O primeiro no foi o A;

nos visitados: A

nos 'expandidos' (da lista de visitados): nenhum

No a 'expandir': A

Os nos a seguir sao os vizinhos de A (a ordem e arbitraria, mas eu segui a ordem alfabetica) ... portanto nos B e D

nos visitados: A, B, e D

nos 'expandidos' (da lista de visitados): A

no a 'expandir': B

Os vizinhos de B sao A, C, D, e E

...


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
AJBM

Então AD e AB era a mesma coisa?

Ja agora Árvore binária completa com altura h é uma em que todos os nós do nível 1 ao h-2 têm dois filhos e todos os filhos dos nós no nível h-1 são contíguos e à esquerda da árvore.

o que são nós contiguos?

Edited by AJBM

Share this post


Link to post
Share on other sites
pmg

Acho que vais gostar de ler o artigo seguinte na Wikipedia:

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Ve tambem, no fundo da pagina, link para outros tipos de arvores ...

Tambem deves gostar do artigo sobre estruturas de dados: http://en.wikipedia.org/wiki/Data_structure


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
AJBM

ok.obrigado.

Eu já tive a ler mas não encontro nada sobre os nos contíguos, por acaso não sabes o que são

Share this post


Link to post
Share on other sites
HappyHippyHippo

Ja agora Árvore binária completa com altura h é uma em que todos os nós do nível 1 ao h-2 têm dois filhos e todos os filhos dos nós no nível h-1 são contíguos e à esquerda da árvore.

onde "sacaste" este definição ?

o que é feito da :

"Árvore binária completa com altura h é uma que tens altura h-1 em que todos os nós na linha h-1 estão preenchidos"

exemplo para h=2

h=0 |       3
   |      / \
h=1 |     1   5
   |    / \ / \
h=2 |    0 2 4 6


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
AJBM

ok obrigado :thumbsup:

Ja agora alguém me pode ajudar a fazer as travessias level order, in order, pos order e pre order ?

Share this post


Link to post
Share on other sites
fearz7

completa que dizer : na última linha, todos os nós estão preenchidos

O que referes não será uma árvore cheia?

Share this post


Link to post
Share on other sites
HappyHippyHippo

O que referes não será uma árvore cheia?

diz-me tu então a diferença entra cheia e completa (se existir)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
fearz7

Segundo o meu prof:

-Árvore binária cheia com altura h é uma árvore em que todos os nós no nível 1 ao nível h – 1 têm dois filhos.

-Uma árvore binária com altura h é considerada completa se estiver balanceada e se todas as folhas no nível h-1 estiverem no lado esquerdo da árvore.

São conceitos diferentes.

Share this post


Link to post
Share on other sites
HappyHippyHippo

... estás a dizer que isto é completo :

h=0 |       3
   |      / \
h=1 |     1   5
   |    / \ 
h=2 |    0 2 

<irony>faz imenso sentido</irony>

ps : só aceitarei essa definição com apresentação de documentação

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
fearz7

Aqui tens .. não estou a inventar nada e já consultei outras fontes e dizem o mesmo que eu referi!

Documentação

Slide 22

Edited by fearz7

Share this post


Link to post
Share on other sites
HappyHippyHippo

foi verificar e nem essa definição é correcta:

http://xlinux.nist.gov/dads//HTML/completeBinaryTree.html

complete binary tree

(data structure)

Definition: A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

isso não quer dizer que tenham de estar à esquerda, mas que estejam o mais à esquerda possível

a seguinte árvore é considerada completa:

h=0 |       3
   |      / \
h=1 |     1   5
   |    / \ /
h=2 |    0 2 4


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
fearz7

... estás a dizer que isto é completo :

h=0 | 3
 | / \
h=1 |1 5
 |/ \
h=2 |0 2

<irony>faz imenso sentido</irony>

ps : só aceitarei essa definição com apresentação de documentação

Sendo assim esta também é completa. E não precisa que todos os nós do último nível tenham dois filhos obrigatoriamente como referiste anteriormente.

Edited by fearz7

Share this post


Link to post
Share on other sites
HappyHippyHippo

Sendo assim esta também é completa. E nao precisa que os nós do ultimo nivel tenham dois filhos obrigatoriamente como referiste anteriormente.

eu sei o que escrevi, eu foi verificar, e já rectifiquei.

agora vai para a aula e rectifica o teu professor


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.