Ir para o conteúdo
AJBM

[Resolvido] Travessias

Mensagens Recomendadas

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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();
}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por HappyHippyHippo

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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?

Editado por AJBM

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Editado por HappyHippyHippo

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Editado por fearz7

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.