Inhalt

• Vergleichstabelle
• Definition von Baum
• Eigenschaften des Baumes:
• Definition von Graph
• Eigenschaften eines Graphen:
• Fazit

Baum und Graph fallen unter die Kategorie der nichtlinearen Datenstruktur, wobei Tree eine sehr nützliche Möglichkeit bietet, eine Beziehung zwischen den Knoten in einer hierarchischen Struktur darzustellen, und Graph folgt einem Netzwerkmodell. Baum und Graph unterscheiden sich dadurch, dass eine Baumstruktur verbunden sein muss und niemals Schleifen haben kann, während es im Graph keine derartigen Einschränkungen gibt.

Eine nichtlineare Datenstruktur besteht aus einer Sammlung von Elementen, die auf einer Ebene verteilt sind, was bedeutet, dass zwischen den Elementen keine solche Reihenfolge besteht, wie sie in einer linearen Datenstruktur vorhanden ist.

1. 1. Vergleichstabelle
   2. Definition
   3. Hauptunterschiede
   4. Fazit

Vergleichstabelle

Vergleichsbasis	Baum	Graph
Pfad	Nur einer zwischen zwei Eckpunkten.	Es ist mehr als ein Pfad zulässig.
Wurzelknoten	Es hat genau einen Wurzelknoten.	Graph hat keinen Wurzelknoten.
Schleifen	Es sind keine Schleifen erlaubt.	Graph kann Schleifen haben.
Komplexität	Weniger komplex	Vergleichsweise komplexer
Traversaltechniken	Vorbestellung, Bestellung und Nachbestellung.	Breitensuche und Tiefensuche.
Anzahl der Kanten	n-1 (wobei n die Anzahl der Knoten ist)	Nicht definiert
Modelltyp	Hierarchisch	Netzwerk

Definition von Baum

EIN Baum ist eine endliche Sammlung von Datenelementen, die üblicherweise als Knoten bezeichnet werden. Wie oben erwähnt, ist ein Baum eine nichtlineare Datenstruktur, die Datenelemente in sortierter Reihenfolge anordnet. Es wird verwendet, um eine hierarchische Struktur zwischen den verschiedenen Datenelementen darzustellen und die Daten in Zweigen zu organisieren, die die Informationen in Beziehung setzen. Das Hinzufügen einer neuen Kante in einem Baum führt zur Bildung der Schleife oder des Stromkreises.

Es gibt verschiedene Arten von Bäumen, wie z. B. einen Binärbaum, einen binären Suchbaum, einen AVL-Baum, einen Binärbaum mit Thread, einen B-Baum usw. Datenkomprimierung, Dateispeicherung, Manipulation des arithmetischen Ausdrucks und Spielbäume sind einige der Anwendungen von Bäumen Datenstruktur.

Eigenschaften des Baumes:

• Am oberen Ende des Baums befindet sich ein Knoten, der als Wurzel des Baums bezeichnet wird.
• Die übrigen Datenelemente sind in disjunkte Teilmengen unterteilt, die als Teilbaum bezeichnet werden.
• Der Baum ist in der Höhe nach unten erweitert.
• Ein Baum muss verbunden sein, dh es muss ein Pfad von einer Wurzel zu allen anderen Knoten vorhanden sein.
• Es enthält keine Schleifen.
• Ein Baum hat n-1 Kanten.

Es gibt verschiedene Begriffe, die mit Bäumen verbunden sind, wie Endknoten, Rand, Ebene, Grad, Tiefe, Wald usw. Unter diesen Begriffen sind einige von ihnen nachstehend beschrieben.

• Kante - Eine Linie, die zwei Knoten verbindet.
• Niveau - Ein Baum wird in Ebenen unterteilt, sodass sich der Wurzelknoten auf Ebene 0 befindet. Dann befinden sich seine unmittelbaren untergeordneten Elemente auf Ebene 1 und seine unmittelbaren untergeordneten Elemente auf Ebene 2 usw. bis zum Terminal- oder Blattknoten.
• Grad - Dies ist die Anzahl der Teilbäume eines Knotens in einem bestimmten Baum.
• Tiefe - Es ist die maximale Ebene eines Knotens in einem bestimmten Baum und auch bekannt als Höhe.
• Terminalknoten - Der Knoten der höchsten Ebene ist der Endknoten, während andere Knoten mit Ausnahme des Endknotens und des Wurzelknotens als Nicht-Endknoten bekannt sind.

