Datenstrukturen sind eine Möglichkeit, Daten so zu organisieren, dass je nach Situation effizienter auf sie zugegriffen werden kann. Datenstrukturen sind die Grundlagen jeder Programmiersprache, auf der ein Programm basiert. Im Vergleich zu anderen Programmiersprachen hilft Python dabei, die Grundlagen dieser Datenstrukturen auf einfachere Weise zu erlernen.
In diesem Artikel besprechen wir die Datenstrukturen in der Programmiersprache Python und wie sie mit einigen spezifischen integrierten Datenstrukturen wie Listentupeln, Wörterbüchern usw. sowie einigen erweiterten Datenstrukturen wie Bäumen, Diagrammen usw. zusammenhängen.
Listen
Python-Listen sind genau wie die in anderen Sprachen deklarierten Arrays eine geordnete Sammlung von Daten. Es ist sehr flexibel, da die Elemente in einer Liste nicht vom gleichen Typ sein müssen.
Die Implementierung von Python List ähnelt Vectors in C++ oder ArrayList in JAVA. Der kostspielige Vorgang besteht darin, das Element am Anfang der Liste einzufügen oder zu löschen, da alle Elemente verschoben werden müssen. Auch das Einfügen und Löschen am Ende der Liste kann kostspielig werden, wenn der vorab zugewiesene Speicher voll wird.
Wir können eine Liste in Python erstellen, wie unten gezeigt.
Beispiel: Python-Liste erstellen
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Ausgabe
[1, 2, 3, 'GFG', 2.3]>
Auf Listenelemente kann über den zugewiesenen Index zugegriffen werden. In Python ist der Startindex der Liste 0 und der Endindex ist (wenn N Elemente vorhanden sind) N-1.
Beispiel: Python-Listenoperationen
Python3
# Creating a List with> # the use of multiple values> List> => [>'Geeks'>,>'For'>,>'Geeks'>]> print>(>'
List containing multiple values: '>)> print>(>List>)> # Creating a Multi-Dimensional List> # (By Nesting a list inside a List)> List2>=> [[>'Geeks'>,>'For'>], [>'Geeks'>]]> print>(>'
Multi-Dimensional List: '>)> print>(List2)> # accessing a element from the> # list using index number> print>(>'Accessing element from the list'>)> print>(>List>[>0>])> print>(>List>[>2>])> # accessing a element using> # negative indexing> print>(>'Accessing element using negative indexing'>)> > # print the last element of list> print>(>List>[>->1>])> > # print the third last element of list> print>(>List>[>->3>])> |
>
Java-String in JSON
>Ausgabe
List containing multiple values: ['Geeks', 'For', 'Geeks'] Multi-Dimensional List: [['Geeks', 'For'], ['Geeks']] Accessing element from the list Geeks Geeks Accessing element using negative indexing Geeks Geeks>
Wörterbuch
Python-Wörterbuch ist wie Hash-Tabellen in jeder anderen Sprache mit der zeitlichen Komplexität von O(1). Es handelt sich um eine ungeordnete Sammlung von Datenwerten, die zum Speichern von Datenwerten wie eine Karte verwendet wird. Im Gegensatz zu anderen Datentypen, die nur einen einzelnen Wert als Element enthalten, enthält Dictionary das Schlüssel-Wert-Paar. Zur Optimierung wird im Wörterbuch ein Schlüsselwert bereitgestellt.
Die Indizierung des Python-Wörterbuchs erfolgt mithilfe von Schlüsseln. Diese sind von jedem hashbaren Typ, d. h. ein Objekt, das sich niemals ändern kann, wie Zeichenfolgen, Zahlen, Tupel usw. Wir können ein Wörterbuch erstellen, indem wir geschweifte Klammern ({}) oder verwenden Wörterbuchverständnis .
Beispiel: Python-Wörterbuchoperationen
Python3
# Creating a Dictionary> Dict> => {>'Name'>:>'Geeks'>,>1>: [>1>,>2>,>3>,>4>]}> print>(>'Creating Dictionary: '>)> print>(>Dict>)> # accessing a element using key> print>(>'Accessing a element using key:'>)> print>(>Dict>[>'Name'>])> # accessing a element using get()> # method> print>(>'Accessing a element using get:'>)> print>(>Dict>.get(>1>))> # creation using Dictionary comprehension> myDict>=> {x: x>*>*>2> for> x>in> [>1>,>2>,>3>,>4>,>5>]}> print>(myDict)> |
>
>Ausgabe
Creating Dictionary: {'Name': 'Geeks', 1: [1, 2, 3, 4]} Accessing a element using key: Geeks Accessing a element using get: [1, 2, 3, 4] {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}> Tupel
Python-Tupel ist eine Sammlung von Python-Objekten, ähnlich einer Liste, aber Tupel sind von Natur aus unveränderlich, d. h. die Elemente im Tupel können nach der Erstellung nicht hinzugefügt oder entfernt werden. Genau wie eine Liste kann auch ein Tupel Elemente unterschiedlichen Typs enthalten.
In Python werden Tupel erstellt, indem eine durch „Komma“ getrennte Folge von Werten mit oder ohne Verwendung von Klammern zum Gruppieren der Datenfolge platziert wird.
Notiz: Tupel können auch mit einem einzelnen Element erstellt werden, allerdings ist das etwas knifflig. Es reicht nicht aus, ein Element in den Klammern zu haben, es muss ein abschließendes „Komma“ stehen, um daraus ein Tupel zu machen.
Beispiel: Python-Tupeloperationen
Python3
# Creating a Tuple with> # the use of Strings> Tuple> => (>'Geeks'>,>'For'>)> print>(>'
Tuple with the use of String: '>)> print>(>Tuple>)> > # Creating a Tuple with> # the use of list> list1>=> [>1>,>2>,>4>,>5>,>6>]> print>(>'
Tuple using List: '>)> Tuple> => tuple>(list1)> # Accessing element using indexing> print>(>'First element of tuple'>)> print>(>Tuple>[>0>])> # Accessing element from last> # negative indexing> print>(>'
Last element of tuple'>)> print>(>Tuple>[>->1>])> > print>(>'
Third last element of tuple'>)> print>(>Tuple>[>->3>])> |
>
>Ausgabe
Tuple with the use of String: ('Geeks', 'For') Tuple using List: First element of tuple 1 Last element of tuple 6 Third last element of tuple 4> Satz
Python-Set ist eine ungeordnete Sammlung von Daten, die veränderbar ist und keine doppelten Elemente zulässt. Sets dienen im Wesentlichen dazu, die Mitgliedschaft zu testen und doppelte Einträge zu eliminieren. Die dabei verwendete Datenstruktur ist Hashing, eine beliebte Technik zum Durchführen von Einfügungen, Löschungen und Durchläufen in O(1) im Durchschnitt.
Wenn an derselben Indexposition mehrere Werte vorhanden sind, wird der Wert an diese Indexposition angehängt, um eine verknüpfte Liste zu bilden. In werden CPython-Sets mithilfe eines Wörterbuchs mit Dummy-Variablen implementiert, wobei die Schlüsselelemente die Mitglieder sind, die mit größerer Optimierung der Zeitkomplexität festgelegt werden.
Set-Implementierung:
Sets mit zahlreichen Operationen auf einer einzelnen HashTable:
Beispiel: Python-Set-Operationen
Python3
# Creating a Set with> # a mixed type of values> # (Having numbers and strings)> Set> => set>([>1>,>2>,>'Geeks'>,>4>,>'For'>,>6>,>'Geeks'>])> print>(>'
Set with the use of Mixed Values'>)> print>(>Set>)> # Accessing element using> # for loop> print>(>'
Elements of set: '>)> for> i>in> Set>:> >print>(i, end>=>' '>)> print>()> # Checking the element> # using in keyword> print>(>'Geeks'> in> Set>)> |
>
>Ausgabe
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Gefrorene Sets
Eingefrorene Mengen in Python sind unveränderliche Objekte, die nur Methoden und Operatoren unterstützen, die ein Ergebnis erzeugen, ohne Auswirkungen auf die eingefrorene Menge oder Mengen, auf die sie angewendet werden. Während Elemente einer Menge jederzeit geändert werden können, bleiben Elemente der eingefrorenen Menge nach der Erstellung gleich.
Wenn keine Parameter übergeben werden, wird ein leeres Frozenset zurückgegeben.
Python3
# Same as {'a', 'b','c'}> normal_set>=> set>([>'a'>,>'b'>,>'c'>])> print>(>'Normal Set'>)> print>(normal_set)> # A frozen set> frozen_set>=> frozenset>([>'e'>,>'f'>,>'g'>])> print>(>'
Frozen Set'>)> print>(frozen_set)> # Uncommenting below line would cause error as> # we are trying to add element to a frozen set> # frozen_set.add('h')> |
>
>Ausgabe
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Zeichenfolge
Python-Strings sind Byte-Arrays, die Unicode-Zeichen darstellen. Einfacher ausgedrückt ist ein String ein unveränderliches Array von Zeichen. Python hat keinen Zeichendatentyp, ein einzelnes Zeichen ist einfach eine Zeichenfolge mit der Länge 1.
Notiz: Da Zeichenfolgen unveränderlich sind, führt die Änderung einer Zeichenfolge zur Erstellung einer neuen Kopie.
Beispiel: Python-Strings-Operationen
Python3
String>=> 'Welcome to GeeksForGeeks'> print>(>'Creating String: '>)> print>(String)> > # Printing First character> print>(>'
First character of String is: '>)> print>(String[>0>])> > # Printing Last character> print>(>'
Last character of String is: '>)> print>(String[>->1>])> |
>
>Ausgabe
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray liefert eine veränderbare Folge von Ganzzahlen im Bereich 0 <= x < 256.
Beispiel: Python-Bytearray-Operationen
Python3
# Creating bytearray> a>=> bytearray((>12>,>8>,>25>,>2>))> print>(>'Creating Bytearray:'>)> print>(a)> # accessing elements> print>(>'
Accessing Elements:'>, a[>1>])> # modifying elements> a[>1>]>=> 3> print>(>'
After Modifying:'>)> print>(a)> # Appending elements> a.append(>30>)> print>(>'
After Adding Elements:'>)> print>(a)> |
>
>Ausgabe
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Bisher haben wir alle Datenstrukturen untersucht, die in den Kern von Python integriert sind. Lassen Sie uns nun tiefer in Python eintauchen und sehen Sie sich das Collections-Modul an, das einige Container bereitstellt, die in vielen Fällen nützlich sind und mehr Funktionen als die oben definierten Funktionen bieten.
Sammlungsmodul
Das Python-Sammlungsmodul wurde eingeführt, um die Funktionalität der integrierten Datentypen zu verbessern. Es bietet verschiedene Container. Sehen wir uns jeden einzelnen im Detail an.
Zähler
Ein Zähler ist eine Unterklasse des Wörterbuchs. Es wird verwendet, um die Anzahl der Elemente in einem Iterable in Form eines ungeordneten Wörterbuchs zu speichern, wobei der Schlüssel das Element im Iterable und der Wert die Anzahl dieses Elements im Iterable darstellt. Dies entspricht einer Tasche oder einem Multiset anderer Sprachen.
Beispiel: Python-Zähleroperationen
Python3
from> collections>import> Counter> > # With sequence of items> print>(Counter([>'B'>,>'B'>,>'A'>,>'B'>,>'C'>,>'A'>,>'B'>,>'B'>,>'A'>,>'C'>]))> > # with dictionary> count>=> Counter({>'A'>:>3>,>'B'>:>5>,>'C'>:>2>})> print>(count)> count.update([>'A'>,>1>])> print>(count)> |
>
>Ausgabe
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> OrderedDict
Ein OrderedDict ist ebenfalls eine Unterklasse des Wörterbuchs, merkt sich aber im Gegensatz zu einem Wörterbuch die Reihenfolge, in der die Schlüssel eingefügt wurden.
Beispiel: Python OrderedDict-Operationen
Python3
from> collections>import> OrderedDict> print>(>'Before deleting:
'>)> od>=> OrderedDict()> od[>'a'>]>=> 1> od[>'b'>]>=> 2> od[>'c'>]>=> 3> od[>'d'>]>=> 4> for> key, value>in> od.items():> >print>(key, value)> print>(>'
After deleting:
'>)> od.pop(>'c'>)> for> key, value>in> od.items():> >print>(key, value)> print>(>'
After re-inserting:
'>)> od[>'c'>]>=> 3> for> key, value>in> od.items():> >print>(key, value)> |
>
>Ausgabe
Before deleting: a 1 b 2 c 3 d 4 After deleting: a 1 b 2 d 4 After re-inserting: a 1 b 2 d 4 c 3>
DefaultDict
DefaultDict wird verwendet, um einige Standardwerte für den Schlüssel bereitzustellen, der nicht existiert und niemals einen KeyError auslöst. Seine Objekte können mit der Methode DefaultDict() initialisiert werden, indem der Datentyp als Argument übergeben wird.
Notiz: default_factory ist eine Funktion, die den Standardwert für das erstellte Wörterbuch bereitstellt. Fehlt dieser Parameter, wird der KeyError ausgelöst.
Beispiel: Python DefaultDict-Operationen
Python3
from> collections>import> defaultdict> > # Defining the dict> d>=> defaultdict(>int>)> > L>=> [>1>,>2>,>3>,>4>,>2>,>4>,>1>,>2>]> > # Iterate through the list> # for keeping the count> for> i>in> L:> > ># The default value is 0> ># so there is no need to> ># enter the key first> >d[i]>+>=> 1> > print>(d)> |
>
>Ausgabe
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> ChainMap
Eine ChainMap kapselt viele Wörterbücher in einer einzigen Einheit und gibt eine Liste von Wörterbüchern zurück. Wenn ein Schlüssel gefunden werden muss, werden alle Wörterbücher nacheinander durchsucht, bis der Schlüssel gefunden ist.
Beispiel: Python ChainMap-Operationen
Python3
from> collections>import> ChainMap> > > d1>=> {>'a'>:>1>,>'b'>:>2>}> d2>=> {>'c'>:>3>,>'d'>:>4>}> d3>=> {>'e'>:>5>,>'f'>:>6>}> > # Defining the chainmap> c>=> ChainMap(d1, d2, d3)> print>(c)> print>(c[>'a'>])> print>(c[>'g'>])> |
>
>
Ausgabe
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
NamedTuple
A NamedTuple gibt ein Tupelobjekt mit Namen für jede Position zurück, die den gewöhnlichen Tupeln fehlt. Betrachten Sie beispielsweise ein Tupel namens student, bei dem das erste Element fname, das zweite lname und das dritte Element das Geburtsdatum darstellt. Angenommen, Sie können zum Aufrufen von fname, anstatt sich die Indexposition zu merken, das Element tatsächlich mit dem Argument fname aufrufen. Dann ist der Zugriff auf das Tupelelement wirklich einfach. Diese Funktionalität wird vom NamedTuple bereitgestellt.
Beispiel: Python NamedTuple-Operationen
Python3
from> collections>import> namedtuple> > # Declaring namedtuple()> Student>=> namedtuple(>'Student'>,[>'name'>,>'age'>,>'DOB'>])> > # Adding values> S>=> Student(>'Nandini'>,>'19'>,>'2541997'>)> > # Access using index> print> (>'The Student age using index is : '>,end>=>'')> print> (S[>1>])> > # Access using name> print> (>'The Student name using keyname is : '>,end>=>'')> print> (S.name)> |
>
>Ausgabe
The Student age using index is : 19 The Student name using keyname is : Nandini>
Worüber
Deque (doppelt beendete Warteschlange) ist die optimierte Liste für schnellere Anhänge- und Pop-Vorgänge von beiden Seiten des Containers. Sie bietet O(1)-Zeitkomplexität für Anhänge- und Popup-Operationen im Vergleich zur Liste mit O(n)-Zeitkomplexität.
Python Deque wird mithilfe doppelt verknüpfter Listen implementiert, daher beträgt die Leistung für den zufälligen Zugriff auf die Elemente O(n).
Beispiel: Python-Deque-Operationen
Python3
# importing 'collections' for deque operations> import> collections> # initializing deque> de>=> collections.deque([>1>,>2>,>3>])> # using append() to insert element at right end> # inserts 4 at the end of deque> de.append(>4>)> # printing modified deque> print>(>'The deque after appending at right is : '>)> print>(de)> # using appendleft() to insert element at left end> # inserts 6 at the beginning of deque> de.appendleft(>6>)> # printing modified deque> print>(>'The deque after appending at left is : '>)> print>(de)> # using pop() to delete element from right end> # deletes 4 from the right end of deque> de.pop()> # printing modified deque> print>(>'The deque after deleting from right is : '>)> print>(de)> # using popleft() to delete element from left end> # deletes 6 from the left end of deque> de.popleft()> # printing modified deque> print>(>'The deque after deleting from left is : '>)> print>(de)> |
Prioritätswarteschlange C++
>
>Ausgabe
The deque after appending at right is : deque([1, 2, 3, 4]) The deque after appending at left is : deque([6, 1, 2, 3, 4]) The deque after deleting from right is : deque([6, 1, 2, 3]) The deque after deleting from left is : deque([1, 2, 3])>
UserDict
UserDict ist ein wörterbuchähnlicher Container, der als Wrapper für die Wörterbuchobjekte fungiert. Dieser Container wird verwendet, wenn jemand sein eigenes Wörterbuch mit geänderten oder neuen Funktionen erstellen möchte.
Beispiel: Python UserDict
Python3
from> collections>import> UserDict> # Creating a Dictionary where> # deletion is not allowed> class> MyDict(UserDict):> > ># Function to stop deletion> ># from dictionary> >def> __del__(>self>):> >raise> RuntimeError(>'Deletion not allowed'>)> > ># Function to stop pop from> ># dictionary> >def> pop(>self>, s>=> None>):> >raise> RuntimeError(>'Deletion not allowed'>)> > ># Function to stop popitem> ># from Dictionary> >def> popitem(>self>, s>=> None>):> >raise> RuntimeError(>'Deletion not allowed'>)> > # Driver's code> d>=> MyDict({>'a'>:>1>,> >'b'>:>2>,> >'c'>:>3>})> print>(>'Original Dictionary'>)> print>(d)> d.pop(>1>)> |
>
>
Ausgabe
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Benutzerliste
UserList ist ein listenähnlicher Container, der als Wrapper um die Listenobjekte fungiert. Dies ist nützlich, wenn jemand eine eigene Liste mit geänderten oder zusätzlichen Funktionen erstellen möchte.
Beispiele: Python-Benutzerliste
Python3
# Python program to demonstrate> # userlist> from> collections>import> UserList> # Creating a List where> # deletion is not allowed> class> MyList(UserList):> > ># Function to stop deletion> ># from List> >def> remove(>self>, s>=> None>):> >raise> RuntimeError(>'Deletion not allowed'>)> > ># Function to stop pop from> ># List> >def> pop(>self>, s>=> None>):> >raise> RuntimeError(>'Deletion not allowed'>)> > # Driver's code> L>=> MyList([>1>,>2>,>3>,>4>])> print>(>'Original List'>)> print>(L)> # Inserting to List'> L.append(>5>)> print>(>'After Insertion'>)> print>(L)> # Deleting From List> L.remove()> |
>
>
Ausgabe
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
Benutzerzeichenfolge
UserString ist ein String-ähnlicher Container und fungiert genau wie UserDict und UserList als Wrapper für String-Objekte. Es wird verwendet, wenn jemand eigene Zeichenfolgen mit geänderter oder zusätzlicher Funktionalität erstellen möchte.
Beispiel: Python UserString
Python3
from> collections>import> UserString> # Creating a Mutable String> class> Mystring(UserString):> > ># Function to append to> ># string> >def> append(>self>, s):> >self>.data>+>=> s> > ># Function to remove from> ># string> >def> remove(>self>, s):> >self>.data>=> self>.data.replace(s, '')> > # Driver's code> s1>=> Mystring(>'Geeks'>)> print>(>'Original String:'>, s1.data)> # Appending to string> s1.append(>'s'>)> print>(>'String After Appending:'>, s1.data)> # Removing from string> s1.remove(>'e'>)> print>(>'String after Removing:'>, s1.data)> |
>
>Ausgabe
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Nachdem wir nun alle Datenstrukturen untersucht haben, wollen wir uns einige erweiterte Datenstrukturen wie Stapel, Warteschlange, Diagramm, verknüpfte Liste usw. ansehen, die in der Python-Sprache verwendet werden können.
Verlinkte Liste
Eine verknüpfte Liste ist eine lineare Datenstruktur, bei der die Elemente nicht an zusammenhängenden Speicherorten gespeichert sind. Die Elemente in einer verknüpften Liste werden mithilfe von Zeigern verknüpft, wie im folgenden Bild dargestellt:
Eine verknüpfte Liste wird durch einen Zeiger auf den ersten Knoten der verknüpften Liste dargestellt. Der erste Knoten wird Kopf genannt. Wenn die verknüpfte Liste leer ist, ist der Wert des Kopfes NULL. Jeder Knoten in einer Liste besteht aus mindestens zwei Teilen:
- Daten
- Zeiger (oder Referenz) auf den nächsten Knoten
Beispiel: Definieren einer verknüpften Liste in Python
Python3
# Node class> class> Node:> ># Function to initialize the node object> >def> __init__(>self>, data):> >self>.data>=> data># Assign data> >self>.>next> => None> # Initialize> ># next as null> # Linked List class> class> LinkedList:> > ># Function to initialize the Linked> ># List object> >def> __init__(>self>):> >self>.head>=> None> |
>
>
Lassen Sie uns eine einfache verknüpfte Liste mit 3 Knoten erstellen.
Python3
# A simple Python program to introduce a linked list> # Node class> class> Node:> ># Function to initialise the node object> >def> __init__(>self>, data):> >self>.data>=> data># Assign data> >self>.>next> => None> # Initialize next as null> # Linked List class contains a Node object> class> LinkedList:> ># Function to initialize head> >def> __init__(>self>):> >self>.head>=> None> # Code execution starts here> if> __name__>=>=>'__main__'>:> ># Start with the empty list> >list> => LinkedList()> >list>.head>=> Node(>1>)> >second>=> Node(>2>)> >third>=> Node(>3>)> >'''> >Three nodes have been created.> >We have references to these three blocks as head,> >second and third> >list.head second third> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | None | | 2 | None | | 3 | None |> >+----+------+ +----+------+ +----+------+> >'''> >list>.head.>next> => second;># Link first node with second> >'''> >Now next of first Node refers to second. So they> >both are linked.> >list.head second third> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | o-------->| 2 | null | | 3 | null |> >+----+------+ +----+------+ +----+------+> >'''> >second.>next> => third;># Link second node with the third node> >'''> >Now next of second Node refers to third. So all three> >nodes are linked.> >list.head second third> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | o-------->| 2 | o-------->| 3 | null |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Durchquerung verknüpfter Listen
Im vorherigen Programm haben wir eine einfache verknüpfte Liste mit drei Knoten erstellt. Lassen Sie uns die erstellte Liste durchlaufen und die Daten jedes Knotens drucken. Schreiben wir zum Durchlaufen eine Allzweckfunktion printList(), die eine beliebige Liste druckt.
Python3
# A simple Python program for traversal of a linked list> # Node class> class> Node:> ># Function to initialise the node object> >def> __init__(>self>, data):> >self>.data>=> data># Assign data> >self>.>next> => None> # Initialize next as null> # Linked List class contains a Node object> class> LinkedList:> ># Function to initialize head> >def> __init__(>self>):> >self>.head>=> None> ># This function prints contents of linked list> ># starting from head> >def> printList(>self>):> >temp>=> self>.head> >while> (temp):> >print> (temp.data)> >temp>=> temp.>next> # Code execution starts here> if> __name__>=>=>'__main__'>:> ># Start with the empty list> >list> => LinkedList()> >list>.head>=> Node(>1>)> >second>=> Node(>2>)> >third>=> Node(>3>)> >list>.head.>next> => second;># Link first node with second> >second.>next> => third;># Link second node with the third node> >list>.printList()> |
>
>Ausgabe
1 2 3>
Stapel
A Stapel ist eine lineare Datenstruktur, die Elemente nach dem Last-In/First-Out-Prinzip (LIFO) oder dem First-In/Last-Out-Prinzip (FILO) speichert. Im Stapel wird ein neues Element an einem Ende hinzugefügt und ein Element nur an diesem Ende entfernt. Die Einfüge- und Löschvorgänge werden oft als Push und Pop bezeichnet.
Die mit dem Stapel verbundenen Funktionen sind:
- empty() – Gibt zurück, ob der Stapel leer ist – Zeitkomplexität: O(1) size() – Gibt die Größe des Stapels zurück – Zeitkomplexität: O(1) top() – Gibt einen Verweis auf das oberste Element des Stapels zurück – Zeitkomplexität: O(1) push(a) – Fügt das Element „a“ oben im Stapel ein – Zeitkomplexität: O(1) pop() – Löscht das oberste Element des Stapels – Zeitkomplexität: O( 1)
Python-Stack-Implementierung
Stack in Python kann auf folgende Weise implementiert werden:
- Liste
- Sammlungen.deque
- queue.LifoQueue
Implementierung mit List
Die in Python integrierte Datenstrukturliste kann als Stapel verwendet werden. Anstelle von push() wird append() verwendet, um Elemente oben im Stapel hinzuzufügen, während pop() das Element in LIFO-Reihenfolge entfernt.
Python3
stack>=> []> # append() function to push> # element in the stack> stack.append(>'g'>)> stack.append(>'f'>)> stack.append(>'g'>)> print>(>'Initial stack'>)> print>(stack)> # pop() function to pop> # element from stack in> # LIFO order> print>(>'
Elements popped from stack:'>)> print>(stack.pop())> print>(stack.pop())> print>(stack.pop())> print>(>'
Stack after elements are popped:'>)> print>(stack)> # uncommenting print(stack.pop())> # will cause an IndexError> # as the stack is now empty> |
>
>Ausgabe
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementierung mitcollections.deque:
Der Python-Stack kann mithilfe der Deque-Klasse aus dem Collections-Modul implementiert werden. Deque wird gegenüber der Liste in den Fällen bevorzugt, in denen wir schnellere Anhänge- und Popup-Vorgänge von beiden Enden des Containers benötigen, da deque im Vergleich zur Liste, die O(n) bereitstellt, eine Zeitkomplexität von O(1) für Append- und Pop-Vorgänge bietet. Zeitkomplexität.
Python3
from> collections>import> deque> stack>=> deque()> # append() function to push> # element in the stack> stack.append(>'g'>)> stack.append(>'f'>)> stack.append(>'g'>)> print>(>'Initial stack:'>)> print>(stack)> # pop() function to pop> # element from stack in> # LIFO order> print>(>'
Elements popped from stack:'>)> print>(stack.pop())> print>(stack.pop())> print>(stack.pop())> print>(>'
Stack after elements are popped:'>)> print>(stack)> # uncommenting print(stack.pop())> # will cause an IndexError> # as the stack is now empty> |
>
>Ausgabe
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementierung mithilfe des Warteschlangenmoduls
Das Warteschlangenmodul verfügt auch über eine LIFO-Warteschlange, bei der es sich im Grunde um einen Stapel handelt. Daten werden mit der Funktion put() in die Warteschlange eingefügt und get() entnimmt Daten aus der Warteschlange.
Python3
from> queue>import> LifoQueue> # Initializing a stack> stack>=> LifoQueue(maxsize>=> 3>)> # qsize() show the number of elements> # in the stack> print>(stack.qsize())> # put() function to push> # element in the stack> stack.put(>'g'>)> stack.put(>'f'>)> stack.put(>'g'>)> print>(>'Full: '>, stack.full())> print>(>'Size: '>, stack.qsize())> # get() function to pop> # element from stack in> # LIFO order> print>(>'
Elements popped from the stack'>)> print>(stack.get())> print>(stack.get())> print>(stack.get())> print>(>'
Empty: '>, stack.empty())> |
>
>Ausgabe
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Warteschlange
Als Stapel werden die Warteschlange ist eine lineare Datenstruktur, die Elemente nach dem FIFO-Prinzip (First In First Out) speichert. Bei einer Warteschlange wird das zuletzt hinzugefügte Element zuerst entfernt. Ein gutes Beispiel für die Warteschlange ist eine beliebige Warteschlange von Verbrauchern für eine Ressource, bei der der Verbraucher, der zuerst kam, zuerst bedient wird.
Mit der Warteschlange verbundene Vorgänge sind:
- Enqueue: Fügt ein Element zur Warteschlange hinzu. Wenn die Warteschlange voll ist, spricht man von einer Überlaufbedingung – Zeitkomplexität: O(1) Aus der Warteschlange entfernen: Entfernt ein Element aus der Warteschlange. Die Elemente werden in der gleichen Reihenfolge abgelegt, in der sie abgelegt werden. Wenn die Warteschlange leer ist, spricht man von einer Unterlaufbedingung – Zeitkomplexität: O(1) Vorne: Holen Sie sich das vordere Element aus der Warteschlange – Zeitkomplexität: O(1) Hinten: Holen Sie sich das letzte Element aus der Warteschlange – Zeitkomplexität : O(1)
Implementierung der Python-Warteschlange
Die Warteschlange in Python kann auf folgende Weise implementiert werden:
- Liste
- Sammlungen.deque
- Schwanz.Schwanz
Implementierung mit Liste
Anstelle von enqueue() und dequeue() werden die Funktionen append() und pop() verwendet.
Python3
# Initializing a queue> queue>=> []> # Adding elements to the queue> queue.append(>'g'>)> queue.append(>'f'>)> queue.append(>'g'>)> print>(>'Initial queue'>)> print>(queue)> # Removing elements from the queue> print>(>'
Elements dequeued from queue'>)> print>(queue.pop(>0>))> print>(queue.pop(>0>))> print>(queue.pop(>0>))> print>(>'
Queue after removing elements'>)> print>(queue)> # Uncommenting print(queue.pop(0))> # will raise and IndexError> # as the queue is now empty> |
>
>Ausgabe
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementierung mitcollections.deque
Deque wird gegenüber der Liste in den Fällen bevorzugt, in denen wir schnellere Anhänge- und Popup-Vorgänge von beiden Enden des Containers benötigen, da deque im Vergleich zur Liste, die O(n) bereitstellt, eine Zeitkomplexität von O(1) für Append- und Pop-Vorgänge bietet. Zeitkomplexität.
Python3
from> collections>import> deque> # Initializing a queue> q>=> deque()> # Adding elements to a queue> q.append(>'g'>)> q.append(>'f'>)> q.append(>'g'>)> print>(>'Initial queue'>)> print>(q)> # Removing elements from a queue> print>(>'
Elements dequeued from the queue'>)> print>(q.popleft())> print>(q.popleft())> print>(q.popleft())> print>(>'
Queue after removing elements'>)> print>(q)> # Uncommenting q.popleft()> # will raise an IndexError> # as queue is now empty> |
>
>Ausgabe
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementierung mithilfe der queue.Queue
Datum des Typoskripts
queue.Queue(maxsize) initialisiert eine Variable auf die maximale Größe maxsize. Eine maximale Größe von Null „0“ bedeutet eine unendliche Warteschlange. Diese Warteschlange folgt der FIFO-Regel.
Python3
from> queue>import> Queue> # Initializing a queue> q>=> Queue(maxsize>=> 3>)> # qsize() give the maxsize> # of the Queue> print>(q.qsize())> # Adding of element to queue> q.put(>'g'>)> q.put(>'f'>)> q.put(>'g'>)> # Return Boolean for Full> # Queue> print>(>'
Full: '>, q.full())> # Removing element from queue> print>(>'
Elements dequeued from the queue'>)> print>(q.get())> print>(q.get())> print>(q.get())> # Return Boolean for Empty> # Queue> print>(>'
Empty: '>, q.empty())> q.put(>1>)> print>(>'
Empty: '>, q.empty())> print>(>'Full: '>, q.full())> # This would result into Infinite> # Loop as the Queue is empty.> # print(q.get())> |
>
>Ausgabe
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Prioritätswarteschlange
Prioritätswarteschlangen sind abstrakte Datenstrukturen, bei denen alle Daten/Werte in der Warteschlange eine bestimmte Priorität haben. Beispielsweise kommt bei Fluggesellschaften Gepäck mit der Bezeichnung Business oder First Class früher an als der Rest. Die Prioritätswarteschlange ist eine Erweiterung der Warteschlange mit den folgenden Eigenschaften.
- Ein Element mit hoher Priorität wird vor einem Element mit niedriger Priorität aus der Warteschlange entfernt.
- Wenn zwei Elemente die gleiche Priorität haben, werden sie entsprechend ihrer Reihenfolge in der Warteschlange bedient.
Python3
# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(>object>):> >def> __init__(>self>):> >self>.queue>=> []> >def> __str__(>self>):> >return> ' '>.join([>str>(i)>for> i>in> self>.queue])> ># for checking if the queue is empty> >def> isEmpty(>self>):> >return> len>(>self>.queue)>=>=> 0> ># for inserting an element in the queue> >def> insert(>self>, data):> >self>.queue.append(data)> ># for popping an element based on Priority> >def> delete(>self>):> >try>:> >max> => 0> >for> i>in> range>(>len>(>self>.queue)):> >if> self>.queue[i]>>self>.queue[>max>]:> >max> => i> >item>=> self>.queue[>max>]> >del> self>.queue[>max>]> >return> item> >except> IndexError:> >print>()> >exit()> if> __name__>=>=> '__main__'>:> >myQueue>=> PriorityQueue()> >myQueue.insert(>12>)> >myQueue.insert(>1>)> >myQueue.insert(>14>)> >myQueue.insert(>7>)> >print>(myQueue)> >while> not> myQueue.isEmpty():> >print>(myQueue.delete())> |
>
>Ausgabe
12 1 14 7 14 12 7 1>
Heap-Warteschlange (oder Heapq)
heapq-Modul in Python stellt die Heap-Datenstruktur bereit, die hauptsächlich zur Darstellung einer Prioritätswarteschlange verwendet wird. Die Eigenschaft dieser Datenstruktur in Python besteht darin, dass jedes Mal das kleinste Heap-Element entfernt wird (min-heap). Immer wenn Elemente verschoben oder entfernt werden, bleibt die Heap-Struktur erhalten. Das Element heap[0] gibt außerdem jedes Mal das kleinste Element zurück.
Es unterstützt das Extrahieren und Einfügen des kleinsten Elements in den O(log n)-Zeiten.
Python3
# importing 'heapq' to implement heap queue> import> heapq> # initializing list> li>=> [>5>,>7>,>9>,>1>,>3>]> # using heapify to convert list into heap> heapq.heapify(li)> # printing created heap> print> (>'The created heap is : '>,end>=>'')> print> (>list>(li))> # using heappush() to push elements into heap> # pushes 4> heapq.heappush(li,>4>)> # printing modified heap> print> (>'The modified heap after push is : '>,end>=>'')> print> (>list>(li))> # using heappop() to pop smallest element> print> (>'The popped and smallest element is : '>,end>=>'')> print> (heapq.heappop(li))> |
>
>Ausgabe
The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1>
Binärer Baum
Ein Baum ist eine hierarchische Datenstruktur, die wie in der folgenden Abbildung aussieht –
tree ---- j <-- root / f k / a h z <-- leaves>
Der oberste Knoten des Baums wird als Wurzel bezeichnet, während die untersten Knoten oder Knoten ohne Kinder als Blattknoten bezeichnet werden. Die Knoten, die sich direkt unter einem Knoten befinden, werden als dessen untergeordnete Knoten bezeichnet, und die Knoten, die direkt über einem Knoten liegen, werden als dessen übergeordnete Knoten bezeichnet.
Ein Binärbaum ist ein Baum, dessen Elemente fast zwei untergeordnete Elemente haben können. Da jedes Element in einem Binärbaum nur zwei untergeordnete Elemente haben kann, nennen wir sie normalerweise das linke und das rechte untergeordnete Element. Ein Binärbaumknoten enthält die folgenden Teile.
- Daten
- Zeiger auf das linke untergeordnete Element
- Zeiger auf das richtige Kind
Beispiel: Knotenklasse definieren
Python3
# A Python class that represents an individual node> # in a Binary Tree> class> Node:> >def> __init__(>self>,key):> >self>.left>=> None> >self>.right>=> None> >self>.val>=> key> |
>
>
Lassen Sie uns nun einen Baum mit 4 Knoten in Python erstellen. Nehmen wir an, die Baumstruktur sieht wie folgt aus:
tree ---- 1 <-- root / 2 3 / 4>
Beispiel: Daten zum Baum hinzufügen
Python3
# Python program to introduce Binary Tree> # A class that represents an individual node in a> # Binary Tree> class> Node:> >def> __init__(>self>,key):> >self>.left>=> None> >self>.right>=> None> >self>.val>=> key> # create root> root>=> Node(>1>)> ''' following is the tree after above statement> >1> >/> >None None'''> root.left>=> Node(>2>);> root.right>=> Node(>3>);> ''' 2 and 3 become left and right children of 1> >1> >/> >2 3> >/ /> None None None None'''> root.left.left>=> Node(>4>);> '''4 becomes left child of 2> >1> >/> >2 3> >/ /> 4 None None None> /> None None'''> |
>
>
Baumdurchquerung
Bäume können überquert werden auf veschiedenen Wegen. Im Folgenden sind die allgemein verwendeten Methoden zum Überqueren von Bäumen aufgeführt. Betrachten wir den folgenden Baum –
tree ---- 1 <-- root / 2 3 / 4 5>
Tiefendurchquerungen:
- Reihenfolge (Links, Wurzel, Rechts): 4 2 5 1 3
- Vorbestellung (Root, Left, Right): 1 2 4 5 3
- Postorder (Links, Rechts, Root): 4 5 2 3 1
Algorithmus Inorder(Baum)
- Durchlaufen Sie den linken Teilbaum, d. h. rufen Sie Inorder(left-subtree) auf.
- Besuchen Sie die Wurzel.
- Durchqueren Sie den rechten Teilbaum, d. h. rufen Sie Inorder(right-subtree) auf.
Algorithmus-Vorbestellung (Baum)
- Besuchen Sie die Wurzel.
- Durchqueren Sie den linken Teilbaum, d. h. rufen Sie Preorder(left-subtree) auf.
- Durchqueren Sie den rechten Teilbaum, d. h. rufen Sie Preorder(right-subtree) auf.
Algorithmus Postanweisung(Baum)
- Durchqueren Sie den linken Teilbaum, d. h. rufen Sie Postorder(left-subtree) auf.
- Durchqueren Sie den rechten Teilbaum, d. h. rufen Sie Postorder(right-subtree) auf.
- Besuchen Sie die Wurzel.
Python3
# Python program to for tree traversals> # A class that represents an individual node in a> # Binary Tree> class> Node:> >def> __init__(>self>, key):> >self>.left>=> None> >self>.right>=> None> >self>.val>=> key> # A function to do inorder tree traversal> def> printInorder(root):> >if> root:> ># First recur on left child> >printInorder(root.left)> ># then print the data of node> >print>(root.val),> ># now recur on right child> >printInorder(root.right)> # A function to do postorder tree traversal> def> printPostorder(root):> >if> root:> ># First recur on left child> >printPostorder(root.left)> ># the recur on right child> >printPostorder(root.right)> ># now print the data of node> >print>(root.val),> # A function to do preorder tree traversal> def> printPreorder(root):> >if> root:> ># First print the data of node> >print>(root.val),> ># Then recur on left child> >printPreorder(root.left)> ># Finally recur on right child> >printPreorder(root.right)> # Driver code> root>=> Node(>1>)> root.left>=> Node(>2>)> root.right>=> Node(>3>)> root.left.left>=> Node(>4>)> root.left.right>=> Node(>5>)> print>(>'Preorder traversal of binary tree is'>)> printPreorder(root)> print>(>'
Inorder traversal of binary tree is'>)> printInorder(root)> print>(>'
Postorder traversal of binary tree is'>)> printPostorder(root)> |
>
>Ausgabe
Preorder traversal of binary tree is 1 2 4 5 3 Inorder traversal of binary tree is 4 2 5 1 3 Postorder traversal of binary tree is 4 5 2 3 1>
Zeitkomplexität – O(n)
Breitenorientierte oder ebene Ordnungsdurchquerung
Durchqueren der Level-Reihenfolge eines Baumes ist die Breitendurchquerung für den Baum. Die Ebenenreihenfolge des obigen Baums beträgt 1 2 3 4 5.
Für jeden Knoten wird zunächst der Knoten besucht und dann werden seine untergeordneten Knoten in eine FIFO-Warteschlange gestellt. Unten ist der Algorithmus dafür –
- Erstellen Sie eine leere Warteschlange q
- temp_node = root /*start from root*/
- Schleife, während temp_node nicht NULL ist
- temp_node->data drucken.
- Stellen Sie die Kinder von temp_node (zuerst die linken, dann die rechten Kinder) in die Warteschlange q
- Entfernen Sie einen Knoten aus q
Python3
# Python program to print level> # order traversal using Queue> # A node structure> class> Node:> > ># A utility function to create a new node> >def> __init__(>self> ,key):> >self>.data>=> key> >self>.left>=> None> >self>.right>=> None> # Iterative Method to print the> # height of a binary tree> def> printLevelOrder(root):> > ># Base Case> >if> root>is> None>:> >return> > ># Create an empty queue> ># for level order traversal> >queue>=> []> ># Enqueue Root and initialize height> >queue.append(root)> >while>(>len>(queue)>>0>):> > ># Print front of queue and> ># remove it from queue> >print> (queue[>0>].data)> >node>=> queue.pop(>0>)> ># Enqueue left child> >if> node.left>is> not> None>:> >queue.append(node.left)> ># Enqueue right child> >if> node.right>is> not> None>:> >queue.append(node.right)> # Driver Program to test above function> root>=> Node(>1>)> root.left>=> Node(>2>)> root.right>=> Node(>3>)> root.left.left>=> Node(>4>)> root.left.right>=> Node(>5>)> print> (>'Level Order Traversal of binary tree is -'>)> printLevelOrder(root)> |
>
>Ausgabe
Level Order Traversal of binary tree is - 1 2 3 4 5>
Zeitkomplexität: O(n)
Graph
A Graph ist eine nichtlineare Datenstruktur bestehend aus Knoten und Kanten. Die Knoten werden manchmal auch als Eckpunkte bezeichnet und die Kanten sind Linien oder Bögen, die zwei beliebige Knoten im Diagramm verbinden. Formaler kann ein Graph als ein Graph definiert werden, der aus einer endlichen Menge von Eckpunkten (oder Knoten) und einer Menge von Kanten besteht, die ein Knotenpaar verbinden.
Im obigen Diagramm ist die Menge der Eckpunkte V = {0,1,2,3,4} und die Menge der Kanten E = {01, 12, 23, 34, 04, 14, 13}.
Die folgenden beiden sind die am häufigsten verwendeten Darstellungen eines Diagramms.
- Adjazenzmatrix
- Adjazenzliste
Adjazenzmatrix
Die Adjazenzmatrix ist ein 2D-Array der Größe V x V, wobei V die Anzahl der Eckpunkte in einem Diagramm ist. Das 2D-Array sei adj[][], ein Schlitz adj[i][j] = 1 zeigt an, dass es eine Kante vom Scheitelpunkt i zum Scheitelpunkt j gibt. Die Adjazenzmatrix für einen ungerichteten Graphen ist immer symmetrisch. Die Adjazenzmatrix wird auch zur Darstellung gewichteter Diagramme verwendet. Wenn adj[i][j] = w, dann gibt es eine Kante vom Scheitelpunkt i zum Scheitelpunkt j mit dem Gewicht w.
Python3
# A simple representation of graph using Adjacency Matrix> class> Graph:> >def> __init__(>self>,numvertex):> >self>.adjMatrix>=> [[>->1>]>*>numvertex>for> x>in> range>(numvertex)]> >self>.numvertex>=> numvertex> >self>.vertices>=> {}> >self>.verticeslist>=>[>0>]>*>numvertex> >def> set_vertex(>self>,vtx,>id>):> >if> 0><>=>vtx<>=>self>.numvertex:> >self>.vertices[>id>]>=> vtx> >self>.verticeslist[vtx]>=> id> >def> set_edge(>self>,frm,to,cost>=>0>):> >frm>=> self>.vertices[frm]> >to>=> self>.vertices[to]> >self>.adjMatrix[frm][to]>=> cost> > ># for directed graph do not add this> >self>.adjMatrix[to][frm]>=> cost> >def> get_vertex(>self>):> >return> self>.verticeslist> >def> get_edges(>self>):> >edges>=>[]> >for> i>in> range> (>self>.numvertex):> >for> j>in> range> (>self>.numvertex):> >if> (>self>.adjMatrix[i][j]!>=>->1>):> >edges.append((>self>.verticeslist[i],>self>.verticeslist[j],>self>.adjMatrix[i][j]))> >return> edges> > >def> get_matrix(>self>):> >return> self>.adjMatrix> G>=>Graph(>6>)> G.set_vertex(>0>,>'a'>)> G.set_vertex(>1>,>'b'>)> G.set_vertex(>2>,>'c'>)> G.set_vertex(>3>,>'d'>)> G.set_vertex(>4>,>'e'>)> G.set_vertex(>5>,>'f'>)> G.set_edge(>'a'>,>'e'>,>10>)> G.set_edge(>'a'>,>'c'>,>20>)> G.set_edge(>'c'>,>'b'>,>30>)> G.set_edge(>'b'>,>'e'>,>40>)> G.set_edge(>'e'>,>'d'>,>50>)> G.set_edge(>'f'>,>'e'>,>60>)> print>(>'Vertices of Graph'>)> print>(G.get_vertex())> print>(>'Edges of Graph'>)> print>(G.get_edges())> print>(>'Adjacency Matrix of Graph'>)> print>(G.get_matrix())> |
>
>
Ausgabe
Eckpunkte des Graphen
[‚a‘, ‚b‘, ‚c‘, ‚d‘, ‚e‘, ‚f‘]
Kanten des Diagramms
[('a', 'c', 20), ('a', 'e', 10), ('b', 'c', 30), ('b', 'e', 40), ( 'c', 'a', 20), ('c', 'b', 30), ('d', 'e', 50), ('e', 'a', 10), ('e ', 'b', 40), ('e', 'd', 50), ('e', 'f', 60), ('f', 'e', 60)]
Adjazenzmatrix des Graphen
[[-1, -1, 20, -1, 10, -1], [-1, -1, 30, -1, 40, -1], [20, 30, -1, -1, -1 , -1], [-1, -1, -1, -1, 50, -1], [10, 40, -1, 50, -1, 60], [-1, -1, -1, -1, 60, -1]]
Adjazenzliste
Es wird ein Array von Listen verwendet. Die Größe des Arrays entspricht der Anzahl der Scheitelpunkte. Das Array sei ein Array[]. Ein Eintragsarray[i] repräsentiert die Liste der Scheitelpunkte neben dem i-ten Scheitelpunkt. Diese Darstellung kann auch zur Darstellung eines gewichteten Diagramms verwendet werden. Die Gewichte von Kanten können als Listen von Paaren dargestellt werden. Es folgt die Adjazenzlistendarstellung des obigen Diagramms.
Python3
# A class to represent the adjacency list of the node> class> AdjNode:> >def> __init__(>self>, data):> >self>.vertex>=> data> >self>.>next> => None> # A class to represent a graph. A graph> # is the list of the adjacency lists.> # Size of the array will be the no. of the> # vertices 'V'> class> Graph:> >def> __init__(>self>, vertices):> >self>.V>=> vertices> >self>.graph>=> [>None>]>*> self>.V> ># Function to add an edge in an undirected graph> >def> add_edge(>self>, src, dest):> > ># Adding the node to the source node> >node>=> AdjNode(dest)> >node.>next> => self>.graph[src]> >self>.graph[src]>=> node> ># Adding the source node to the destination as> ># it is the undirected graph> >node>=> AdjNode(src)> >node.>next> => self>.graph[dest]> >self>.graph[dest]>=> node> ># Function to print the graph> >def> print_graph(>self>):> >for> i>in> range>(>self>.V):> >print>(>'Adjacency list of vertex {}
head'>.>format>(i), end>=>'')> >temp>=> self>.graph[i]> >while> temp:> >print>(>' ->{}'>.>format>(temp.vertex), end>=>'')> >temp>=> temp.>next> >print>(>'
'>)> # Driver program to the above graph class> if> __name__>=>=> '__main__'>:> >V>=> 5> >graph>=> Graph(V)> >graph.add_edge(>0>,>1>)> >graph.add_edge(>0>,>4>)> >graph.add_edge(>1>,>2>)> >graph.add_edge(>1>,>3>)> >graph.add_edge(>1>,>4>)> >graph.add_edge(>2>,>3>)> >graph.add_edge(>3>,>4>)> >graph.print_graph()> |
>
>Ausgabe
Adjacency list of vertex 0 head ->4 -> 1 Adjazenzliste von Scheitelpunkt 1 Kopf -> 4 -> 3 -> 2 -> 0 Adjazenzliste von Scheitelpunkt 2 Kopf -> 3 -> 1 Adjazenzliste von Scheitelpunkt 3 Kopf -> 4 -> 2 -> 1 Adjazenz Liste von Scheitelpunkt 4 Kopf -> 3 -> 1 -> 0>
Graphdurchquerung
Breitensuche oder BFS
Breitenorientierte Durchquerung für einen Graphen ähnelt die Breitendurchquerung eines Baumes. Der einzige Haken hier ist, dass Diagramme im Gegensatz zu Bäumen Zyklen enthalten können, sodass wir möglicherweise wieder zum selben Knoten gelangen. Um zu vermeiden, dass ein Knoten mehr als einmal verarbeitet wird, verwenden wir ein boolesches besuchtes Array. Der Einfachheit halber wird angenommen, dass alle Scheitelpunkte vom Startscheitelpunkt aus erreichbar sind.
Im folgenden Diagramm beginnen wir beispielsweise mit der Durchquerung von Scheitelpunkt 2. Wenn wir Scheitelpunkt 0 erreichen, suchen wir nach allen angrenzenden Scheitelpunkten. 2 ist auch ein angrenzender Scheitelpunkt von 0. Wenn wir besuchte Scheitelpunkte nicht markieren, wird 2 erneut verarbeitet und es wird zu einem nicht terminierenden Prozess. Eine Breitendurchquerung des folgenden Diagramms ist 2, 0, 3, 1.
Python3
# Python3 Program to print BFS traversal> # from a given source vertex. BFS(int s)> # traverses vertices reachable from s.> from> collections>import> defaultdict> # This class represents a directed graph> # using adjacency list representation> class> Graph:> ># Constructor> >def> __init__(>self>):> ># default dictionary to store graph> >self>.graph>=> defaultdict(>list>)> ># function to add an edge to graph> >def> addEdge(>self>,u,v):> >self>.graph[u].append(v)> ># Function to print a BFS of graph> >def> BFS(>self>, s):> ># Mark all the vertices as not visited> >visited>=> [>False>]>*> (>max>(>self>.graph)>+> 1>)> ># Create a queue for BFS> >queue>=> []> ># Mark the source node as> ># visited and enqueue it> >queue.append(s)> >visited[s]>=> True> >while> queue:> ># Dequeue a vertex from> ># queue and print it> >s>=> queue.pop(>0>)> >print> (s, end>=> ' '>)> ># Get all adjacent vertices of the> ># dequeued vertex s. If a adjacent> ># has not been visited, then mark it> ># visited and enqueue it> >for> i>in> self>.graph[s]:> >if> visited[i]>=>=> False>:> >queue.append(i)> >visited[i]>=> True> # Driver code> # Create a graph given in> # the above diagram> g>=> Graph()> g.addEdge(>0>,>1>)> g.addEdge(>0>,>2>)> g.addEdge(>1>,>2>)> g.addEdge(>2>,>0>)> g.addEdge(>2>,>3>)> g.addEdge(>3>,>3>)> print> (>'Following is Breadth First Traversal'> >' (starting from vertex 2)'>)> g.BFS(>2>)> # This code is contributed by Neelam Yadav> |
>
>Ausgabe
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Zeitkomplexität: O(V+E), wobei V die Anzahl der Eckpunkte im Diagramm und E die Anzahl der Kanten im Diagramm ist.
Tiefensuche oder DFS
Tiefendurchquerung für ein Diagramm ähnelt der Tiefendurchquerung eines Baums. Der einzige Haken hier ist, dass Diagramme im Gegensatz zu Bäumen Zyklen enthalten können und ein Knoten möglicherweise zweimal besucht wird. Um zu vermeiden, dass ein Knoten mehr als einmal verarbeitet wird, verwenden Sie ein boolesches besuchtes Array.
Algorithmus:
- Erstellen Sie eine rekursive Funktion, die den Index des Knotens und ein besuchtes Array übernimmt.
- Markieren Sie den aktuellen Knoten als besucht und drucken Sie den Knoten aus.
- Durchlaufen Sie alle benachbarten und nicht markierten Knoten und rufen Sie die rekursive Funktion mit dem Index des benachbarten Knotens auf.
Python3
# Python3 program to print DFS traversal> # from a given graph> from> collections>import> defaultdict> # This class represents a directed graph using> # adjacency list representation> class> Graph:> ># Constructor> >def> __init__(>self>):> ># default dictionary to store graph> >self>.graph>=> defaultdict(>list>)> ># function to add an edge to graph> >def> addEdge(>self>, u, v):> >self>.graph[u].append(v)> ># A function used by DFS> >def> DFSUtil(>self>, v, visited):> ># Mark the current node as visited> ># and print it> >visited.add(v)> >print>(v, end>=>' '>)> ># Recur for all the vertices> ># adjacent to this vertex> >for> neighbour>in> self>.graph[v]:> >if> neighbour>not> in> visited:> >self>.DFSUtil(neighbour, visited)> ># The function to do DFS traversal. It uses> ># recursive DFSUtil()> >def> DFS(>self>, v):> ># Create a set to store visited vertices> >visited>=> set>()> ># Call the recursive helper function> ># to print DFS traversal> >self>.DFSUtil(v, visited)> # Driver code> # Create a graph given> # in the above diagram> g>=> Graph()> g.addEdge(>0>,>1>)> g.addEdge(>0>,>2>)> g.addEdge(>1>,>2>)> g.addEdge(>2>,>0>)> g.addEdge(>2>,>3>)> g.addEdge(>3>,>3>)> print>(>'Following is DFS from (starting from vertex 2)'>)> g.DFS(>2>)> |
>
>Ausgabe
Following is DFS from (starting from vertex 2) 2 0 1 3>
Zeitkomplexität: O(V + E), wobei V die Anzahl der Eckpunkte und E die Anzahl der Kanten im Diagramm ist.