Was ist der Unterschied zwischen der Datenstruktur Tree und Graph?

Was ist akademisch gesehen der wesentliche Unterschied zwischen der Datenstruktur Tree und Graph? Und wie wäre es mit der baumbasierten Suche und der grafischen Suche?

Ein Baum ist nur eine eingeschränkte Form eines Diagramms.

Bäume haben eine Richtung (Eltern-Kind-Beziehungen) und enthalten keine Zyklen. Sie passen in die Kategorie der gerichteten azyklischen Graphen (oder einer DAG). Bäume sind also DAGs mit der Einschränkung, dass ein Kind nur einen Elternteil haben kann.

Wichtig ist, dass Bäume keine rekursive Datenstruktur sind. Sie können aufgrund der oben genannten Einschränkungen nicht als rekursive Datenstruktur implementiert werden. Es kann aber auch jede DAG-Implementierung verwendet werden, die im Allgemeinen nicht rekursiv ist. Meine bevorzugte Tree-Implementierung ist eine zentralisierte Kartendarstellung und nicht rekursiv.

Diagramme werden im Allgemeinen zuerst in der Breite oder zuerst in der Tiefe durchsucht. Gleiches gilt für Tree.

Anstatt es zu erklären, zeige ich es lieber in Bildern.

Ein Baum in Echtzeit

Ein Diagramm im realen Gebrauch

Ja, eine Karte kann als Diagrammdatenstruktur dargestellt werden.

Sie so zu sehen, macht das Leben leichter. Bäume werden an Stellen verwendet, an denen wir wissen, dass jeder Knoten nur ein übergeordnetes Element hat. Diagramme können jedoch mehrere Vorgänger haben (der übergeordnete Begriff wird im Allgemeinen nicht für Diagramme verwendet).

In der realen Welt können Sie fast alles mithilfe von Diagrammen darstellen. Ich habe zum Beispiel eine Karte verwendet. Wenn Sie jede Stadt als Knoten betrachten, kann sie von mehreren Punkten aus erreicht werden. Die Punkte, die zu diesem Knoten führen, werden als Vorgänger bezeichnet, und die Punkte, zu denen dieser Knoten führt, werden als Nachfolger bezeichnet.

Der elektrische Schaltplan, der Plan eines Hauses, eines Computernetzwerks oder eines Flusssystems sind nur einige weitere Beispiele für Diagramme. Viele Beispiele aus der Praxis können als Diagramme betrachtet werden.

Technisches Diagramm könnte so sein

Baum :

Grafik:

Stellen Sie sicher, dass Sie auf die folgenden Links verweisen. Diese beantworten fast alle Ihre Fragen zu Bäumen und Grafiken.

Verweise :

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

Die anderen Antworten sind nützlich, aber es fehlen die Eigenschaften der einzelnen:

Graph

^{Ungerichtete Grafik, Bildquelle: Wikipedia}

^{Gerichtete Grafik, Bildquelle: Wikipedia}

• Besteht aus einer Reihe von Eckpunkten (oder Knoten) und einer Reihe von Kanten, die einige oder alle verbinden
• Jede Kante kann zwei beliebige Scheitelpunkte verbinden, die noch nicht durch eine identische Kante verbunden sind (in derselben Richtung, im Fall eines gerichteten Graphen).
• Muss nicht verbunden sein (die Kanten müssen nicht alle Scheitelpunkte miteinander verbinden): Ein einzelnes Diagramm kann aus einigen getrennten Scheitelpunktsätzen bestehen

• Könnte gerichtet oder ungerichtet sein (was für alle Kanten in der Grafik gelten würde)
  Gemäß Wikipedia :

  Wenn die Eckpunkte beispielsweise Personen auf einer Party darstellen und zwischen zwei Personen ein Rand besteht, wenn sie sich die Hand geben, ist dieses Diagramm ungerichtet, da jede Person A einer Person B nur dann die Hand geben kann, wenn B auch A die Hand schüttelt. Wenn im Gegensatz dazu eine Kante von einer Person A zu einer Person B A bewundert, die B bewundert, dann ist dieser Graph gerichtet, weil Bewunderung nicht notwendigerweise erwidert wird.

Baum

^{Bildquelle: Wikipedia}

• Eine Art Grafik
• Scheitelpunkte werden häufiger als "Knoten" bezeichnet.
• Kanten sind gerichtet und repräsentieren eine Beziehung "ist Kind von" (oder "ist Eltern von")
• Jeder Knoten (außer dem Wurzelknoten) hat genau einen Elternteil (und null oder mehr Kinder).
• Hat genau einen "Wurzel" -Knoten (wenn der Baum mindestens einen Knoten hat), der ein Knoten ohne übergeordnetes Element ist
• Muss verbunden sein
• Ist azyklisch, was bedeutet, dass es keine Zyklen hat : "Ein Zyklus ist ein Pfad [AKA-Sequenz] von Kanten und Scheitelpunkten, auf dem ein Scheitelpunkt von sich aus erreichbar ist."

