Mensagens

A mostrar mensagens de Abril, 2012

Estruturas de dados não lineares (Parte V)

Imagem
Representação de Grafos

 Os Grafos podem ser representados de duas formas:
Lista de adjacência 
                                                                               ou
Matriz de adjacência


Lista de adjacência
  Dentro de um array, vector em português, cada posição terá o indice de um Vértice do Grafo, e cada posição dessearray, vector em português, terá o enderço para um lista das ligações que esse Vértice tiver.

Vamos ver uma Lista de adjacência para entendermos melhor.

Matriz de adjacência
É criada um Matriz, em que cada  linha/colunaterá o numero de Vértice, e as suas ligações será respectivamente Zero,0, se não existir e um, 1, se houver ligação.


Como seria o Grafo representado por essa matriz ?



Assim:
.

Estruturas de dados não lineares (Parte IV)

Imagem
Grafos

  Estruturas chamadas de grafos, representa-se G(V,E), onde V é um conjunto  de objectos denominados vértices e E é as ligações por eles, V, existentes.

 Tipos de Grafos

Direccionais : Este tipo de Grafos como o nome diz apresentão uma direcção nas suas ligações.
Exemplo Imagine as ligações de um Grafo Direccional, com uma rua de sentido único.

Não Direccionais: Estes Grafos não tenhem direcção, ou seja, a ligação é percorrida nos dois sentidos.
                              Exemplo Imagine as ligações de um Grafo não Direccional, com uma rua de 2 sentidos.


Propriedades

Completos : Um grafo completo tem os vértices todos com ligações entre si.

Conexos    : É um grafo onde todos os vértices tenham pelo menos uma ligação.

Não Conexos : É um grafo um vértice pelo menos não tenha nenhuma ligação.

Estruturas de dados não lineares (Parte III)

 Árvores Binárias

Há varios tipos de árvores binarias (BT), o tipo mais utilizado na computação. A principal utilização é a de procura binária, ou só de procura.

  Uma árvore binária diz-se de procura, se é vazia, ou se verifica todas as seguintes
condições:

         a raiz da árvore é maior do que todos os elementos da sub-árvore esquerda;
         a raiz da árvore é menor do que todos os elementos da sub-árvore direita;
         ambas as sub-árvores são árvores binárias de procura.





   A Estrutura de dados, Árvore Binária, além de possuir uma grande característica hierárquica organizacional das informações "imputadas" em sua estrutura, essa estrutura agiliza e optimiza os processos básicos de inserção, exclusão, ordenação, etc.

  Destacar também que tal estrutura, é tão importante porque oferece grande poder, flexibilidade e eficiência quando usadas em programas de gerenciamento de bando de dados. Isso ocorre porque a informação para esses bancos de dados…

Estruturas de dados não lineares (Parte II)

Travessias de árvore

Há três tipos de travessias numa árvore:            Préordem, Inordem e Pósordem

     Tais tenhem maneiras diferentes de "passarem" e escreverem a árvore

Préordem:   R E D
                 visita primeiramente a raiz                               R
                 visita seguidamente a sub-árvore esquerda   E
                 posteriormente visita a sub-árvore direita     D

Inordem: E R D
                visita primeiramente a sub-árvore esquerda    E
                visita seguidamente a raiz                                   R
                posteriormente visita a sub-árvore direita        D

Pósorder: E D R
                visita primeiramente a sub-árvore esquerda    E
                visita seguidamente a sub-árvore direita          D                    
                posteriormente visita a raiz                                 R

para visualização dos algoritmos das travessias em metodo recursivo e iterativo
http://www.box.com/s/623z586lzv/1/204…