Data struktur är ett sätt att organisera data så att de kan nås mer effektivt beroende på situationen. Datastrukturer är grunderna i alla programmeringsspråk som ett program är byggt runt. Python hjälper till att lära sig grunderna för dessa datastrukturer på ett enklare sätt jämfört med andra programmeringsspråk.
I den här artikeln kommer vi att diskutera datastrukturerna i Python-programmeringsspråket och hur de är relaterade till vissa specifika inbyggda datastrukturer som listtupler, ordböcker etc. samt några avancerade datastrukturer som träd, grafer etc.
Listor
Pythonlistor är precis som arrayerna, deklarerade på andra språk som är en ordnad samling av data. Det är väldigt flexibelt då objekten i en lista inte behöver vara av samma typ.
Implementeringen av Python List liknar Vectors i C++ eller ArrayList i JAVA. Den kostsamma operationen är att infoga eller ta bort elementet från början av listan eftersom alla element måste flyttas. Insättning och radering i slutet av listan kan också bli kostsamt i det fall det förallokerade minnet blir fullt.
Vi kan skapa en lista i python som visas nedan.
Exempel: Skapa Python List
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Produktion
[1, 2, 3, 'GFG', 2.3]>
Listelement kan nås av det tilldelade indexet. I python startindex för listan är sekvensen 0 och slutindexet är (om N element finns där) N-1.
Exempel: 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>])> |
>
läsa från en csv-fil i java
>Produktion
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>
Lexikon
Python ordbok är som hashtabeller på vilket annat språk som helst med tidskomplexiteten O(1). Det är en oordnad samling av datavärden, som används för att lagra datavärden som en karta, som, till skillnad från andra datatyper som bara innehåller ett enda värde som ett element, innehåller Dictionary paret nyckel:värde. Nyckel-värde finns i ordboken för att göra den mer optimerad.
Indexering av Python Dictionary görs med hjälp av nycklar. Dessa är av vilken typ som helst som kan hashbart, dvs ett objekt vars aldrig kan ändras som strängar, siffror, tupler, etc. Vi kan skapa en ordbok genom att använda klammerparenteser ({}) eller ordboksförståelse .
Exempel: 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)> |
>
>Produktion
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}> Tuple
Python Tuple är en samling av Python-objekt ungefär som en lista men Tuples är oföränderliga till sin natur, dvs. elementen i tuplen kan inte läggas till eller tas bort när de väl har skapats. Precis som en lista kan en Tuple också innehålla element av olika slag.
I Python skapas tupler genom att placera en sekvens av värden separerade med 'komma' med eller utan användning av parenteser för gruppering av datasekvensen.
Notera: Tuples kan också skapas med ett enda element, men det är lite knepigt. Att ha ett element inom parentes är inte tillräckligt, det måste finnas ett efterföljande 'komma' för att göra det till en tupel.
Exempel: 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>])> |
>
>Produktion
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> Uppsättning
Python set är en oordnad samling av data som är föränderlig och inte tillåter några duplicerade element. Uppsättningar används i princip för att inkludera medlemskapstestning och eliminera dubbla poster. Datastrukturen som används i detta är Hashing, en populär teknik för att utföra infogning, radering och genomgång i O(1) i genomsnitt.
Om flera värden finns på samma indexposition, läggs värdet till den indexpositionen för att bilda en länkad lista. I implementeras CPython-uppsättningar med hjälp av en ordbok med dummyvariabler, där nyckelväsen medlemmarna ställer in med större optimeringar av tidskomplexiteten.
Set Implementering:
Uppsättningar med många operationer på en enda hashtabell:
Exempel: Python Set Operations
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>)> |
>
>Produktion
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Frysta set
Frysta uppsättningar i Python är oföränderliga objekt som endast stöder metoder och operatorer som producerar ett resultat utan att påverka den eller de frusna uppsättningarna som de tillämpas på. Även om element i en uppsättning kan ändras när som helst, förblir element i den frysta uppsättningen desamma efter att de skapats.
Om inga parametrar skickas, returnerar den en tom frusen uppsättning.
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')> |
>
>Produktion
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Sträng
Python-strängar är arrayer av byte som representerar Unicode-tecken. I enklare termer är en sträng en oföränderlig uppsättning tecken. Python har ingen teckendatatyp, ett enda tecken är helt enkelt en sträng med längden 1.
Notera: Eftersom strängar är oföränderliga, kommer modifiering av en sträng att resultera i att en ny kopia skapas.
Exempel: Python Strings Operations
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>])> |
>
>Produktion
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray ger en föränderlig sekvens av heltal i intervallet 0 <= x < 256.
Exempel: Python Bytearray Operations
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)> |
>
>Produktion
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Hittills har vi studerat alla datastrukturer som är inbyggda i kärnan Python. Låt nu dyka mer djupt in i Python och se samlingsmodulen som tillhandahåller några behållare som är användbara i många fall och ger fler funktioner än de ovan definierade funktionerna.
Insamlingsmodul
Python-insamlingsmodulen introducerades för att förbättra funktionaliteten hos de inbyggda datatyperna. Det ger olika behållare, låt oss se var och en av dem i detalj.
Räknare
En räknare är en underklass till ordboken. Den används för att hålla räkningen av elementen i en iterabel i form av en oordnad ordbok där nyckeln representerar elementet i iterabeln och värdet representerar räkningen av det elementet i den iterbara. Detta motsvarar en påse eller flera andra språk.
Exempel: Python Counter Operations
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)> |
>
>Produktion
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> OrderedDict
En OrderedDict är också en underklass av ordbok men till skillnad från en ordbok kommer den ihåg i vilken ordning nycklarna sattes in.
Exempel: Python OrderedDict Operations
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)> |
>
>Produktion
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 används för att tillhandahålla vissa standardvärden för nyckeln som inte finns och som aldrig ger upphov till ett KeyError. Dess objekt kan initieras med metoden DefaultDict() genom att skicka datatypen som ett argument.
Notera: default_factory är en funktion som tillhandahåller standardvärdet för den skapade ordboken. Om denna parameter saknas så höjs KeyError.
Exempel: Python DefaultDict Operations
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)> |
>
>Produktion
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> Kedjekarta
En ChainMap kapslar in många ordböcker i en enda enhet och returnerar en lista med ordböcker. När en nyckel behövs för att hittas, söks alla ordböcker en efter en tills nyckeln hittas.
Exempel: 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'>])> |
>
>
Produktion
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
Namnet Tuple
A Namnet Tuple returnerar ett tuppelobjekt med namn för varje position som de vanliga tuplarna saknar. Tänk till exempel på en tuppelnamn elev där det första elementet representerar fname, andra representerar lname och det tredje elementet representerar DOB. Anta att för att anropa fname istället för att komma ihåg indexpositionen kan du faktiskt anropa elementet genom att använda fname-argumentet, då blir det väldigt enkelt att komma åt tuples-elementet. Denna funktion tillhandahålls av NamedTuple.
Exempel: Python NamedTuple Operations
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)> |
>
>Produktion
The Student age using index is : 19 The Student name using keyname is : Nandini>
Om vad
Deque (dubbelt avslutad kö) är den optimerade listan för snabbare append- och popoperationer från båda sidor av behållaren. Det ger O(1)-tidskomplexitet för append- och popoperationer jämfört med listan med O(n)-tidskomplexitet.
Python Deque implementeras med hjälp av dubbellänkade listor, därför är prestandan för slumpmässig åtkomst till elementen O(n).
Exempel: Python Deque Operations
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)> |
slumptal mellan 1 och 10
>
>Produktion
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 är en ordboksliknande behållare som fungerar som ett omslag runt ordboksobjekten. Denna behållare används när någon vill skapa sin egen ordbok med någon modifierad eller ny funktionalitet.
Exempel: 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>)> |
>
>
Produktion
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Användarlista
UserList är en listliknande behållare som fungerar som ett omslag runt listobjekten. Detta är användbart när någon vill skapa sin egen lista med någon modifierad eller ytterligare funktionalitet.
Exempel: 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()> |
>
>
Produktion
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
UserString
UserString är en strängliknande behållare och precis som UserDict och UserList fungerar den som ett omslag runt strängobjekt. Det används när någon vill skapa sina egna strängar med någon modifierad eller ytterligare funktionalitet.
Exempel: 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)> |
>
>Produktion
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Nu efter att ha studerat alla datastrukturer, låt oss se några avancerade datastrukturer som stack, kö, graf, länkad lista, etc. som kan användas i Python Language.
Länkad lista
En länkad lista är en linjär datastruktur, där elementen inte lagras på sammanhängande minnesplatser. Elementen i en länkad lista är länkade med hjälp av pekare som visas i bilden nedan:
En länkad lista representeras av en pekare till den första noden i den länkade listan. Den första noden kallas huvudet. Om den länkade listan är tom är värdet på huvudet NULL. Varje nod i en lista består av minst två delar:
- Data
- Pekare (eller referens) till nästa nod
Exempel: Definiera länkad lista 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> |
>
>
Låt oss skapa en enkel länkad lista 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 |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Länkad listövergång
I det tidigare programmet har vi skapat en enkel länkad lista med tre noder. Låt oss gå igenom den skapade listan och skriva ut data för varje nod. För genomgång, låt oss skriva en allmän funktion printList() som skriver ut vilken lista som helst.
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()> |
>
>Produktion
1 2 3>
Stack
A stack är en linjär datastruktur som lagrar objekt på ett Last-In/First-Out (LIFO) eller First-In/Last-Out (FILO) sätt. I stack läggs ett nytt element till i ena änden och ett element tas endast bort från den änden. Insert och delete-operationerna kallas ofta push och pop.
Funktionerna associerade med stack är:
- empty() – Returnerar om stacken är tom – Tidskomplexitet: O(1) size() – Returnerar storleken på stacken – Tidskomplexitet: O(1) top() – Returnerar en referens till det översta elementet i stacken – Tidskomplexitet: O(1) push(a) – Infogar elementet 'a' överst i stacken – Tidskomplexitet: O(1) pop() – Tar bort det översta elementet i stacken – Tidskomplexitet: O( 1)
Python Stack Implementering
Stack i Python kan implementeras på följande sätt:
- lista
- Collections.deque
- queue.LifoQueue
Implementering med hjälp av List
Pythons inbyggda datastrukturlista kan användas som en stack. Istället för push(), används append() för att lägga till element till toppen av stacken medan pop() tar bort elementet i LIFO-ordning.
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> |
>
>Produktion
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementering med collections.deque:
Python-stack kan implementeras med hjälp av deque-klassen från samlingsmodulen. Deque föredras framför listan i de fall där vi behöver snabbare append- och pop-operationer från båda ändarna av behållaren, eftersom deque ger en O(1)-tidskomplexitet för append- och pop-operationer jämfört med list som ger O(n) tidskomplexitet.
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> |
>
>Produktion
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementering med hjälp av kömodul
Kömodulen har också en LIFO Queue, som i grunden är en Stack. Data infogas i Queue med put()-funktionen och get() tar ut data från Queue.
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())> |
>
>Produktion
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Kö
Som en stack, den kö är en linjär datastruktur som lagrar objekt på ett First In First Out (FIFO) sätt. Med en kö tas det senast tillagda objektet bort först. Ett bra exempel på kö är varje kö av konsumenter till en resurs där konsumenten som kom först serveras först.
Operationer associerade med kö är:
- Enqueue: Lägger till ett objekt i kön. Om kön är full, så sägs det vara ett överflödestillstånd – Tidskomplexitet: O(1) Dequeue: Tar bort ett objekt från kön. Föremålen skjuts i samma ordning som de skjuts. Om kön är tom, sägs det vara ett underflödestillstånd – Tidskomplexitet: O(1) Främre: Hämta det främre objektet från kön – Tidskomplexitet: O(1) Bakre: Hämta det sista objektet från kön – Tidskomplexitet : O(1)
Python-köimplementering
Kö i Python kan implementeras på följande sätt:
- lista
- samlingar.deque
- svans.svans
Implementering med hjälp av lista
Istället för enqueue() och dequeue(), används append() och pop()-funktionen.
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> |
>
>Produktion
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementering med hjälp av collections.deque
Deque föredras framför listan i de fall där vi behöver snabbare append- och pop-operationer från båda ändarna av behållaren, eftersom deque ger en O(1)-tidskomplexitet för append- och pop-operationer jämfört med list som ger O(n) tidskomplexitet.
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> |
>
>Produktion
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementering med hjälp av queue.Queue
hur man kör ett skript i linux
queue.Queue(maxsize) initierar en variabel till en maximal storlek på maxsize. En maxstorlek på noll '0' betyder en oändlig kö. Denna kö följer FIFO-regeln.
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())> |
>
>Produktion
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Prioriterad kö
Prioriterade köer är abstrakta datastrukturer där varje data/värde i kön har en viss prioritet. Till exempel hos flygbolag kommer bagage med titeln Business eller First-class tidigare än resten. Priority Queue är en förlängning av kön med följande egenskaper.
- Ett element med hög prioritet tas ur kö före ett element med låg prioritet.
- Om två element har samma prioritet serveras de enligt deras ordning i kön.
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())> |
>
>Produktion
12 1 14 7 14 12 7 1>
Heap-kö (eller heapq)
heapq-modul i Python tillhandahåller högdatastrukturen som huvudsakligen används för att representera en prioritetskö. Egenskapen för denna datastruktur i Python är att varje gång det minsta heapelementet poppas (min-heap). Närhelst element trycks eller skjuts upp bibehålls högstrukturen. Heap[0]-elementet returnerar också det minsta elementet varje gång.
Det stöder extrahering och infogning av det minsta elementet i O(log n) gånger.
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))> |
>
>Produktion
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 träd
Ett träd är en hierarkisk datastruktur som ser ut som bilden nedan -
tree ---- j <-- root / f k / a h z <-- leaves>
Trädets översta nod kallas roten medan de nedersta noderna eller noderna utan barn kallas bladnoder. Noderna som är direkt under en nod kallas dess barn och noderna som är direkt ovanför något kallas dess förälder.
Ett binärt träd är ett träd vars element kan ha nästan två barn. Eftersom varje element i ett binärt träd bara kan ha två barn, brukar vi kalla dem för vänster och höger barn. En binär trädnod innehåller följande delar.
- Data
- Pekare till vänster barn
- Pekare till rätt barn
Exempel: Definiera nodklass
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> |
>
>
Låt oss nu skapa ett träd med 4 noder i Python. Låt oss anta att trädstrukturen ser ut som nedan -
tree ---- 1 <-- root / 2 3 / 4>
Exempel: Lägga till data i trädet
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'''> |
>
>
Traversal av träd
Träd kan korsas på olika sätt. Följande är de allmänt använda sätten att korsa träd. Låt oss betrakta trädet nedan -
tree ---- 1 <-- root / 2 3 / 4 5>
Depth First Traversals:
- Inordning (vänster, rot, höger): 4 2 5 1 3
- Förbeställning (rot, vänster, höger): 1 2 4 5 3
- Postorder (vänster, höger, rot): 4 5 2 3 1
Algorithm Inorder(träd)
- Gå igenom det vänstra underträdet, d.v.s. anrop Inorder (vänster-underträd)
- Besök roten.
- Gå igenom det högra underträdet, d.v.s. anrop Inorder (höger-underträdet)
Algoritm förbeställning (träd)
- Besök roten.
- Gå igenom det vänstra underträdet, d.v.s. ring Preorder (vänster-underträd)
- Gå igenom det högra underträdet, d.v.s. anropa Preorder (höger-underträdet)
Algorithm Postorder(tree)
- Gå igenom det vänstra underträdet, d.v.s. anrop Postorder (vänster-underträd)
- Gå igenom det högra underträdet, d.v.s. anrop Postorder (höger-underträdet)
- 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)> |
>
>Produktion
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>
Tidskomplexitet – O(n)
Bredth-First eller Level Order Traversal
Nivåordningsövergång av ett träd är bredd-första traversering för trädet. Nivåordningens genomgång av ovanstående träd är 1 2 3 4 5.
För varje nod besöks först noden och sedan placeras dess undernoder i en FIFO-kö. Nedan är algoritmen för detsamma –
- Skapa en tom kö q
- temp_node = rot /*börja från rot*/
- Loop medan temp_node inte är NULL
- skriv ut temp_node->data.
- Ställ temp_nodes barn (först vänster sedan höger barn) till q
- Ta bort en nod från 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)> |
>
>Produktion
Level Order Traversal of binary tree is - 1 2 3 4 5>
Tidskomplexitet: O(n)
Graf
A Graf är en olinjär datastruktur som består av noder och kanter. Noderna kallas ibland även för hörn och kanterna är linjer eller bågar som förbinder två valfria noder i grafen. Mer formellt kan en graf definieras som en graf som består av en ändlig uppsättning av hörn (eller noder) och en uppsättning kanter som förbinder ett par noder.
I grafen ovan är uppsättningen av hörn V = {0,1,2,3,4} och uppsättningen av kanter E = {01, 12, 23, 34, 04, 14, 13}.
Följande två är de mest använda representationerna av en graf.
- Adjacency matris
- Adjacency List
Adjacency matris
Adjacency Matrix är en 2D-matris med storleken V x V där V är antalet hörn i en graf. Låt 2D-matrisen vara adj[][], en lucka adj[i][j] = 1 indikerar att det finns en kant från vertex i till vertex j. Närliggande matris för en oriktad graf är alltid symmetrisk. Adjacency Matrix används också för att representera viktade grafer. Om adj[i][j] = w, så finns det en kant från vertex i till vertex j med vikt 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())> |
>
>
Produktion
Vertices of Graph
['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]]
Adjacency List
En rad listor används. Storleken på arrayen är lika med antalet hörn. Låt arrayen vara en array[]. En inmatningsmatris[i] representerar listan över hörn som gränsar till det i:te hörnet. Denna representation kan också användas för att representera en viktad graf. Kanternas vikter kan representeras som listor med par. Följande är granskningslistan representation av grafen ovan.
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()> |
>
>Produktion
Adjacency list of vertex 0 head ->4 -> 1 Adjacency list av vertex 1 head -> 4 -> 3 -> 2 -> 0 Adjacency list of vertex 2 head -> 3 -> 1 Adjacency list of vertex 3 head -> 4 -> 2 -> 1 Adjacency lista över vertex 4 huvud -> 3 -> 1 -> 0>
Genomgång av graf
Breadth-First Search eller BFS
Bredth-First Traversal för en graf liknar Breadth-First Traversal av ett träd. Den enda haken här är att till skillnad från träd kan grafer innehålla cykler, så vi kan komma till samma nod igen. För att undvika att bearbeta en nod mer än en gång använder vi en boolesk besökt array. För enkelhetens skull antas det att alla hörn är nåbara från startpunkten.
Till exempel, i följande graf, börjar vi traversering från vertex 2. När vi kommer till vertex 0 letar vi efter alla intilliggande hörn av den. 2 är också en angränsande hörn på 0. Om vi inte markerar besökta hörn, kommer 2 att bearbetas igen och det blir en icke-avslutande process. En Breadth-First Traversal av följande graf är 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> |
>
>Produktion
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Tidskomplexitet: O(V+E) där V är antalet hörn i grafen och E är antalet kanter i grafen.
Depth First Search eller DFS
Depth First Traversal för en graf liknar Depth First Traversal av ett träd. Den enda haken här är att till skillnad från träd kan grafer innehålla cykler, en nod kan besökas två gånger. För att undvika att bearbeta en nod mer än en gång, använd en boolesk besökt array.
Algoritm:
- Skapa en rekursiv funktion som tar nodens index och en besökt array.
- Markera den aktuella noden som besökt och skriv ut noden.
- Gå igenom alla intilliggande och omarkerade noder och anrop den rekursiva funktionen med indexet för den intilliggande 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>)> |
>
>Produktion
Following is DFS from (starting from vertex 2) 2 0 1 3>
Tidskomplexitet: O(V + E), där V är antalet hörn och E är antalet kanter i grafen.