Datastrukturer er en måte å organisere data på slik at de kan nås mer effektivt avhengig av situasjonen. Datastrukturer er grunnleggende for ethvert programmeringsspråk som et program er bygget rundt. Python hjelper til med å lære det grunnleggende i disse datastrukturene på en enklere måte sammenlignet med andre programmeringsspråk.

I denne artikkelen vil vi diskutere datastrukturene i Python-programmeringsspråket og hvordan de er relatert til noen spesifikke innebygde datastrukturer som listetupler, ordbøker osv. samt noen avanserte datastrukturer som trær, grafer osv.

Lister

Python-lister er akkurat som arrayene, deklarert på andre språk som er en ordnet samling av data. Det er veldig fleksibelt da elementene i en liste ikke trenger å være av samme type.

Implementeringen av Python List ligner Vectors i C++ eller ArrayList i JAVA. Den kostbare operasjonen er å sette inn eller slette elementet fra begynnelsen av listen ettersom alle elementene må flyttes. Innsetting og sletting på slutten av listen kan også bli kostbart i tilfelle det forhåndstildelte minnet blir fullt.

Vi kan lage en liste i python som vist nedenfor.

Eksempel: Opprette Python List

Python3

List> => [> 1> ,> 2> ,> 3> ,> 'GFG'> ,> 2.3> ]> print> (> List> )>

Produksjon

[1, 2, 3, 'GFG', 2.3] 

Listeelementer kan nås av den tilordnede indeksen. I python-startindeksen på listen er sekvensen 0 og sluttindeksen er (hvis N elementer er der) N-1.

Eksempel: Python List Operations

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> ])>

Produksjon

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 

Ordbok

Python-ordbok er som hashtabeller på et hvilket som helst annet språk med tidskompleksiteten til O(1). Det er en uordnet samling av dataverdier, som brukes til å lagre dataverdier som et kart, som, i motsetning til andre datatyper som bare har en enkelt verdi som et element, inneholder Dictionary nøkkel:verdi-paret. Nøkkelverdi er gitt i ordboken for å gjøre den mer optimalisert.

Indeksering av Python Dictionary gjøres ved hjelp av taster. Disse er av en hvilken som helst hashbar type, dvs. et objekt som aldri kan endres som strenger, tall, tupler osv. Vi kan lage en ordbok ved å bruke krøllete klammeparenteser ({}) eller ordbokforståelse .

Eksempel: Python Dictionary Operations

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)>

Produksjon

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} 

Tuppel

Python Tuple er en samling av Python-objekter omtrent som en liste, men Tuples er uforanderlige i naturen, dvs. elementene i tupleen kan ikke legges til eller fjernes når de først er opprettet. Akkurat som en liste, kan en Tuple også inneholde elementer av ulike typer.

I Python lages tupler ved å plassere en sekvens av verdier atskilt med 'komma' med eller uten bruk av parenteser for gruppering av datasekvensen.

Merk: Tuples kan også lages med et enkelt element, men det er litt vanskelig. Å ha ett element i parentes er ikke tilstrekkelig, det må være et etterfølgende 'komma' for å gjøre det til en tuppel.

Eksempel: Python Tuple Operations

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> ])>

Produksjon

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 

Sett

Python-sett er en uordnet samling av data som kan endres og ikke tillater duplikatelementer. Sett brukes i utgangspunktet til å inkludere medlemskapstesting og eliminere dupliserte oppføringer. Datastrukturen som brukes i dette er Hashing, en populær teknikk for å utføre innsetting, sletting og kryssing i O(1) i gjennomsnitt.

Hvis flere verdier er tilstede på samme indeksposisjon, blir verdien lagt til den indeksposisjonen for å danne en koblet liste. I, er CPython-sett implementert ved hjelp av en ordbok med dummy-variabler, hvor nøkkelvesener medlemmene setter med større optimaliseringer av tidskompleksiteten.

Sett implementering:

Sett med mange operasjoner på en enkelt hashtabell:

Eksempel: Python-settoperasjoner

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> )>

Produksjon

Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True 

Frosne sett

Frosne sett i Python er uforanderlige objekter som bare støtter metoder og operatører som produserer et resultat uten å påvirke det eller de frosne settene de brukes på. Mens elementer i et sett kan endres når som helst, forblir elementene i det frosne settet de samme etter opprettelsen.

Hvis ingen parametere sendes, returnerer den et tomt frossensett.

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')>