Es gibt einige Überlappungen in den obigen Eigenschaften. Insbesondere werden die letzten beiden Eigenschaften durch den Rest der Eigenschaften impliziert. Trotzdem sind alle erwähnenswert.

Im Baum hat jeder Knoten (außer dem Wurzelknoten) genau einen Vorgängerknoten und einen oder zwei Nachfolgeknoten. Es kann mithilfe von In-Order-, Pre-Order-, Post-Order- und Breadth First-Durchquerungen durchlaufen werden. Baum ist eine spezielle Art von Grafik, die keinen Zyklus hat und daher als DAG (Directed Acyclic Graph) bezeichnet wird. Baum ist ein hierarchisches Modell.

In der Grafik hat jeder Knoten einen oder mehrere Vorgängerknoten und Nachfolgeknoten. Der Graph wird mit den Algorithmen Depth First Search (DFS) und Breadth First Search (BFS) durchlaufen. Der Graph hat einen Zyklus, ist also komplexer als der Baum. Graph ist ein Netzwerkmodell. Es gibt zwei Arten von Diagrammen: gerichtete Diagramme und ungerichtete Diagramme.

Bäume sind offensichtlich: Sie sind rekursive Datenstrukturen, die aus Knoten mit untergeordneten Knoten bestehen.

Map (auch bekannt als Dictionary) sind Schlüssel / Wert-Paare. Geben Sie einer Karte einen Schlüssel und sie gibt den zugehörigen Wert zurück.

Karten können mithilfe von Bäumen implementiert werden. Ich hoffe, Sie finden das nicht verwirrend.

UPDATE: Das Verwechseln von "Grafik" mit "Karte" ist sehr verwirrend.

Diagramme sind komplexer als Bäume. Bäume implizieren rekursive Eltern-Kind-Beziehungen. Es gibt natürliche Möglichkeiten, einen Baum zu durchqueren: Tiefe zuerst, Breite zuerst, Ebenenreihenfolge usw.

Diagramme können unidirektionale oder bidirektionale Pfade zwischen Knoten haben, zyklisch oder azyklisch sein usw. Ich würde Diagramme als komplexer betrachten.

Ich denke, eine flüchtige Suche in einem anständigen Datenstrukturtext (z. B. "Algorithms Design Manual") würde mehr und bessere Informationen liefern als eine beliebige Anzahl von SO-Antworten. Ich würde empfehlen, dass Sie nicht den passiven Weg gehen und selbst recherchieren.

Der Baum ist eine spezielle Form eines Graphen, dh ein minimal verbundener Graph mit nur einem Pfad zwischen zwei beliebigen Eckpunkten.

Im Diagramm kann es mehr als einen Pfad geben, dh das Diagramm kann unidirektionale oder bidirektionale Pfade (Kanten) zwischen Knoten aufweisen

Sie können auch weitere Details sehen: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

In der Mathematik ist ein Graph eine Darstellung einer Menge von Objekten, bei denen einige Paare der Objekte durch Verknüpfungen verbunden sind. Die miteinander verbundenen Objekte werden durch mathematische Abstraktionen dargestellt, die als Scheitelpunkte bezeichnet werden, und die Verknüpfungen, die einige Scheitelpunktpaare verbinden, werden als Kanten bezeichnet. [1] In der Regel wird ein Diagramm in schematischer Form als Satz von Punkten für die Eckpunkte dargestellt, die durch Linien oder Kurven für die Kanten verbunden sind. Graphen sind eines der Untersuchungsobjekte in der diskreten Mathematik.

Ein Wurzelknoten im Baum und nur ein Elternteil für ein Kind. Es gibt jedoch kein Konzept für den Wurzelknoten. Ein weiterer Unterschied besteht darin, dass der Baum ein hierarchisches Modell ist, der Graph jedoch ein Netzwerkmodell.

Ein Baum ist ein Digraph, so dass:

a) Wenn die Kantenrichtungen entfernt sind, ist es verbunden und azyklisch

1. Sie können entweder die Annahme entfernen, dass es azyklisch ist
2. Wenn es endlich ist, können Sie alternativ die Annahme entfernen, dass es verbunden ist

b) Jeder Scheitelpunkt bis auf einen, die Wurzel, hat Grad 1

c) Die Wurzel hat Grad 0

1. Wenn es nur endlich viele Knoten gibt, können Sie entweder die Annahme entfernen, dass die Wurzel Grad 0 hat, oder die Annahme, dass andere Knoten als die Wurzel Grad 1 haben

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