Jump to content

[Resolvido] Travessias


AJBM

Recommended Posts

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();
}
Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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
Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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
Link to comment
Share on other sites

... 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
Link to comment
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
×
×
  • Create New...

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.