Qual é a diferença entre a estrutura de dados Árvore e Gráfico?

Academicamente falando, qual é a diferença essencial entre a estrutura de dados Árvore e Gráfico? E a pesquisa baseada em árvore e a pesquisa baseada em gráfico?

Uma árvore é apenas uma forma restrita de um gráfico.

As árvores têm direção (relações pai / filho) e não contêm ciclos. Eles se encaixam na categoria de Gráficos Acíclicos Dirigidos (ou um DAG). Portanto, as árvores são DAGs com a restrição de que um filho pode ter apenas um pai.

É importante ressaltar que as árvores não são uma estrutura de dados recursiva. Eles não podem ser implementados como uma estrutura de dados recursiva devido às restrições acima. Mas qualquer implementação do DAG, que geralmente não é recursiva, também pode ser usada. Minha implementação em árvore preferida é uma representação centralizada do mapa e não é recursiva.

Geralmente, os gráficos são pesquisados ​​em largura primeiro ou em profundidade primeiro. O mesmo se aplica à Árvore.

Em vez de explicar, prefiro mostrá-lo em fotos.

Uma árvore em tempo real

Um gráfico na vida real

Sim, um mapa pode ser visualizado como uma estrutura de dados gráficos.

Vê-los assim facilita a vida. As árvores são usadas em locais onde sabemos que cada nó tem apenas um pai. Mas os gráficos podem ter vários predecessores (o termo pai geralmente não é usado para gráficos).

No mundo real, você pode representar quase qualquer coisa usando gráficos. Eu usei um mapa, por exemplo. Se você considerar cada cidade como um nó, poderá ser alcançado a partir de vários pontos. Os pontos que levam a este nó são chamados predecessores e os pontos aos quais esse nó levará são chamados sucessores.

diagrama de circuito elétrico, o plano de uma casa, rede de computadores ou sistema fluvial são mais alguns exemplos de gráficos. Muitos exemplos do mundo real podem ser considerados como gráficos.

O diagrama técnico pode ser assim

Árvore:

Gráfico :

Certifique-se de consultar os links abaixo. Eles responderão quase todas as suas perguntas sobre árvores e gráficos.

Referências :

1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

3. Wikipedia

As outras respostas são úteis, mas faltam as propriedades de cada uma:

Gráfico

^{Gráfico não direcionado, fonte da imagem: Wikipedia}

^{Gráfico direcionado, fonte da imagem: Wikipedia}

• Consiste em um conjunto de vértices (ou nós) e um conjunto de arestas conectando alguns ou todos eles
• Qualquer aresta pode conectar dois vértices que ainda não estão conectados por uma aresta idêntica (na mesma direção, no caso de um gráfico direcionado)
• Não precisa estar conectado (as arestas não precisam conectar todos os vértices): um único gráfico pode consistir em alguns conjuntos desconectados de vértices

• Pode ser direcionado ou não direcionado (que se aplicaria a todas as arestas do gráfico)
  Conforme Wikipedia :

  Por exemplo, se os vértices representam pessoas em uma festa e existe uma margem entre duas pessoas se eles apertarem as mãos, esse gráfico não será direcionado porque qualquer pessoa A pode apertar as mãos de uma pessoa B apenas se B também apertar as mãos de A. Por outro lado, se qualquer margem de uma pessoa A para uma pessoa B corresponde a A que admira B, esse gráfico é direcionado, porque a admiração não é necessariamente recíproca.

Árvore

^{Fonte da imagem: Wikipedia}

• Um tipo de gráfico
• Vértices são mais comumente chamados "nós"
• As arestas são direcionadas e representam um relacionamento "é filho de" (ou "é pai de")
• Cada nó (exceto o nó raiz) possui exatamente um pai (e zero ou mais filhos)
• Possui exatamente um nó "raiz" (se a árvore tiver pelo menos um nó), que é um nó sem um pai
• Tem que estar conectado
• É acíclico, o que significa que não possui ciclos : "um ciclo é um caminho [sequência AKA] de arestas e vértices em que um vértice é alcançável por si mesmo"