Produksjon

Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'}) 

String

Python-strenger er arrays av byte som representerer Unicode-tegn. I enklere termer er en streng en uforanderlig rekke tegn. Python har ikke en tegndatatype, et enkelt tegn er ganske enkelt en streng med lengden 1.

Merk: Siden strenger er uforanderlige, vil endring av en streng resultere i å lage en ny kopi.

Eksempel: Python-strengoperasjoner

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> ])>

Produksjon

Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s 

Bytearray

Python Bytearray gir en foranderlig sekvens av heltall i området 0 <= x < 256.

Eksempel: Python Bytearray-operasjoner

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)>

Produksjon

Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e') 

Til nå har vi studert alle datastrukturene som er innebygd i kjernen Python. La nå dykke mer inn i Python og se samlingsmodulen som gir noen beholdere som er nyttige i mange tilfeller og gir flere funksjoner enn de ovenfor definerte funksjonene.

Samlingsmodul

Python-samlingsmodulen ble introdusert for å forbedre funksjonaliteten til de innebygde datatypene. Det gir forskjellige beholdere, la oss se hver enkelt av dem i detalj.

Tellere

En teller er en underklasse av ordboken. Den brukes til å holde tellingen av elementene i en iterabel i form av en uordnet ordbok der nøkkelen representerer elementet i den iterable og verdien representerer tellingen av det elementet i den iterable. Dette tilsvarer en pose eller multisett med andre språk.

Eksempel: Python-telleroperasjoner

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)>

Produksjon

Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1}) 

BestiltDict

An BestiltDict er også en underklasse av ordbok, men i motsetning til en ordbok, husker den rekkefølgen nøklene ble satt inn.

Eksempel: Python OrderedDict-operasjoner

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)>

Produksjon

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 brukes til å gi noen standardverdier for nøkkelen som ikke eksisterer og aldri gir en KeyError. Objektene kan initialiseres ved å bruke DefaultDict()-metoden ved å sende datatypen som et argument.

Merk: default_factory er en funksjon som gir standardverdien for den opprettede ordboken. Hvis denne parameteren er fraværende, økes KeyError.

Eksempel: Python DefaultDict-operasjoner

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)>

Produksjon

defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2}) 

Kjedekart

Et kjedekart kapsler inn mange ordbøker i en enkelt enhet og returnerer en liste med ordbøker. Når en nøkkel er nødvendig for å bli funnet, søkes alle ordbøkene en etter en til nøkkelen er funnet.

Eksempel: Python ChainMap Operations

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'> ])>

Produksjon

ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1 

KeyError: 'g' 

Oppkalt Tuple

EN Oppkalt Tuple returnerer et tuppelobjekt med navn for hver posisjon som de vanlige tuplene mangler. Tenk for eksempel på en tuppelnavn elev der det første elementet representerer fname, det andre representerer lname og det tredje elementet representerer DOB. Anta at for å kalle fname i stedet for å huske indeksposisjonen kan du faktisk kalle elementet ved å bruke fname-argumentet, da vil det være veldig enkelt å få tilgang til tuples-elementet. Denne funksjonaliteten leveres av NamedTuple.

Eksempel: Python NamedTuple-operasjoner

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)>

Produksjon

The Student age using index is : 19 The Student name using keyname is : Nandini 

Om hva

Deque (dobbelt avsluttet kø) er den optimaliserte listen for raskere tilføy- og pop-operasjoner fra begge sider av beholderen. Den gir O(1)-tidskompleksitet for append- og popoperasjoner sammenlignet med listen med O(n)-tidskompleksitet.

Python Deque er implementert ved å bruke dobbeltkoblede lister, derfor er ytelsen for tilfeldig tilgang til elementene O(n).

Eksempel: Python Deque-operasjoner

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)>

Produksjon

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 er en ordboklignende beholder som fungerer som en innpakning rundt ordbokobjektene. Denne beholderen brukes når noen ønsker å lage sin egen ordbok med en eller annen modifisert eller ny funksjonalitet.

Eksempel: 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> )>

Produksjon

Original Dictionary {'a': 1, 'b': 2, 'c': 3} 

RuntimeError: Deletion not allowed 

Brukerliste

UserList er en listelignende beholder som fungerer som en innpakning rundt listeobjektene. Dette er nyttig når noen ønsker å lage sin egen liste med en modifisert eller tilleggsfunksjonalitet.

Eksempler: Python UserList

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()>

