Quelle est la différence entre la structure de données Tree et Graph?

Sur le plan académique, quelle est la différence essentielle entre la structure de données Tree et Graph? Et que diriez-vous de la recherche basée sur l'arbre et de la recherche basée sur un graphique?

Un arbre n'est qu'une forme restreinte d'un graphique.

Les arbres ont une direction (relations parent / enfant) et ne contiennent pas de cycles. Ils s'inscrivent dans la catégorie des graphes acycliques dirigés (ou un DAG). Les arbres sont donc des DAG avec la restriction qu'un enfant ne peut avoir qu'un seul parent.

Une chose qu'il est important de souligner, les arbres ne sont pas une structure de données récursive. Ils ne peuvent pas être implémentés en tant que structure de données récursive en raison des restrictions ci-dessus. Mais toute implémentation de DAG, qui n'est généralement pas récursive, peut également être utilisée. Mon implémentation d'arbre préférée est une représentation cartographique centralisée et n'est pas récursive.

Les graphiques sont généralement recherchés d'abord en largeur ou en profondeur. La même chose s'applique à Tree.

Au lieu d'expliquer, je préfère le montrer en images.

Un arbre en temps réel

Un graphique en utilisation réelle

Oui, une carte peut être visualisée sous la forme d'une structure de données graphique.

