Data structuren zijn een manier om gegevens zo te organiseren dat ze, afhankelijk van de situatie, efficiënter toegankelijk zijn. Datastructuren zijn de fundamenten van elke programmeertaal waarrond een programma is gebouwd. Python helpt om de basis van deze datastructuren op een eenvoudiger manier te leren in vergelijking met andere programmeertalen.
In dit artikel bespreken we de datastructuren in de programmeertaal Python en hoe deze gerelateerd zijn aan enkele specifieke ingebouwde datastructuren zoals lijsttupels, woordenboeken, enz., evenals enkele geavanceerde datastructuren zoals bomen, grafieken, enz.
Lijsten
Python-lijsten zijn net als de arrays, gedeclareerd in andere talen, wat een geordende verzameling gegevens is. Het is zeer flexibel omdat de items in een lijst niet van hetzelfde type hoeven te zijn.
De implementatie van Python List is vergelijkbaar met vectoren in C++ of ArrayList in JAVA. De kostbare operatie is het invoegen of verwijderen van het element vanaf het begin van de lijst, omdat alle elementen moeten worden verschoven. Het invoegen en verwijderen aan het einde van de lijst kan ook kostbaar worden in het geval dat het vooraf toegewezen geheugen vol raakt.
We kunnen een lijst maken in Python, zoals hieronder weergegeven.
Voorbeeld: Python-lijst maken
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Uitvoer
[1, 2, 3, 'GFG', 2.3]>
Lijstelementen zijn toegankelijk via de toegewezen index. In de Python-startindex van de lijst is de reeks 0 en de eindindex is (als er N-elementen zijn) N-1.
Voorbeeld: Python-lijstbewerkingen
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>])> |
>
computer uitgevonden jaar
>Uitvoer
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>
Woordenboek
Python-woordenboek is als hashtabellen in elke andere taal met de tijdscomplexiteit van O(1). Het is een ongeordende verzameling gegevenswaarden, gebruikt om gegevenswaarden op te slaan als een kaart, die, in tegenstelling tot andere gegevenstypen die slechts één waarde als element bevatten, in het woordenboek het sleutel:waarde-paar bevat. Sleutelwaarde wordt in het woordenboek opgenomen om het geoptimaliseerd te maken.
Het indexeren van Python Dictionary gebeurt met behulp van sleutels. Deze zijn van elk hashbaar type, dat wil zeggen een object dat nooit kan veranderen, zoals tekenreeksen, getallen, tupels, enz. We kunnen een woordenboek maken door accolades ({}) te gebruiken of woordenboekbegrip .
Voorbeeld: Python-woordenboekbewerkingen
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)> |
>
>Uitvoer
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 is een verzameling Python-objecten die veel op een lijst lijkt, maar Tuples zijn onveranderlijk van aard, dat wil zeggen dat de elementen in de tuple niet kunnen worden toegevoegd of verwijderd nadat ze zijn gemaakt. Net als een lijst kan een Tuple ook elementen van verschillende typen bevatten.
In Python worden tupels gemaakt door een reeks waarden te plaatsen, gescheiden door ‘komma’, met of zonder het gebruik van haakjes voor het groeperen van de gegevensreeks.
Opmerking: Tupels kunnen ook met één enkel element worden gemaakt, maar dit is een beetje lastig. Het is niet voldoende om één element tussen haakjes te hebben; er moet een ‘komma’ achter staan om er een tupel van te maken.
Voorbeeld: Python Tuple-bewerkingen
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>])> |
>
>Uitvoer
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> Set
Python-set is een ongeordende verzameling gegevens die veranderlijk is en geen duplicaatelementen toestaat. Sets worden in principe gebruikt om lidmaatschapstests uit te voeren en dubbele vermeldingen te elimineren. De datastructuur die hierbij wordt gebruikt is Hashing, een populaire techniek om gemiddeld invoeging, verwijdering en traversal in O(1) uit te voeren.
Als er meerdere waarden aanwezig zijn op dezelfde indexpositie, wordt de waarde aan die indexpositie toegevoegd om een gekoppelde lijst te vormen. Hierin worden CPython-sets geïmplementeerd met behulp van een woordenboek met dummyvariabelen, waarbij sleutelwezens door de leden worden ingesteld met grotere optimalisaties van de tijdscomplexiteit.
Implementatie instellen:
Sets met talloze bewerkingen op één enkele hashtabel:
Voorbeeld: Python Set-bewerkingen
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>)> |
>
>Uitvoer
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Bevroren sets
Bevroren sets in Python zijn onveranderlijke objecten die alleen methoden en operatoren ondersteunen die een resultaat opleveren zonder de bevroren set of sets waarop ze worden toegepast te beïnvloeden. Hoewel elementen van een set op elk moment kunnen worden gewijzigd, blijven elementen van de bevroren set na het maken hetzelfde.
Als er geen parameters worden doorgegeven, retourneert het een lege frozenset.
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')> |
>
>Uitvoer
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Snaar
Python Strings zijn arrays van bytes die Unicode-tekens vertegenwoordigen. In eenvoudiger bewoordingen is een string een onveranderlijke reeks tekens. Python heeft geen tekengegevenstype, een enkel teken is eenvoudigweg een string met een lengte van 1.
Opmerking: Omdat strings onveranderlijk zijn, zal het wijzigen van een string resulteren in het maken van een nieuwe kopie.
Voorbeeld: Python Strings-bewerkingen
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>])> |
>
>Uitvoer
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray geeft een veranderlijke reeks gehele getallen in het bereik 0 <= x < 256.
Voorbeeld: Python Bytearray-bewerkingen
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)> |
>
>Uitvoer
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Tot nu toe hebben we alle datastructuren bestudeerd die in kern-Python zijn ingebouwd. Laten we nu dieper in Python duiken en de verzamelingsmodule bekijken die een aantal containers biedt die in veel gevallen nuttig zijn en meer functies bieden dan de hierboven gedefinieerde functies.
Collectiemodule
De Python-verzamelingsmodule is geïntroduceerd om de functionaliteit van de ingebouwde gegevenstypen te verbeteren. Het biedt verschillende containers, laten we ze allemaal in detail bekijken.
Tellers
Een teller is een subklasse van het woordenboek. Het wordt gebruikt om het aantal elementen in een iterabele bij te houden in de vorm van een ongeordend woordenboek waarbij de sleutel het element in de iterabele vertegenwoordigt en de waarde het aantal van dat element in de iterabele vertegenwoordigt. Dit komt overeen met een tas of een multiset van andere talen.
Voorbeeld: Python-tellerbewerkingen
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)> |
>
>Uitvoer
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> BesteldDict
Een BesteldDict is ook een subklasse van een woordenboek, maar in tegenstelling tot een woordenboek onthoudt het de volgorde waarin de sleutels zijn ingevoegd.
Voorbeeld: Python OrderedDict-bewerkingen
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)> |
>
>Uitvoer
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>
Standaarddict
Standaarddict wordt gebruikt om enkele standaardwaarden op te geven voor de sleutel die niet bestaat en geeft nooit een KeyError. De objecten kunnen worden geïnitialiseerd met behulp van de DefaultDict()-methode door het gegevenstype als argument door te geven.
Opmerking: default_factory is een functie die de standaardwaarde levert voor het gemaakte woordenboek. Als deze parameter ontbreekt, wordt de KeyError gegenereerd.
Voorbeeld: Python DefaultDict-bewerkingen
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)> |
>
>Uitvoer
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> Ketenkaart
Een ChainMap vat vele woordenboeken samen in één enkele eenheid en retourneert een lijst met woordenboeken. Wanneer er een sleutel moet worden gevonden, worden alle woordenboeken één voor één doorzocht totdat de sleutel is gevonden.
Voorbeeld: Python ChainMap-bewerkingen
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'>])> |
>
>
Uitvoer
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
GenoemdTupel
A GenoemdTuple retourneert een tuple-object met namen voor elke positie die de gewone tupels missen. Beschouw bijvoorbeeld een tuple genaamd student waarbij het eerste element fname vertegenwoordigt, het tweede lname en het derde element de DOB vertegenwoordigt. Stel dat je voor het aanroepen van fname in plaats van het onthouden van de indexpositie het element daadwerkelijk kunt aanroepen met behulp van het fname-argument, dan is het heel gemakkelijk om toegang te krijgen tot het tuples-element. Deze functionaliteit wordt geleverd door NamedTuple.
Voorbeeld: Python NamedTuple-bewerkingen
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)> |
>
>Uitvoer
The Student age using index is : 19 The Student name using keyname is : Nandini>
Over wat
Deque (dubbel beëindigde wachtrij) is de geoptimaliseerde lijst voor snellere toevoeg- en pop-bewerkingen vanaf beide zijden van de container. Het biedt O(1) tijdscomplexiteit voor append- en pop-bewerkingen in vergelijking met de lijst met O(n) tijdscomplexiteit.
Python Deque wordt geïmplementeerd met behulp van dubbel gekoppelde lijsten, daarom zijn de prestaties voor willekeurige toegang tot de elementen O(n).
Voorbeeld: Python Deque-bewerkingen
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)> |
jdbc jdbc
>
>Uitvoer
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])>
GebruikerDict
UserDict is een woordenboekachtige container die fungeert als omhulsel rond de woordenboekobjecten. Deze container wordt gebruikt wanneer iemand zijn eigen woordenboek wil maken met een aangepaste of nieuwe functionaliteit.
Voorbeeld: 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>)> |
>
>
Uitvoer
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Gebruikers lijst
UserList is een lijstachtige container die fungeert als omhulsel rond de lijstobjecten. Dit is handig als iemand zijn eigen lijst wil maken met wat aangepaste of extra functionaliteit.
Voorbeelden: Python-gebruikerslijst
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()> |
>
>
Uitvoer
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
Gebruikersreeks
UserString is een stringachtige container en fungeert net als UserDict en UserList als een wrapper rond stringobjecten. Het wordt gebruikt wanneer iemand zijn eigen strings wil maken met een aangepaste of extra functionaliteit.
Voorbeeld: 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)> |
>
>Uitvoer
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Laten we nu, na het bestuderen van alle datastructuren, enkele geavanceerde datastructuren bekijken, zoals stapel, wachtrij, grafiek, gekoppelde lijst, enz. die kunnen worden gebruikt in Python Language.
Gekoppelde lijst
Een gekoppelde lijst is een lineaire datastructuur, waarbij de elementen niet op aangrenzende geheugenlocaties zijn opgeslagen. De elementen in een gekoppelde lijst zijn gekoppeld met behulp van verwijzingen, zoals weergegeven in de onderstaande afbeelding:
Een gekoppelde lijst wordt weergegeven door een verwijzing naar het eerste knooppunt van de gekoppelde lijst. Het eerste knooppunt wordt het hoofd genoemd. Als de gekoppelde lijst leeg is, is de waarde van het hoofd NULL. Elk knooppunt in een lijst bestaat uit minimaal twee delen:
- Gegevens
- Wijzer (of referentie) naar het volgende knooppunt
Voorbeeld: gekoppelde lijst definiëren 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> |
>
>
Laten we een eenvoudige gekoppelde lijst maken met 3 knooppunten.
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 | nul | | 3 | nul |> >+----+------+ +----+------+ +----+------+> >'''> >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 | nul |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Gekoppelde lijstdoorgang
In het vorige programma hebben we een eenvoudige gekoppelde lijst met drie knooppunten gemaakt. Laten we de gemaakte lijst doorkruisen en de gegevens van elk knooppunt afdrukken. Laten we voor het doorlopen een algemene functie printList() schrijven die een bepaalde lijst afdrukt.
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()> |
>
>Uitvoer
1 2 3>
Stapel
A stapel is een lineaire datastructuur die items opslaat op een Last-In/First-Out (LIFO) of First-In/Last-Out (FILO) manier. Bij stapelen wordt aan één uiteinde een nieuw element toegevoegd en alleen aan dat uiteinde wordt een element verwijderd. De invoeg- en verwijderbewerkingen worden vaak push en pop genoemd.
De functies die verband houden met stapelen zijn:
- empty() – Geeft terug of de stapel leeg is – Tijdscomplexiteit: O(1) size() – Geeft de grootte van de stapel terug – Tijdscomplexiteit: O(1) top() – Geeft een verwijzing naar het bovenste element van de stapel terug – Tijdcomplexiteit: O(1) push(a) – Voegt het element 'a' bovenaan de stapel in – Tijdcomplexiteit: O(1) pop() – Verwijdert het bovenste element van de stapel – Tijdcomplexiteit: O( 1)
Implementatie van Python Stack
Stack in Python kan op de volgende manieren worden geïmplementeerd:
- lijst
- Collecties.deque
- wachtrij.LifoQueue
Implementatie met behulp van Lijst
De ingebouwde datastructuurlijst van Python kan als stapel worden gebruikt. In plaats van push() wordt append() gebruikt om elementen bovenaan de stapel toe te voegen, terwijl pop() het element in LIFO-volgorde verwijdert.
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> |
>
>Uitvoer
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementatie met collections.deque:
Python-stack kan worden geïmplementeerd met behulp van de deque-klasse uit de collectiemodule. Deque heeft de voorkeur boven de lijst in de gevallen waarin we snellere append- en pop-bewerkingen nodig hebben vanaf beide uiteinden van de container, omdat deque een O(1) tijdscomplexiteit biedt voor append- en pop-bewerkingen in vergelijking met list die O(n) biedt. tijd complexiteit.
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> |
>
>Uitvoer
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementatie met behulp van wachtrijmodule
De wachtrijmodule heeft ook een LIFO-wachtrij, die in feite een stapel is. Gegevens worden in de wachtrij ingevoegd met behulp van de functie put() en get() haalt gegevens uit de wachtrij.
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())> |
>
>Uitvoer
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Wachtrij
Als stapel wordt de wachtrij is een lineaire datastructuur waarin items op een First In First Out (FIFO) manier worden opgeslagen. Bij een wachtrij wordt het minst recent toegevoegde item als eerste verwijderd. Een goed voorbeeld van de wachtrij is elke wachtrij van consumenten voor een hulpbron waarbij de consument die als eerste kwam, als eerste wordt bediend.
Bewerkingen die aan de wachtrij zijn gekoppeld, zijn:
- Enqueue: Voegt een item toe aan de wachtrij. Als de wachtrij vol is, wordt er gesproken van een Overflow-conditie. Tijdcomplexiteit: O(1) Dequeue: verwijdert een item uit de wachtrij. De items worden in dezelfde volgorde geplaatst als waarin ze zijn geduwd. Als de wachtrij leeg is, wordt er gesproken van een Underflow-conditie – Tijdcomplexiteit: O(1) Voorkant: Haal het voorste item uit de wachtrij – Tijdcomplexiteit: O(1) Achterkant: Haal het laatste item uit de wachtrij – Tijdcomplexiteit : O(1)
Implementatie van Python-wachtrij
Wachtrij in Python kan op de volgende manieren worden geïmplementeerd:
- lijst
- collecties.deque
- staart.staart
Implementatie met behulp van lijst
In plaats van enqueue() en dequeue(), worden de functies append() en pop() gebruikt.
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> |
>
>Uitvoer
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementatie met behulp van collections.deque
Deque heeft de voorkeur boven de lijst in de gevallen waarin we snellere append- en pop-bewerkingen nodig hebben vanaf beide uiteinden van de container, omdat deque een O(1) tijdscomplexiteit biedt voor append- en pop-bewerkingen in vergelijking met list die O(n) biedt. tijd complexiteit.
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> |
>
>Uitvoer
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementatie met behulp van de wachtrij.Queue
werkbalk voor snelle toegang tot woorden
wachtrij.Queue(maxsize) initialiseert een variabele tot een maximale grootte van maxsize. Een maximale grootte van nul ‘0’ betekent een oneindige wachtrij. Deze wachtrij volgt de 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())> |
>
>Uitvoer
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Prioriteits-rij
Prioritaire wachtrijen zijn abstracte datastructuren waarbij elke data/waarde in de wachtrij een bepaalde prioriteit heeft. Bij luchtvaartmaatschappijen arriveert bagage met de titel Business of First Class bijvoorbeeld eerder dan de rest. Prioriteitswachtrij is een uitbreiding van de wachtrij met de volgende eigenschappen.
- Een element met hoge prioriteit wordt uit de wachtrij gehaald vóór een element met lage prioriteit.
- Als twee elementen dezelfde prioriteit hebben, worden ze geserveerd volgens hun volgorde in de wachtrij.
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())> |
>
>Uitvoer
12 1 14 7 14 12 7 1>
Heap-wachtrij (of heapq)
heapq-module in Python biedt de heap-gegevensstructuur die voornamelijk wordt gebruikt om een prioriteitswachtrij weer te geven. De eigenschap van deze datastructuur in Python is dat elke keer het kleinste heap-element wordt gepopt (min-heap). Telkens wanneer elementen worden geduwd of gepoft, blijft de heap-structuur behouden. Het element heap[0] retourneert ook elke keer het kleinste element.
Het ondersteunt de extractie en invoeging van het kleinste element in de O(log n) tijden.
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))> |
>
>Uitvoer
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>
Binaire boom
Een boom is een hiërarchische gegevensstructuur die eruitziet als de onderstaande afbeelding:
tree ---- j <-- root / f k / a h z <-- leaves>
Het bovenste knooppunt van de boom wordt de wortel genoemd, terwijl de onderste knooppunten of de knooppunten zonder kinderen de bladknooppunten worden genoemd. De knooppunten die zich direct onder een knooppunt bevinden, worden de onderliggende knooppunten genoemd, en de knooppunten die zich direct boven iets bevinden, worden de ouder genoemd.
Een binaire boom is een boom waarvan de elementen bijna twee kinderen kunnen hebben. Omdat elk element in een binaire boom slechts twee kinderen kan hebben, noemen we ze doorgaans de linker- en rechterkinderen. Een binaire boomknooppunt bevat de volgende onderdelen.
- Gegevens
- Wijzer naar het linkerkind
- Wijzer naar het juiste kind
Voorbeeld: knooppuntklasse definiëren
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> |
>
>
Laten we nu een boom maken met 4 knooppunten in Python. Laten we aannemen dat de boomstructuur er als volgt uitziet:
tree ---- 1 <-- root / 2 3 / 4>
Voorbeeld: gegevens aan de boom toevoegen
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'''> |
>
>
Boomdoortocht
Bomen kunnen worden doorkruist op verschillende manieren. Hieronder volgen de algemeen gebruikte manieren om bomen te doorkruisen. Laten we de onderstaande boom bekijken -
tree ---- 1 <-- root / 2 3 / 4 5>
Diepte Eerste Traversals:
- In volgorde (links, wortel, rechts): 4 2 5 1 3
- Voorbestelling (Root, Links, Rechts): 1 2 4 5 3
- Postorder (links, rechts, root): 4 5 2 3 1
Algoritme in volgorde(boom)
- Doorloop de linker deelboom, d.w.z. roep Inorder(linker-subboom) aan
- Bezoek de wortel.
- Doorloop de rechter deelboom, d.w.z. roep Inorder(rechter-subboom) aan
Algoritme vooraf bestellen(boom)
- Bezoek de wortel.
- Doorloop de linker subboom, d.w.z. roep Preorder(linker-subboom) aan
- Doorloop de rechter subboom, d.w.z. roep Preorder(rechter-subboom) aan
Algoritme Postwissel(boom)
- Doorloop de linker subboom, d.w.z. roep Postorder(linker-subboom) aan
- Doorloop de rechter subboom, d.w.z. roep Postorder(rechter-subboom) aan
- Bezoek de wortel.
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)> |
>
>Uitvoer
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>
Tijdcomplexiteit – O(n)
Breedte-eerste of niveau-ordertransactie
Niveauvolgorde doorlopen van een boom is de breedte-eerste doorgang voor de boom. De niveauvolgorde van de bovenstaande boom is 1 2 3 4 5.
Voor elk knooppunt wordt het knooppunt eerst bezocht en vervolgens worden de onderliggende knooppunten in een FIFO-wachtrij geplaatst. Hieronder staat het algoritme voor hetzelfde -
- Maak een lege wachtrij q
- temp_node = root /*start vanaf root*/
- Loop terwijl temp_node niet NULL is
- print temp_node->gegevens.
- Plaats de kinderen van temp_node (eerst links en dan rechts) in de wachtrij voor q
- Haal een knooppunt uit q uit de wachtrij
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)> |
>
>Uitvoer
Level Order Traversal of binary tree is - 1 2 3 4 5>
Tijdcomplexiteit: O(n)
Grafiek
A grafiek is een niet-lineaire datastructuur bestaande uit knooppunten en randen. De knooppunten worden ook wel hoekpunten genoemd en de randen zijn lijnen of bogen die twee willekeurige knooppunten in de grafiek met elkaar verbinden. Formeel kan een grafiek worden gedefinieerd als een grafiek die bestaat uit een eindige reeks hoekpunten (of knooppunten) en een reeks randen die een paar knooppunten verbinden.
In de bovenstaande grafiek is de set hoekpunten V = {0,1,2,3,4} en de set randen E = {01, 12, 23, 34, 04, 14, 13}.
De volgende twee zijn de meest gebruikte weergaven van een grafiek.
- Nabijheidsmatrix
- Nabijheidslijst
Nabijheidsmatrix
Aangrenzende matrix is een 2D-array met de grootte V x V, waarbij V het aantal hoekpunten in een grafiek is. Stel dat de 2D-array adj[][] is, een slot adj[i][j] = 1 geeft aan dat er een rand is van hoekpunt i naar hoekpunt j. De aangrenzende matrix voor een ongerichte grafiek is altijd symmetrisch. Aangrenzende matrix wordt ook gebruikt om gewogen grafieken weer te geven. Als adj[i][j] = w, dan is er een rand van hoekpunt i naar hoekpunt j met 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())> |
>
>
Uitvoer
Hoekpunten van grafiek
[‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’]
Randen van grafiek
[('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)]
Nabijheidsmatrix van grafiek
[[-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]]
Nabijheidslijst
Er wordt gebruik gemaakt van een array van lijsten. De grootte van de array is gelijk aan het aantal hoekpunten. Laat de array een array[] zijn. Een entry-array[i] vertegenwoordigt de lijst met hoekpunten grenzend aan het i-de hoekpunt. Deze weergave kan ook worden gebruikt om een gewogen grafiek weer te geven. De gewichten van randen kunnen worden weergegeven als lijsten van paren. Hieronder volgt de weergave van de aangrenzende lijst van de bovenstaande grafiek.
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()> |
>
>Uitvoer
Adjacency list of vertex 0 head ->4 -> 1 Aangrenzende lijst van hoekpunt 1 hoofd -> 4 -> 3 -> 2 -> 0 Aangrenzende lijst van hoekpunt 2 hoofd -> 3 -> 1 Aangrenzende lijst van hoekpunt 3 hoofd -> 4 -> 2 -> 1 Aangrenzende lijst lijst van hoekpunt 4 hoofd -> 3 -> 1 -> 0>
Grafiek Traversal
Breedte-eerst zoeken of BFS
Breedte-eerste doorgang want een grafiek is vergelijkbaar met de breedte-eerste doorgang van een boom. Het enige probleem hier is dat grafieken, in tegenstelling tot bomen, cycli kunnen bevatten, waardoor we mogelijk weer op hetzelfde knooppunt terechtkomen. Om te voorkomen dat een knooppunt meerdere keren wordt verwerkt, gebruiken we een Booleaanse bezochte array. Voor de eenvoud wordt aangenomen dat alle hoekpunten bereikbaar zijn vanaf het startpunt.
In de volgende grafiek beginnen we bijvoorbeeld met het doorlopen van hoekpunt 2. Wanneer we bij hoekpunt 0 komen, zoeken we naar alle aangrenzende hoekpunten ervan. 2 is ook een aangrenzend hoekpunt van 0. Als we de bezochte hoekpunten niet markeren, wordt 2 opnieuw verwerkt en wordt het een niet-beëindigend proces. Een breedte-eerste doorgang van de volgende grafiek is 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> |
>
>Uitvoer
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Tijdcomplexiteit: O(V+E) waarbij V het aantal hoekpunten in de grafiek is en E het aantal randen in de grafiek.
Diepte eerst zoeken of DFS
Diepte Eerste Traversal voor een grafiek is vergelijkbaar met Diepte Eerste Traversal van een boom. Het enige probleem hier is dat grafieken, in tegenstelling tot bomen, cycli kunnen bevatten en dat een knooppunt twee keer kan worden bezocht. Om te voorkomen dat een knooppunt meerdere keren wordt verwerkt, gebruikt u een Booleaanse bezochte array.
Algoritme:
- Maak een recursieve functie die de index van het knooppunt en een bezochte array overneemt.
- Markeer het huidige knooppunt als bezocht en druk het knooppunt af.
- Doorloop alle aangrenzende en ongemarkeerde knooppunten en roep de recursieve functie aan met de index van het aangrenzende knooppunt.
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>)> |
>
>Uitvoer
Following is DFS from (starting from vertex 2) 2 0 1 3>
Tijdcomplexiteit: O(V + E), waarbij V het aantal hoekpunten is en E het aantal randen in de grafiek.