Definition von Graph

EIN Graph ist auch eine mathematische nichtlineare Datenstruktur, die verschiedene Arten physikalischer Strukturen darstellen kann. Es besteht aus einer Gruppe von Eckpunkten (oder Knoten) und einer Reihe von Kanten, die die beiden Eckpunkte verbinden. Scheitelpunkte im Diagramm werden als Punkt oder Kreise dargestellt und Kanten als Bögen oder Liniensegmente. Eine Kante wird durch E (v, w) dargestellt, wobei v und w die Eckpunktpaare sind. Durch das Entfernen einer Kante aus einem Schaltkreis oder einem verbundenen Graphen wird ein Subgraph erstellt, der ein Baum ist.

Die Diagramme werden in verschiedene Kategorien unterteilt, z. B. gerichtet, nicht gerichtet, verbunden, nicht verbunden, einfach und mehrere Diagramme. Computernetzwerk, Transportsystem, soziales Netzwerkdiagramm, elektrische Schaltkreise und Projektplanung sind einige der Anwendungen der Diagrammdatenstruktur. Es wird auch in der Managementtechnik eingesetzt, die als bezeichnet wird PERT (Programmbewertung und Überprüfungstechnik) und CPM (Critical Path Method), bei der die Graphenstruktur analysiert wird.

Eigenschaften eines Graphen:

• Ein Scheitelpunkt in einem Diagramm kann mithilfe von Kanten mit einer beliebigen Anzahl anderer Scheitelpunkte verbunden werden.
• Eine Kante kann bidirektional oder gerichtet sein.
• Eine Kante kann gewichtet werden.

Im Diagramm werden auch verschiedene Begriffe verwendet, z. B. benachbarte Scheitelpunkte, Pfad, Zyklus, Grad, verbundenes Diagramm, vollständiges Diagramm, gewichtetes Diagramm usw. Wir wollen einige dieser Begriffe verstehen.

• Benachbarte Eckpunkte - Ein Scheitelpunkt a grenzt an den Scheitelpunkt b, wenn es eine Kante (a, b) oder (b, a) gibt.
• Pfad - Ein Pfad von einem zufälligen Eckpunkt w ist eine benachbarte Folge von Eckpunkten.
• Zyklus - Es ist ein Pfad, bei dem der erste und der letzte Scheitelpunkt identisch sind.
• Grad - Es ist eine Anzahl von Kanten, die auf einen Scheitelpunkt fallen.
• Verbundener Graph - Wenn es einen Pfad von einem zufälligen Scheitelpunkt zu einem anderen Scheitelpunkt gibt, wird dieser Graph als verbundener Graph bezeichnet.

1. In einem Baum existiert nur ein Pfad zwischen zwei Eckpunkten, wohingegen ein Graph unidirektionale und bidirektionale Pfade zwischen den Knoten haben kann.
2. In der Struktur gibt es genau einen Stammknoten, und jedes Kind kann nur ein Elternteil haben. Im Gegensatz dazu gibt es in einem Diagramm kein Konzept für den Wurzelknoten.
3. Ein Baum kann keine Schleifen und Selbstschleifen haben, während ein Graph Schleifen und Selbstschleifen haben kann.
4. Diagramme sind komplizierter, da es Schleifen und Selbstschleifen geben kann. Im Gegensatz dazu sind Bäume im Vergleich zur Grafik einfach.
5. Der Baum wird unter Verwendung von Vorbestellungs-, In-Order- und Post-Order-Techniken durchlaufen. Zum Durchlaufen von Graphen verwenden wir BFS (Breadth First Search) und DFS (Depth First Search).
6. Ein Baum kann n-1 Kanten haben. Im Gegensatz dazu gibt es im Diagramm keine vordefinierte Anzahl von Kanten, und dies hängt vom Diagramm ab.
7. Ein Baum hat eine hierarchische Struktur, während ein Graph ein Netzwerkmodell hat.

Fazit

Graph und Tree sind die nichtlineare Datenstruktur, die zur Lösung verschiedener komplexer Probleme verwendet wird. Ein Graph ist eine Gruppe von Eckpunkten und Kanten, wobei eine Kante ein Paar von Eckpunkten verbindet, während ein Baum als minimal verbundener Graph betrachtet wird, der verbunden und frei von Schleifen sein muss.