Produksjon

Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5] 

RuntimeError: Deletion not allowed 

UserString

UserString er en strenglignende beholder, og akkurat som UserDict og UserList fungerer den som en innpakning rundt strengobjekter. Den brukes når noen ønsker å lage sine egne strenger med noen modifisert eller tilleggsfunksjonalitet.

Eksempel: 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)>

Produksjon

Original String: Geeks String After Appending: Geekss String after Removing: Gkss 

La oss nå, etter å ha studert alle datastrukturene, se noen avanserte datastrukturer som stack, kø, graf, koblet liste, etc. som kan brukes i Python Language.

Koblet liste

En koblet liste er en lineær datastruktur, der elementene ikke er lagret på sammenhengende minneplasseringer. Elementene i en koblet liste er koblet ved hjelp av pekere som vist i bildet nedenfor:

En koblet liste er representert med en peker til den første noden i den koblede listen. Den første noden kalles hodet. Hvis den koblede listen er tom, er verdien på hodet NULL. Hver node i en liste består av minst to deler:

• Data
• Peker (eller referanse) til neste node

Eksempel: Definere lenket liste i 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>

La oss lage en enkel koblet liste med 3 noder.

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 |> > +----+------+ +----+------+ +----+------+> > '''>

Linked List Traversal

I forrige program har vi laget en enkel lenket liste med tre noder. La oss krysse den opprettede listen og skrive ut dataene til hver node. For gjennomgang, la oss skrive en generell funksjon printList() som skriver ut en gitt liste.

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()>

Produksjon

1 2 3 

Stable

EN stable er en lineær datastruktur som lagrer elementer på en Last-In/First-Out (LIFO) eller First-In/Last-Out (FILO) måte. I stabel legges et nytt element til i den ene enden, og et element fjernes bare fra den enden. Sett inn og slett-operasjoner kalles ofte push og pop.

Funksjonene knyttet til stack er:

empty() – Returnerer om stabelen er tom – Tidskompleksitet: O(1) size() – Returnerer størrelsen på stabelen – Tidskompleksitet: O(1) top() – Returnerer en referanse til det øverste elementet i stabelen – Tidskompleksitet: O(1) push(a) – Setter inn elementet 'a' på toppen av stabelen – Tidskompleksitet: O(1) pop() – Sletter det øverste elementet i stabelen – Tidskompleksitet: O( 1)

Python Stack Implementering

Stack i Python kan implementeres på følgende måter:

• liste
• Collections.deque
• queue.LifoQueue

Implementering ved hjelp av List

Pythons innebygde datastrukturliste kan brukes som en stabel. I stedet for push(), brukes append() til å legge til elementer på toppen av stabelen mens pop() fjerner elementet i LIFO-rekkefølge.

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>

Produksjon

Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: [] 

Implementering ved hjelp av collections.deque:

Python-stack kan implementeres ved å bruke deque-klassen fra samlingsmodulen. Deque foretrekkes fremfor listen i tilfeller der vi trenger raskere append- og pop-operasjoner fra begge ender av beholderen, da deque gir en O(1)-tidskompleksitet for append- og pop-operasjoner sammenlignet med liste som gir O(n) tidskompleksitet.

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>

Produksjon

Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([]) 

Implementering ved bruk av kømodul

Kømodulen har også en LIFO Queue, som i utgangspunktet er en Stack. Data settes inn i køen ved å bruke put()-funksjonen og get() tar data ut fra køen.

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())>

Produksjon

0 Full: True Size: 3 Elements popped from the stack g f g Empty: True 

Kø

Som en stabel kø er en lineær datastruktur som lagrer elementer på en First In First Out (FIFO) måte. Med en kø fjernes det elementet som sist ble lagt til først. Et godt eksempel på køen er en hvilken som helst kø av forbrukere for en ressurs der forbrukeren som kom først blir servert først.

Operasjoner knyttet til køen er:

Enqueue: Legger til et element i køen. Hvis køen er full, sies det å være en overløpstilstand – Tidskompleksitet: O(1) Dekø: Fjerner et element fra køen. Elementene er poppet i samme rekkefølge som de skyves. Hvis køen er tom, sies det å være en underflyt-tilstand – Tidskompleksitet: O(1) Foran: Hent det fremre elementet fra køen – Tidskompleksitet: O(1) Bak: Hent det siste elementet fra køen – Tidskompleksitet : O(1)

Implementering av Python-kø

Kø i Python kan implementeres på følgende måter:

• liste
• samlinger.deque
• hale.hale

Implementering ved hjelp av liste

I stedet for enqueue() og dequeue(), brukes funksjonen append() og pop().

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>

Produksjon

Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements [] 

Implementering ved hjelp av collections.deque

Deque foretrekkes fremfor listen i tilfeller der vi trenger raskere append- og pop-operasjoner fra begge ender av beholderen, da deque gir en O(1)-tidskompleksitet for append- og pop-operasjoner sammenlignet med liste som gir O(n) tidskompleksitet.

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>

Produksjon

Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([]) 

Implementering ved hjelp av køen.Kø

queue.Queue(maxsize) initialiserer en variabel til en maksimal størrelse på maxsize. En maksimal størrelse på null '0' betyr en uendelig kø. Denne køen følger FIFO-regelen.

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())>

Produksjon

0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False 

Prioritetskø

Prioriterte køer er abstrakte datastrukturer hvor hver data/verdi i køen har en viss prioritet. For eksempel hos flyselskaper kommer bagasje med tittelen Business eller First-class tidligere enn resten. Priority Queue er en utvidelse av køen med følgende egenskaper.

• Et element med høy prioritet settes ut av kø før et element med lav prioritet.
• Hvis to elementer har samme prioritet, serveres de i henhold til rekkefølgen i køen.

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())>

Produksjon

12 1 14 7 14 12 7 1 

Heap-kø (eller heapq)

heapq-modul i Python gir haugdatastrukturen som hovedsakelig brukes til å representere en prioritert kø. Egenskapen til denne datastrukturen i Python er at hver gang det minste heap-elementet poppes (min-heap). Hver gang elementer skyves eller poppes, opprettholdes haugstrukturen. Heap[0]-elementet returnerer også det minste elementet hver gang.

Den støtter utvinning og innsetting av det minste elementet i O(log n) ganger.

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))>

Produksjon

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ært tre

Et tre er en hierarkisk datastruktur som ser ut som figuren nedenfor -

 tree ---- j  <-- root /  f k /   a h z  <-- leaves 

Den øverste noden av treet kalles roten, mens de nederste nodene eller nodene uten barn kalles bladnodene. Nodene som er rett under en node kalles dens barn og nodene som er rett over noe kalles dens overordnede.

Et binært tre er et tre hvis elementer kan ha nesten to barn. Siden hvert element i et binært tre bare kan ha 2 barn, kaller vi dem vanligvis venstre og høyre barn. En binær tre-node inneholder følgende deler.

• Data
• Peker til venstre barn
• Peker til rett barn

Eksempel: Definere nodeklasse

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>

La oss nå lage et tre med 4 noder i Python. La oss anta at trestrukturen ser ut som nedenfor -

 tree ---- 1  <-- root /  2 3 / 4 

Eksempel: Legge til data i treet

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'''>