Há alguma sobreposição nas propriedades acima. Especificamente, as duas últimas propriedades estão implícitas pelo restante das propriedades. Mas todos eles são dignos de nota, no entanto.

Na árvore, cada nó (exceto o nó raiz) possui exatamente um nó predecessor e um ou dois nós sucessores. Ele pode ser percorrido usando as travessias Em ordem, Pré-ordem, Pós-ordem e Primeira largura. A árvore é um tipo especial de gráfico que não possui ciclo, conhecido como DAG (Directed Acyclic Graph). Árvore é um modelo hierárquico.

No gráfico, cada nó possui um ou mais nós predecessores e nós sucessores. O gráfico é percorrido usando os algoritmos Depth First Search (DFS) e Breadth First Search (BFS). O gráfico tem ciclo, portanto é mais complexo que a árvore. O gráfico é um modelo de rede. Existem dois tipos de gráfico: gráficos direcionados e gráficos não direcionados.

As árvores são óbvias: são estruturas de dados recursivas que consistem em nós com filhos.

Mapa (também conhecido como dicionário) são pares de chave / valor. Dê uma chave ao mapa e ele retornará o valor associado.

Os mapas podem ser implementados usando árvores, espero que você não ache isso confuso.

ATUALIZAÇÃO: "Gráfico" confuso para "Mapa" é muito confuso.

Os gráficos são mais complexos que as árvores. As árvores implicam relações recursivas entre pais e filhos. Existem maneiras naturais de percorrer uma árvore: profundidade primeiro, largura primeiro, ordem de nível, etc.

Os gráficos podem ter caminhos unidirecionais ou bidirecionais entre os nós, sejam cíclicos ou acíclicos, etc. Eu consideraria os gráficos mais complexos.

Eu acho que uma pesquisa superficial em qualquer texto de estruturas de dados decente (por exemplo, "Manual de Design de Algoritmos") daria mais e melhores informações do que qualquer número de respostas do SO. Eu recomendo que você não siga a rota passiva e comece a fazer algumas pesquisas por si mesmo.

A árvore é uma forma especial de gráfico, ou seja, gráfico minimamente conectado e com apenas um caminho entre dois vértices.

No gráfico , pode haver mais de um caminho, ou seja, o gráfico pode ter caminhos unidirecionais ou bidirecionais (arestas) entre os nós

Além disso, você pode ver mais detalhes: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

Em matemática, um gráfico é uma representação de um conjunto de objetos em que alguns pares de objetos são conectados por links. Os objetos interconectados são representados por abstrações matemáticas chamadas vértices, e os links que conectam alguns pares de vértices são denominados arestas. [1] Normalmente, um gráfico é representado na forma de diagrama como um conjunto de pontos para os vértices, unidos por linhas ou curvas para as arestas. Os gráficos são um dos objetos de estudo da matemática discreta.

um nó raiz na árvore e apenas um pai para um filho. No entanto, não há conceito de nó raiz. Outra diferença é que a árvore é um modelo hierárquico, mas o gráfico é um modelo de rede.

Uma árvore é um dígrafo que:

a) com as direções da borda removidas, é conectada e acíclica

1. Você pode remover a suposição de que é acíclico
2. Se for finito, você pode remover alternativamente a suposição de que esteja conectado

b) todo vértice, com exceção de um, a raiz, tem 1

c) a raiz tem 0 graus

1. Se houver apenas muitos nós finitamente, você poderá remover a suposição de que a raiz tenha 0 indegree ou a suposição de que os nós que não sejam a raiz tenham grau 1

Referência: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

A árvore é basicamente um gráfico não direcionado que não contém ciclo, então podemos dizer que a árvore é uma forma mais restrita de gráfico. No entanto, árvore e gráfico têm aplicação diferente para implementar vários algoritmos na programação. Por exemplo, o gráfico pode ser usado para o roteiro do modelo e a árvore para implementar qualquer estrutura de dados hierárquica.