Contente

• Gráfico de comparação
• Definição de Árvore
• Propriedades da árvore:
• Definição de Gráfico
• Propriedades de um gráfico:
• Conclusão

Árvore e gráfico se enquadram na categoria de estrutura de dados não linear, em que a árvore oferece uma maneira muito útil de representar um relacionamento entre os nós em uma estrutura hierárquica e o gráfico segue um modelo de rede. Árvore e gráfico são diferenciados pelo fato de que uma estrutura em árvore deve estar conectada e nunca pode ter loops enquanto no gráfico não existem essas restrições.

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 uma sequência entre os elementos como existe em uma estrutura de dados linear.

1. 1. Gráfico de comparação
   2. Definição
   3. Principais diferenças
   4. Conclusão

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	Possui exatamente um nó raiz.	O gráfico não possui um nó raiz.
rotações	Não são permitidos loops.	O gráfico pode ter loops.
Complexidade	Menos complexo	Mais complexo comparativamente
Técnicas transversais	Pré-encomenda, Encomenda e Pós-encomenda.	Pesquisa de amplitude e 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 os itens de dados em ordem classificada. É 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 aresta em uma árvore resulta na formação do loop ou circuito.

Existem vários tipos de árvores, como árvore binária, árvore de pesquisa binária, árvore AVL, árvore binária encadeada, árvore B, etc. Compactação de dados, armazenamento de arquivos, manipulação da expressão aritmética e árvores de jogo são algumas das aplicações da árvore. estrutura de dados.

Propriedades da árvore:

• Há um nó designado na parte superior da árvore, conhecido como raiz da árvore.
• Os itens de dados restantes são divididos em subconjuntos separados, chamados de 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 possui n-1 arestas.

Existem vários termos associados a árvores, como nó terminal, aresta, nível, grau, profundidade, floresta, etc. Entre esses termos, alguns deles descritos abaixo.

• Beira - Uma linha que conecta dois nós.
• Nível - Uma árvore é particionada em níveis de modo que o nó raiz esteja no nível 0. Então, seus filhos imediatos estão no nível 1 e seus filhos imediatos 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 o terminal e o nó raiz, são conhecidos como nós não terminais.

Definição de Gráfico

UMA gráfico também é uma estrutura de dados não linear matemática 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 direcionada, não direcionada, conectada, não conectada, simples e multigráficos. Rede de computadores, sistema de transporte, gráfico de rede social, circuitos elétricos e planejamento de projetos são algumas das aplicações da estrutura de dados de gráficos. Também é empregado na técnica de gerenciamento denominada como PERT (avaliação do programa e técnica de revisão) e CPM (método do caminho crítico) no qual 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 aresta pode ser bidirecionada ou direcionada.
• Uma aresta 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 desses 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 sequência adjacente de vértices.
• Ciclo - É um caminho onde o primeiro e o último vértices são os mesmos.
• Grau - É um número de arestas incidentes em um vértice.
• Gráfico conectado - Se existe um caminho de um vértice aleatório para qualquer outro vértice, esse gráfico é conhecido como gráfico conectado.

1. Em uma árvore, existe apenas um caminho entre dois vértices, enquanto um gráfico pode ter caminhos unidirecionais e bidirecionais entre os nós.
2. Na árvore, existe exatamente um nó raiz e cada filho pode ter apenas um pai. Em contrapartida, em um gráfico, não há conceito do nó raiz.
3. Uma árvore não pode ter loops e auto-loops, enquanto o gráfico pode ter loops e auto-loops.
4. Os gráficos são mais complicados, pois podem ter loops e auto-loops. Por outro lado, as árvores são simples em comparação com o gráfico.
5. A árvore é percorrida usando técnicas de pré-ordem, ordem e pós-ordem. Por outro lado, para travessia de gráfico, usamos BFS (Largura da Primeira Pesquisa) e DFS (Profundidade da Primeira Pesquisa).
6. 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.
7. Uma árvore possui uma estrutura hierárquica, enquanto o gráfico possui um modelo de rede.

Conclusão

Gráfico e árvore são a estrutura de dados não linear que é usada para resolver vários problemas complexos. Um gráfico é um grupo de vértices e arestas em que uma aresta conecta um par de vértices, enquanto uma árvore é considerada um gráfico minimamente conectado, que deve ser conectado e livre de loops.