Traversering av tre

Trær kan krysses på forskjellige måter. Følgende er de generelt brukte måtene å krysse trær på. La oss vurdere treet nedenfor -

 tree ---- 1  <-- root /  2 3 /  4 5 

Depth First Traversals:

• I rekkefølge (venstre, rot, høyre): 4 2 5 1 3
• Forhåndsbestilling (Root, Venstre, Høyre): 1 2 4 5 3
• Postordre (venstre, høyre, rot): 4 5 2 3 1

Algoritme rekkefølge (tre)

• Gå gjennom venstre undertre, dvs. ring Inorder (venstre-undertre)
• Besøk roten.
• Gå gjennom høyre undertre, dvs. ring Inorder (høyre undertre)

Algoritme forhåndsbestilling (tre)

• Besøk roten.
• Gå gjennom venstre undertre, dvs. ring Preorder (venstre-undertre)
• Gå gjennom høyre undertre, dvs. ring Preorder (høyre undertre)

Algoritme Postordre (tre)

• Gå gjennom venstre undertre, dvs. ring Postorder (venstre-undertre)
• Gå gjennom høyre undertre, dvs. ring Postorder (høyre undertre)
• Besøk roten.

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)>

Produksjon

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 

Tidskompleksitet – O(n)

Breadth-First eller Level Order Traversal

Nivåordregjennomgang av et tre er bredde-første kryssing for treet. Nivårekkefølgen for treet ovenfor er 1 2 3 4 5.

For hver node besøkes først noden, og deretter settes dens underordnede noder i en FIFO-kø. Nedenfor er algoritmen for det samme –

