Continuando nossos estudos em Java sobre Grafos, vamos ver agora como fazer pesquisas em grafos usando nossa classe Java. Neste post veremos um vídeo com introdução a duas pesquisas em grafos: pesquisa em largura e pesquisa em profundidade.
Na primeira busca a gente começa pelo vértice raiz e explora todos os vértices vizinhos. Então, para cada um desses vértices mais próximos, exploramos os seus vértices vizinhos inexplorados e assim por diante, até que ele encontre o alvo da busca.
Já na segunda busca (em profundidade), como o próprio nome indica, a gente começa num nó raiz (da mesma forma que na busca em largura), só que agora a gente explora tanto quanto possível cada um dos seus ramos, antes de retroceder. Isto é, a gente seleciona um dos filhos da raiz e daí um de seus filhos e assim por diante até chegar em um nó final (que não tem filhos). Só aí a gente, retrocede para continuar a busca.
Neste post vamos ver como utilizar a classe Graphics para desenhar figuras fractais usando Java. Utilizamos como base a classe de fractais apresentada no livro de Deitel. Se você está começando vale a pena ler este livro. Ele é bastante completo. O texto é fácil de ler, apesar de que eu acho o layout meio bagunçado. Neste post vamos ver uma variação do que é apresentado no livro do Deitel.
Para entender como a classe gera o fractal sugiro ler o livro do Deitel. Não entrarei nestes detalhes aqui. A explicação do livro é bastante elaborada. Se alguém ainda tiver uma dúvida, poste no comentário que eu tentarei explicar com mais detalhes.
Para entender como as coisas (pontos, retas, círculos etc) são desenhadas na tela, é importante entender como funcionam as coordenadas da tela. A origem é no canto superior esquerdo da tela. O eixo x (horizontal) começa na esquerda e cresce em direção a direita. O eixo y (vertical) começa de cima e cresce para baixo. A figura abaixo mostra melhor como identificar um ponto na tela.
Para desenhar um ponto, precisamos somente de 3 coisas (três ?): os valores de x e y e a cor do ponto.
Para desenhar uma reta precisamos de informação para posicionar 2 pontos e da cor.
O Java as coordenadas são colocadas nesta mesma ordem: primeiro a largura (eixo horizontal x ou width em inglês), depois a altura (eixo vertical y ou height em inglês).
Para podermos desenhar precisamos ter acesso à classe Graphics. Como vamos fazer isto? Simples, os componentes GUI normalmente possuem um método public void paintComponent( Graphics g ). Qual é o parâmetro do método? Isto mesmo, é Graphics. Desta forma poderemos usar g para desenhar uma reta por exemplo com g.drawLine(x1, y1, x2, y2).
Se você olhar na documentação do Java não verá um método denominado ponto ou círculo, tipo um drawPoint. Para desenhar um ponto, use drawLine com x1=x2 e y1=y2. Para desenhar um círculo, use drawOval com width=height.
Os métodos drawXXXX desenham somente o contorno. Para preencher o interior é necessário usar fillXXXX. Por exemplo drawOval(20,30,10,10) desenha uma circunferência no ponto x=20, y=30 e com raio igual a 10. É só aquela linha do contorno. Para ter um círculo, você deve usar fillOval(20,30,10,10).
No início eu falei da cor, mas vocês já devem ter visto que não faz parte dos parâmetros de desenho. A classe Graphics possui setColor(cor) que determinar a cor corrente. Por exemplo, se queremos desenhar 2 círculos, um verde e outro azul temos que fazer:
Uma árvore splay é uma árvore de busca binária auto-ajustável de tal forma que os elementos acessados mais recentemente, serão mais rapidamente acessados em seguida em função um rearranjo da estrutura da árvore.
Podemos executar sobre os elementos da árvore splay as seguinte operações básicas: inserção, pesquisa e remoção em tempo amortizado de O (log n).
A árvore splay foi inventado por Daniel Domingos Sleator e Robert Endre Tarjan em 1985.
