Uma estrutura de dados não linear consiste em uma coleção dos elementos que são distribuídos em um plano, o que significa que não existe tal seqüência entre os elementos como existe em uma estrutura de dados linear.
Gráfico de comparação
| Base para comparação | Árvore | Gráfico |
|---|---|---|
| Caminho | Apenas um entre dois vértices. | Mais de um caminho é permitido. |
| Nó raiz | Tem exatamente um nó raiz. | O gráfico não possui um nó raiz. |
| rotações | Nenhum loop é permitido. | O gráfico pode ter loops. |
| Complexidade | Menos complexo | Mais complexo comparativamente |
| Técnicas de Traversal | Pré-encomenda, em ordem e pós-encomenda. | Pesquisa em largura e pesquisa em profundidade. |
| Número de arestas | n-1 (onde n é o número de nós) | Não definido |
| Tipo de modelo | Hierárquico | Rede |
Definição de Árvore
Uma árvore é uma coleção finita de itens de dados geralmente denominados nós. Como mencionado acima, uma árvore é uma estrutura de dados não linear que organiza itens de dados na ordem de classificação. Ele é usado para mostrar uma estrutura hierárquica entre os vários elementos de dados e organiza os dados em ramificações que relacionam as informações. A adição de uma nova borda em uma árvore resulta em uma formação do loop ou circuito.
Existem vários tipos de árvores, como uma árvore binária, árvore de pesquisa binária, árvore AVL, árvore binária, B-tree, etc. A compactação de dados, armazenamento de arquivos, manipulação da expressão aritmética e árvores de jogos são algumas das aplicações da árvore. estrutura de dados.
Propriedades da árvore:
- Há um nó designado no topo da árvore, conhecido como raiz da árvore.
- Os itens de dados restantes são divididos em subconjuntos disjuntos, referenciados como subárvore.
- A árvore é expandida em altura em direção ao fundo.
- Uma árvore deve estar conectada, o que significa que deve haver um caminho de uma raiz para todos os outros nós.
- Não contém loops.
- Uma árvore tem n-1 arestas.
Existem vários termos associados a árvores, como o nó terminal, borda, nível, grau, profundidade, floresta, etc. Entre esses termos, alguns deles descritos abaixo.
- Borda - Uma linha que conecta dois nós.
- Nível - Uma árvore é particionada em níveis de tal forma que o nó raiz está no nível 0. Então, seus filhos imediatos estão no nível 1, e seus filhos imediatos estão no nível 2 e assim por diante até o nó terminal ou folha.
- Grau - É o número de subárvores de um nó em uma determinada árvore.
- Profundidade - É o nível máximo de qualquer nó em uma determinada árvore e também é conhecido como altura .
- Nó Terminal - O nó de nível mais alto é o nó terminal, enquanto outros nós, exceto terminal e nó raiz, são conhecidos como nós não-terminais.
Definição de gráfico
Um gráfico é também uma estrutura de dados não lineares e matemáticos que pode representar vários tipos de estrutura física. Consiste em um grupo de vértices (ou nós) e um conjunto de arestas que conectam os dois vértices. Os vértices no gráfico são representados como pontos ou círculos e as arestas são mostradas como arcos ou segmentos de linha. Uma aresta é representada por E (v, w) onde v e w são os pares de vértices. A remoção de uma aresta de um circuito ou gráfico conectado cria um subgráfico que é uma árvore.
Os gráficos são classificados em várias categorias, como direcionado, não direcionado, conectado, não conectado, simples e multi-gráfico. Rede de computadores, sistema de transporte, gráfico de redes sociais, circuitos elétricos e planejamento de projetos são algumas das aplicações da estrutura de dados gráficos. Ele também é empregado na técnica de gerenciamento nomeada como PERT (avaliação de programa e técnica de revisão) e CPM (método de caminho crítico) em que a estrutura do gráfico é analisada.
Propriedades de um gráfico:
- Um vértice em um gráfico pode ser conectado a qualquer número de outros vértices usando arestas.
- Uma borda pode ser bidirecionada ou direcionada.
- Uma borda pode ser ponderada.
No gráfico também usamos vários termos como vértices adjacentes, caminho, ciclo, grau, gráfico conectado, gráfico completo, gráfico ponderado, etc. Vamos entender alguns destes termos.
- Vértices adjacentes - Um vértice a é adjacente ao vértice b se houver uma aresta (a, b) ou (b, a).
- Caminho - Um caminho de um vértice aleatório w é uma seqüência adjacente de vértices.
- Ciclo - É um caminho onde o primeiro e último vértices são os mesmos.
- Grau - É um número de arestas incidentes em um vértice.
- Gráfico conectado - Se houver um caminho de um vértice aleatório para qualquer outro vértice, esse gráfico será conhecido como um gráfico conectado.
Principais diferenças entre árvore e gráfico
- Em uma árvore, existe apenas um caminho entre quaisquer dois vértices, enquanto um gráfico pode ter caminhos unidirecionais e bidirecionais entre os nós.
- Na árvore, há exatamente um nó raiz e cada filho pode ter apenas um pai. Em contraste, em um gráfico, não há conceito do nó raiz.
- Uma árvore não pode ter loops e self-loops, enquanto o gráfico pode ter loops e auto-loops.
- Os gráficos são mais complicados, pois podem ter loops e auto-loops. Em contraste, as árvores são simples em comparação com o gráfico.
- A árvore é atravessada usando técnicas de pré-encomenda, ordem e pós-ordem. Por outro lado, para o percurso do gráfico, usamos BFS (Breadth First Search) e DFS (Depth First Search).
- Uma árvore pode ter n-1 arestas. Pelo contrário, no gráfico, não há um número predefinido de arestas e isso depende do gráfico.
- Uma árvore tem uma estrutura hierárquica, enquanto o gráfico tem um modelo de rede.
Conclusão
Gráfico e árvore são a estrutura de dados não lineares que é usada para resolver vários problemas complexos. Um grafo é um grupo de vértices e arestas onde uma aresta conecta um par de vértices enquanto uma arvore é considerada como um grafo minimamente conectado que deve estar conectado e livre de loops.