• Opprett en tom kø q
• temp_node = rot /*start fra rot*/
• Loop mens temp_node ikke er NULL
  • skriv ut temp_node->data.
  • Sett temp_nodes barn i kø (først venstre og deretter høyre barn) til q
  • Sett en node i kø fra 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)>

Produksjon

Level Order Traversal of binary tree is - 1 2 3 4 5 

Tidskompleksitet: O(n)

Kurve

EN kurve er en ikke-lineær datastruktur som består av noder og kanter. Nodene blir noen ganger også referert til som toppunkter, og kantene er linjer eller buer som forbinder hvilke som helst to noder i grafen. Mer formelt kan en graf defineres som en graf som består av et begrenset sett med toppunkter (eller noder) og et sett med kanter som forbinder et par noder.

I grafen ovenfor er settet med toppunkter V = {0,1,2,3,4} og settet med kanter E = {01, 12, 23, 34, 04, 14, 13}.

De følgende to er de mest brukte representasjonene av en graf.

• Adjacency Matrix
• Tilknytningsliste

Adjacency Matrix

Adjacency Matrix er en 2D-array av størrelse V x V der V er antall toppunkter i en graf. La 2D-matrisen være adj[][], et spor adj[i][j] = 1 indikerer at det er en kant fra toppunkt i til toppunkt j. Nærhetsmatrisen for en urettet graf er alltid symmetrisk. Adjacency Matrix brukes også til å representere vektede grafer. Hvis adj[i][j] = w, så er det en kant fra toppunkt i til toppunkt j med vekt 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())>

Produksjon

Toppunktene til grafen

['A B C D E F']

Kanter av graf

[('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)]

Adjacency Matrix of Graph

[[-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]]

Tilknytningsliste

En rekke lister brukes. Størrelsen på matrisen er lik antall toppunkter. La matrisen være en matrise[]. En inngangsmatrise[i] representerer listen over toppunkter ved siden av det ite toppunktet. Denne representasjonen kan også brukes til å representere en vektet graf. Vektene til kanter kan representeres som lister over par. Følgende er tilstøtende listerepresentasjon av grafen ovenfor.

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()>

Produksjon

Adjacency list of vertex 0 head ->4 -> 1 Adjacency liste over toppunkt 1 hode -> 4 -> 3 -> 2 -> 0 Adjacency liste over toppunkt 2 hode -> 3 -> 1 Adjacency liste over toppunkt 3 hode -> 4 -> 2 -> 1 Adjacency liste over toppunkt 4 hode -> 3 -> 1 -> 0 

Grafgjennomgang

Breadth-First Search eller BFS

Breadth-First Traversal for en graf ligner på Breadth-First Traversal av et tre. Den eneste fangsten her er, i motsetning til trær, kan grafer inneholde sykluser, så vi kan komme til samme node igjen. For å unngå å behandle en node mer enn én gang, bruker vi en boolsk besøkt matrise. For enkelhets skyld antas det at alle toppunktene er tilgjengelige fra startpunktet.

For eksempel, i følgende graf, starter vi traversering fra toppunkt 2. Når vi kommer til toppunkt 0, ser vi etter alle tilstøtende toppunkter av det. 2 er også et tilstøtende toppunkt på 0. Hvis vi ikke merker besøkte toppunkter, vil 2 bli behandlet på nytt og det blir en ikke-avsluttende prosess. En Breadth-First Traversal av følgende graf er 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>

Produksjon

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1 

Tidskompleksitet: O(V+E) hvor V er antall toppunkter i grafen og E er antall kanter i grafen.

Depth First Search eller DFS

Depth First Traversal for en graf ligner på Depth First Traversal av et tre. Den eneste fangsten her er, i motsetning til trær, kan grafer inneholde sykluser, en node kan besøkes to ganger. For å unngå å behandle en node mer enn én gang, bruk en boolsk besøkt matrise.

Algoritme:

• Lag en rekursiv funksjon som tar indeksen til noden og en besøkt matrise.
• Merk gjeldende node som besøkt og skriv ut noden.
• Gå gjennom alle tilstøtende og umerkede noder og kall den rekursive funksjonen med indeksen til den tilstøtende noden.

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> )>

Produksjon

Following is DFS from (starting from vertex 2) 2 0 1 3 

Tidskompleksitet: O(V + E), der V er antall hjørner og E er antall kanter i grafen.