Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores, Grafos - Coggle Diagram
Árvores
-
-
árvores de busca binária
são árvores binárias cujos valores assinalados em seus vértices são sempre maiores que os valores assinalados nos vértices da subárvore à esquerda e menores do que os valores assinalados nos vértices da subárvore da direita.
a eficiência dos algoritmos mais importantes de busca em árvores binárias dependem da a altura h de uma árvore com n vértices:
piso(log de n [base 2]) <= h <= n - 1
uma árvore de busca binária normalmente é implementada como uma coleção de nós que correspondem aos vértices da árvore; cada nó possuirá o valor atribuído aquele vértice e dois ponteiros que apontarão para os nós a esquerda e direita daquele vértice.
-
arvores possuem algumas propriedades que grafos não apresentam, logo toda árvore é um grafo, mas nem todo grafo pode ser considerado uma árvore
um exemplo de propriedade exclusiva de árvores é que o número de arestas nunca será maior que o número de vértices: |E| = |V| - 1 (onde |E| é a cardinalidade do conjunto de arestas e |V| é a cardinalidade do conjunto de vértices
outra propriedade importante é que sempre existe um único caminho simples entre dois vértices quaisquer de uma árvore.
árvores enraizadas
é possível selecionarmos um vertice específico de uma árvore para chamá-lo de raiz, esse vértice estará no nível 0 da árvore;
todos os vértices adjacentes ao vértice raiz estarão no nível 1 da árvore; os adjacentes a estes, com exceção da raiz, estarão no nível 2, e assim por diante...
-
busca em BSTs
assumindo que a árvore foi criada e populada corretamente, a busca pode ser feida de acordo com o seguinte passo a passo:
- é recebido um elemento v com determinado valor a ser comparado recursivamente com os elementos de uma árvore.
- se a árvore for vazia, a busca já retorna a falha, caso contrário o algorítmo prossegue.
- o valor v é comparado com o valor contido no nó raíz daquela árvore: caso seja aquele desejado a busca se encerra; caso o valor contido no nó raiz seja menor do que o valor de v, a busca continua na subárvore da direita; caso o valor encontrado na raiz seja maior, a busca prossegue na subárvore da esquerda.
- o passo três é repetido utilizando agora cada vértice das subárvores que forem escolhidas; isto continua até que um dos ponteiros direcione a busca para um nó nulo (que significaria que a busca não for bem sucedida) ou até que o elemento procurado seja encontrado.
eficiência
seguindo determinado passo à passo, é possível identificar que a eficiência do algoritmo depende apenas da altura da árvore, tendo como n - 1 comparações o pior caso em uma árvore com altura = n, razão pela qual esse algoritmo é classificado na categoria de big theta(n)
ainda assim, no caso médio esse algoritmo apresenta uma eficiência classificada como
big theta(log n) o que pode ser considerado bastante eficiênte.
inserção em BSTs
a inserção em árvores binárias segue praticamente o mesmo algorítmo da busca, com a diferença que neste caso não procuramos a igualdade.
desse modo, quando chegamos ao ponteiro que aponta para o nó nulo, substituímos este por o novo elemento que será inserido na lista e agora os ponteiros do novo nó é que apontarão para o nulo.
pelo mesmo motivo, a eficiência da inserção pode ser comparada com a da busca e classificada da mesma maneira.
-
outra definião é a de floresta, que pode ser entendida como um grafo acíclico, mas não necessariamente conectado.
Grafos
Algumas definições
Vértices adjacentes
são denominados assim dois vértices que estão conectados entre si por meio de uma aresta não direcionada.
Arestas não direcionadas
são aquelas que conectam dois vértices sem atribuir direcionamento ao par, ou seja, o par (u, v) de vértices é igual ao par (v, u).
-
Vértices incidentes
assim também denominados vértices conectados diretamente por uma determinada aresta pois, em relação aquela aresta, um incidide diretamente no outro, e vice-versa.
-
Arestas direcionadas
estas são arestas que indicam direção em um grafo, indicando o sentido da leitura entre dois vértices, logo o par (u, v) é diferente do par (v, u).
-
-
-
Vértice
Também chamados de nós, são os elementos de um conjunto finito e não vazio que indicam os pontos do grafo.
Aresta
São os elementos do segundo conjunto que formam os grafos, estes tem por função conectar os vértices do mesmo - atribuindo ou não propriedades particulares (como direção ou peso, por exemplo).
-
-
Grafo esparço
em contrapartida, grafos que apresentam apenas algumas de suas possíveis arestas entre vértices, são ditos esparços
Representação de grafos
-
Matriz de adjacêcias
para um grafo de n vértices é criada uma matriz de tamanho n x n, dessa forma, para cada par de vértices (i, j) (linhas e colunas, respectivamente) é atribuído valor 1 caso exista aresta entre eles e 0 caso contrário.
Lista de adjacências
esta representação utiliza-se de listas ligadas para a indicação dos vértices que estão conectados, ou seja, existe uma lista inicial que contém todos os vértices e, à partir de cada nó desta lista, são linkadas novas listas que contém todos os vértices cujo aquele vértice está conectado.
Quando o grafo é esparço, a representação por meio de listas ligadas torna-se menos custosa em termos espaciais. Todavia, quando falamos de grafos densos, a representação matricial é mais indicada devido a quantidade de espaço requerida pelos ponteiros das listas.
Grafos ponderados
são grafos com números assinados às suas arestas; estes números podem ser chamados de pesos ou custos e são utilizados para representar valores respectivos à cada aresta.
As duas principais maneiras de representar grafos também podem ser utilizadas para representar grafos ponderados: utilizando o peso daquela aresta ao invés do número 1, para a abordagem matricial; e adicionar mais uma propriedade ao elemento nó da lista ligada (o custo).
Caminhos e ciclos
em um grafo, o caminho entre um vértice v até outro vértice u pode ser definido como a sequência de vértices adjacentes que iniciam em v e chegam até u.
se todos os vértices nesse caminho são distintos, ele é denominado simples
-
um caminho direto pode ser entendido como uma sequência de vértices conectados por arestas direcionadas que conectam o primerio par de vértices aos pares consecutivos, sem que existam ciclos neste caminho.
-
-
pela definição do livro, gráficos podem apresentar loops ou arestas que conectem um vértice a ele mesmo.
de acordo com a característica de um grafo (ser denso ou esparço) existe implicações na escolha do melhor algoritmo para tratá-lo.
um grafo é dito conectado se para todo vértice u e v existe um caminho partindo de u e chegando até v.