Les voir ainsi rend la vie plus facile. Les arbres sont utilisés aux endroits où nous savons que chaque nœud n'a qu'un seul parent. Mais les graphiques peuvent avoir plusieurs prédécesseurs (le terme parent n'est généralement pas utilisé pour les graphiques).

Dans le monde réel, vous pouvez représenter presque tout à l'aide de graphiques. J'ai utilisé une carte, par exemple. Si vous considérez chaque ville comme un nœud, elle peut être atteinte à partir de plusieurs points. Les points qui mènent à ce nœud sont appelés prédécesseurs et les points auxquels ce nœud mènera sont appelés successeurs.

le schéma électrique, le plan d'une maison, d'un réseau informatique ou d'un réseau fluvial ne sont que quelques exemples de graphiques supplémentaires. De nombreux exemples du monde réel peuvent être considérés comme des graphiques.

Le schéma technique pourrait être comme ça

Arbre:

Graphique :

Assurez-vous de vous référer aux liens ci-dessous. Ceux-ci répondront à presque toutes vos questions sur les arbres et les graphiques.

Références :

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. Wikipédia

Les autres réponses sont utiles, mais il leur manque les propriétés de chacune:

Graphique

^{Graphique non dirigé, source de l'image: Wikipedia}

^{Graphique dirigé, source de l'image: Wikipedia}

• Se compose d'un ensemble de sommets (ou nœuds) et d'un ensemble d'arêtes reliant certains d'entre eux ou tous
• Toute arête peut relier deux sommets quelconques qui ne sont pas déjà connectés par une arête identique (dans la même direction, dans le cas d'un graphe orienté)
• N'a pas besoin d'être connecté (les arêtes n'ont pas à connecter tous les sommets ensemble): un seul graphe peut être constitué de quelques ensembles de sommets déconnectés

• Peut être dirigé ou non (ce qui s'appliquerait à toutes les arêtes du graphique)
  Selon Wikipedia :

  Par exemple, si les sommets représentent des personnes lors d'une fête et qu'il y a un bord entre deux personnes si elles se serrent la main, alors ce graphique n'est pas orienté car toute personne A ne peut serrer la main d'une personne B que si B serre également la main de A. En revanche, si un avantage d'une personne A à une personne B correspond à A admirant B, alors ce graphique est dirigé, car l'admiration n'est pas nécessairement réciproque.

Arbre

^{Source de l'image: Wikipedia}

• Un type de graphique
• Les sommets sont plus communément appelés "nœuds"
• Les bords sont orientés et représentent une relation «est l'enfant de» (ou «est le parent de»)
• Chaque nœud (sauf le nœud racine) a exactement un parent (et zéro ou plusieurs enfants)
• A exactement un nœud "racine" (si l'arbre a au moins un nœud), qui est un nœud sans parent
• Doit être connecté
• Est acyclique, ce qui signifie qu'il n'a pas de cycles : "un cycle est un chemin [séquence AKA] d'arêtes et de sommets dans lequel un sommet est accessible à partir de lui-même"

Il y a un certain chevauchement dans les propriétés ci-dessus. Plus précisément, les deux dernières propriétés sont impliquées par le reste des propriétés. Mais tous valent la peine d'être notés.

Dans l'arborescence, chaque nœud (à l'exception du nœud racine) a exactement un nœud prédécesseur et un ou deux nœuds successeurs. Il peut être parcouru à l'aide des traversées Dans l'ordre, Pré-commande, Post-commande et Largeur d'abord. L'arbre est un type spécial de graphe qui n'a pas de cycle, donc appelé DAG (Directed Acyclic Graph). L'arbre est un modèle hiérarchique.

Dans le graphique, chaque nœud a un ou plusieurs nœuds prédécesseurs et nœuds successeurs. Le graphique est parcouru à l'aide des algorithmes Depth First Search (DFS) et Breadth First Search (BFS). Le graphique a un cycle, il est donc plus complexe que l'arbre. Graph est un modèle de réseau. Il existe deux types de graphes: les graphes orientés et les graphes non orientés.

Les arbres sont évidents: ce sont des structures de données récursives constituées de nœuds avec des enfants.

La carte (aka dictionnaire) est une paire clé / valeur. Donnez une clé à une carte et elle renverra la valeur associée.

Les cartes peuvent être implémentées à l'aide d'arbres, j'espère que vous ne trouvez pas cela déroutant.

MISE À JOUR: "graphe" confus pour "carte" est très déroutant.

Les graphiques sont plus complexes que les arbres. Les arbres impliquent des relations parent / enfant récursives. Il existe des moyens naturels de parcourir un arbre: profondeur d'abord, largeur d'abord, ordre des niveaux, etc.

Les graphes peuvent avoir des chemins unidirectionnels ou bidirectionnels entre les nœuds, être cycliques ou acycliques, etc. Je considérerais les graphes comme plus complexes.

Je pense qu'une recherche superficielle dans n'importe quel texte de structures de données décentes (par exemple "Algorithms Design Manual") donnerait des informations plus nombreuses et meilleures que n'importe quel nombre de réponses SO. Je vous recommande de ne pas emprunter la voie passive et de commencer à faire des recherches par vous-même.

L'arbre est une forme spéciale de graphique, c'est-à-dire un graphe minimalement connecté et n'ayant qu'un seul chemin entre deux sommets.

Dans le graphe, il peut y avoir plus d'un chemin, c'est-à-dire que le graphe peut avoir des chemins unidirectionnels ou bidirectionnels (arêtes) entre les nœuds

Vous pouvez également voir plus de détails: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

En mathématiques, un graphe est une représentation d'un ensemble d'objets où certaines paires d'objets sont reliées par des liens. Les objets interconnectés sont représentés par des abstractions mathématiques appelées sommets, et les liens qui relient certaines paires de sommets sont appelés arêtes. [1] En règle générale, un graphique est représenté sous forme schématique sous la forme d'un ensemble de points pour les sommets, joints par des lignes ou des courbes pour les arêtes. Les graphiques sont l'un des objets d'étude en mathématiques discrètes.

un nœud racine dans l'arborescence et un seul parent pour un enfant. Cependant, il n'y a pas de concept de nœud racine. Une autre différence est que l'arbre est un modèle hiérarchique, mais le graphique est un modèle de réseau.

Un arbre est un digraphe tel que:

a) avec les directions de bord supprimées, il est connecté et acyclique

1. Vous pouvez supprimer soit l'hypothèse qu'il est acyclique
2. S'il est fini, vous pouvez également supprimer l'hypothèse qu'il est connecté

b) chaque sommet sauf un, la racine, a indegree 1

c) la racine a indegree 0

1. S'il n'y a qu'un nombre fini de nœuds, vous pouvez supprimer soit l'hypothèse selon laquelle la racine a un degré 0 ou l'hypothèse que les nœuds autres que la racine ont le degré 1

Référence: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

L'arbre est essentiellement un graphe non orienté qui ne contient pas de cycle, nous pouvons donc dire que l'arbre est une forme de graphe plus restreinte. Cependant, l'arbre et le graphique ont des applications différentes pour implémenter divers algorithmes en programmation. Par exemple, le graphique peut être utilisé pour le modèle de feuille de route et l'arbre peut être utilisé pour mettre en œuvre toute structure de données hiérarchique.