Structuri de date reprezintă o modalitate de organizare a datelor astfel încât să poată fi accesate mai eficient în funcție de situație. Structurile de date sunt elementele fundamentale ale oricărui limbaj de programare în jurul căruia este construit un program. Python ajută la învățarea elementelor fundamentale ale acestor structuri de date într-un mod mai simplu în comparație cu alte limbaje de programare.
În acest articol, vom discuta despre structurile de date din limbajul de programare Python și despre modul în care acestea sunt legate de unele structuri specifice de date încorporate, cum ar fi tupluri de listă, dicționare etc., precum și unele structuri de date avansate, cum ar fi arbori, grafice etc.
Liste
Listele Python sunt la fel ca și matricele, declarate în alte limbi care reprezintă o colecție ordonată de date. Este foarte flexibil, deoarece elementele dintr-o listă nu trebuie să fie de același tip.
Implementarea Python List este similară cu Vectors în C++ sau ArrayList în JAVA. Operațiunea costisitoare este inserarea sau ștergerea elementului de la începutul Listei, deoarece toate elementele trebuie să fie mutate. Inserarea și ștergerea la sfârșitul listei pot deveni costisitoare și în cazul în care memoria prealocată devine plină.
Putem crea o listă în python, așa cum se arată mai jos.
Exemplu: Crearea listei Python
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Ieșire
[1, 2, 3, 'GFG', 2.3]>
Elementele listei pot fi accesate prin indexul atribuit. În indexul de pornire python al listei, secvența este 0 și indexul final este (dacă există N elemente) N-1.
Exemplu: Operații Python Listă
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>])> |
>
list vs set in java
>Ieșire
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>
Dicţionar
Dicționar Python este ca tabelele hash în orice altă limbă cu complexitatea de timp a O(1). Este o colecție neordonată de valori de date, folosită pentru a stoca valorile datelor ca o hartă, care, spre deosebire de alte tipuri de date care dețin doar o singură valoare ca element, Dicționarul deține perechea cheie:valoare. Valoarea-cheie este furnizată în dicționar pentru a-l optimiza.
Indexarea dicționarului Python se face cu ajutorul tastelor. Acestea sunt de orice tip hashable, adică un obiect al cărui obiect nu se poate schimba niciodată, cum ar fi șiruri, numere, tupluri etc. Putem crea un dicționar folosind acolade ({}) sau înțelegerea dicționarului .
Exemplu: 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)> |
>
>Ieșire
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}> Tuplu
Python Tuple este o colecție de obiecte Python asemănătoare unei liste, dar tuplurile sunt imuabile în natură, adică elementele din tuplu nu pot fi adăugate sau eliminate odată create. La fel ca o Listă, un tuplu poate conține și elemente de diferite tipuri.
În Python, tuplurile sunt create prin plasarea unei secvențe de valori separate prin „virgulă” cu sau fără utilizarea parantezelor pentru gruparea secvenței de date.
Notă: Tuplurile pot fi create și cu un singur element, dar este puțin complicat. A avea un element în paranteze nu este suficient, trebuie să existe o „virgulă” în urmă pentru a-l face un tuplu.
Exemplu: Operații cu tuplu Python
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>])> |
>
>Ieșire
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> A stabilit
Set Python este o colecție neordonată de date care este mutabilă și nu permite niciun element duplicat. Seturile sunt folosite practic pentru a include testarea membrilor și eliminarea intrărilor duplicate. Structura de date folosită în aceasta este Hashing, o tehnică populară pentru a efectua inserarea, ștergerea și traversarea în O(1) în medie.
Dacă mai multe valori sunt prezente la aceeași poziție de index, atunci valoarea este atașată la acea poziție de index, pentru a forma o listă legată. În, seturile CPython sunt implementate folosind un dicționar cu variabile fictive, în care ființele cheie pe care membrii le setează cu optimizări mai mari la complexitatea timpului.
Set de implementare:
Seturi cu numeroase operații pe un singur HashTable:
Exemplu: Operații de set Python
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>)> |
>
>Ieșire
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Seturi congelate
Seturile înghețate în Python sunt obiecte imuabile care acceptă doar metode și operatori care produc un rezultat fără a afecta setul sau seturile înghețate la care sunt aplicate. În timp ce elementele unui set pot fi modificate în orice moment, elementele setului înghețat rămân aceleași după creare.
Dacă nu sunt transmise parametri, returnează un set înghețat gol.
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')> |
>
>Ieșire
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Şir
Șirurile Python sunt matrice de octeți care reprezintă caractere Unicode. În termeni mai simpli, un șir este o matrice imuabilă de caractere. Python nu are un tip de date caracter, un singur caracter este pur și simplu un șir cu lungimea de 1.
Notă: Deoarece șirurile sunt imuabile, modificarea unui șir va duce la crearea unei noi copii.
Exemplu: Operații cu șiruri Python
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>])> |
>
>Ieșire
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray oferă o secvență mutabilă de numere întregi în intervalul 0 <= x < 256.
Exemplu: Operații Python Bytearray
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)> |
>
>Ieșire
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Până acum am studiat toate structurile de date care sunt încorporate în Python de bază. Acum, să ne aprofundăm mai mult în Python și să vedem modulul de colecții care oferă câteva containere care sunt utile în multe cazuri și oferă mai multe caracteristici decât funcțiile definite mai sus.
Modulul Colecții
Modulul de colectare Python a fost introdus pentru a îmbunătăți funcționalitatea tipurilor de date încorporate. Oferă diverse containere, să le vedem pe fiecare în detaliu.
Contoare
Un contor este o subclasă a dicționarului. Este folosit pentru a păstra numărul elementelor dintr-un iterabil sub forma unui dicționar neordonat, unde cheia reprezintă elementul din iterabil și valoarea reprezintă numărul acelui element din iterabil. Acest lucru este echivalent cu o geantă sau un set multiplu de alte limbi.
Exemplu: Operații de contor Python
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)> |
>
>Ieșire
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> OrderedDict
Un OrderedDict este, de asemenea, o subclasă de dicționar, dar spre deosebire de un dicționar, își amintește ordinea în care au fost introduse cheile.
Exemplu: 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)> |
>
>Ieșire
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 este folosit pentru a furniza unele valori implicite pentru cheia care nu există și nu generează niciodată o KeyError. Obiectele sale pot fi inițializate folosind metoda DefaultDict() prin trecerea tipului de date ca argument.
Notă: default_factory este o funcție care oferă valoarea implicită pentru dicționarul creat. Dacă acest parametru este absent, atunci KeyError este ridicată.
Exemplu: Operații Python DefaultDict
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)> |
>
>Ieșire
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> ChainMap
Un ChainMap încapsulează multe dicționare într-o singură unitate și returnează o listă de dicționare. Când trebuie găsită o cheie, atunci toate dicționarele sunt căutate unul câte unul până când cheia este găsită.
Exemplu: Operații Python ChainMap
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'>])> |
>
>
Ieșire
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
NamedTuple
A NamedTuple returnează un obiect tuplu cu nume pentru fiecare poziție care le lipsește tuplurile obișnuite. De exemplu, luați în considerare un tuplu numește student unde primul element reprezintă fname, al doilea reprezintă lname și al treilea element reprezintă DOB. Să presupunem că pentru a apela fname în loc să vă amintiți poziția indexului puteți apela de fapt elementul folosind argumentul fname, atunci va fi foarte ușor să accesați elementul tuples. Această funcționalitate este oferită de NamedTuple.
Exemplu: Operații Python NamedTuple
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)> |
>
>Ieșire
The Student age using index is : 19 The Student name using keyname is : Nandini>
Despre ce
Deque (coadă dublu terminată) este lista optimizată pentru operații mai rapide de adăugare și deschidere de pe ambele părți ale containerului. Oferă complexitate de timp O(1) pentru operațiunile de adăugare și pop în comparație cu lista cu complexitate de timp O(n).
Python Deque este implementat folosind liste dublu legate, prin urmare, performanța pentru accesarea aleatorie a elementelor este O(n).
Exemplu: Operații Python Deque
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)> |
parcurgerea în prealabil a unui arbore
>
>Ieșire
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 este un container asemănător dicționarului care acționează ca un înveliș în jurul obiectelor dicționarului. Acest container este folosit atunci când cineva dorește să-și creeze propriul dicționar cu unele funcționalități modificate sau noi.
Exemplu: 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>)> |
>
>
Ieșire
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Lista de utilizatori
UserList este un container asemănător unei liste care acționează ca un înveliș în jurul obiectelor din listă. Acest lucru este util atunci când cineva dorește să-și creeze propria listă cu unele funcționalități modificate sau suplimentare.
Exemple: 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()> |
>
>
Ieșire
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
UserString
UserString este un container asemănător șirului și la fel ca UserDict și UserList, acționează ca un înveliș în jurul obiectelor șir. Este folosit atunci când cineva dorește să-și creeze propriile șiruri de caractere cu unele funcționalități modificate sau suplimentare.
Exemplu: 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)> |
>
>Ieșire
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Acum, după ce am studiat toate structurile de date, să vedem câteva structuri de date avansate, cum ar fi stiva, coada, graficul, lista legată etc., care pot fi utilizate în limbajul Python.
Lista legată
O listă legată este o structură de date liniară, în care elementele nu sunt stocate în locații de memorie adiacente. Elementele dintr-o listă legată sunt legate folosind pointeri, așa cum se arată în imaginea de mai jos:
O listă legată este reprezentată de un pointer către primul nod al listei legate. Primul nod se numește cap. Dacă lista legată este goală, atunci valoarea capului este NULL. Fiecare nod dintr-o listă constă din cel puțin două părți:
- Date
- Indicator (sau referință) către următorul nod
Exemplu: definirea listei legate în 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> |
>
>
Să creăm o listă simplă legată cu 3 noduri.
Python3
# A simple Python program to introduce a linked list> # Node class> class> Node:> ># Function to initialise the node object> >def> __init__(>self>, data):> >self>.data>=> data># Assign data> >self>.>next> => None> # Initialize next as null> # Linked List class contains a Node object> class> LinkedList:> ># Function to initialize head> >def> __init__(>self>):> >self>.head>=> None> # Code execution starts here> if> __name__>=>=>'__main__'>:> ># Start with the empty list> >list> => LinkedList()> >list>.head>=> Node(>1>)> >second>=> Node(>2>)> >third>=> Node(>3>)> >'''> >Three nodes have been created.> >We have references to these three blocks as head,> >second and third> >list.head second third> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | None | | 2 | None | | 3 | None |> >+----+------+ +----+------+ +----+------+> >'''> >list>.head.>next> => second;># Link first node with second> >'''> >Now next of first Node refers to second. So they> >both are linked.> >list.head second third> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | o-------->| 2 | nul | | 3 | nul |> >+----+------+ +----+------+ +----+------+> >'''> >second.>next> => third;># Link second node with the third node> >'''> >Now next of second Node refers to third. So all three> >nodes are linked.> >list.head second third> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | o-------->| 2 | o-------->| 3 | nul |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Traversarea listelor conectate
În programul anterior, am creat o listă simplă legată cu trei noduri. Să parcurgem lista creată și să imprimăm datele fiecărui nod. Pentru traversare, să scriem o funcție de uz general printList() care tipărește orice listă dată.
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()> |
>
>Ieșire
1 2 3>
Grămadă
A grămadă este o structură de date liniară care stochează articole într-o manieră Last-In/First-Out (LIFO) sau First-In/Last-Out (FILO). În stivă, un element nou este adăugat la un capăt și un element este eliminat numai de la acel capăt. Operațiile de inserare și ștergere sunt adesea numite push și pop.
Funcțiile asociate cu stiva sunt:
- empty() – Returnează dacă stiva este goală – Time Complexity: O(1) size() – Returnează dimensiunea stivei – Time Complexity: O(1) top() – Returnează o referință la elementul cel mai de sus al stivei – Complexitatea timpului: O(1) push(a) – Inserează elementul „a” în partea de sus a stivei – Complexitatea timpului: O(1) pop() – Șterge elementul cel mai de sus al stivei – Complexitatea timpului: O( 1)
Implementarea stivei Python
Stack în Python poate fi implementat folosind următoarele moduri:
- listă
- Colecţii.deque
- coadă.LifoQueue
Implementare folosind List
Lista de structuri de date încorporată din Python poate fi folosită ca stivă. În loc de push(), append() este folosit pentru a adăuga elemente în partea de sus a stivei, în timp ce pop() elimină elementul în ordinea LIFO.
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> |
>
>Ieșire
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementare folosind collections.deque:
Stiva Python poate fi implementată folosind clasa deque din modulul de colecții. Deque este preferat față de listă în cazurile în care avem nevoie de operații mai rapide de adăugare și pop de la ambele capete ale containerului, deoarece deque oferă o complexitate de timp O(1) pentru operațiunile de adăugare și pop în comparație cu lista care oferă O(n) complexitatea timpului.
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> |
>
>Ieșire
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementare folosind modulul de coadă
Modulul de coadă are, de asemenea, o coadă LIFO, care este practic o stivă. Datele sunt inserate în coadă folosind funcția put() și get() scoate datele din coadă.
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())> |
>
>Ieșire
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Coadă
Ca o stivă, coadă este o structură de date liniară care stochează articole într-o manieră First In First Out (FIFO). Cu o coadă, articolul adăugat cel mai puțin recent este eliminat mai întâi. Un bun exemplu de coadă este orice coadă de consumatori pentru o resursă în care consumatorul care a venit primul este servit primul.
Operațiile asociate cu coada sunt:
- Codă: adaugă un articol în coadă. Dacă coada este plină, atunci se spune că este o condiție de depășire – Complexitatea timpului: O(1) Decodare: Îndepărtează un articol din coadă. Elementele sunt afișate în aceeași ordine în care sunt împinse. Dacă coada este goală, atunci se spune că este o condiție Underflow – Complexitatea timpului: O(1) Front: Preluați elementul din față din coadă – Complexitatea timpului: O(1) Spate: Obțineți ultimul articol din coadă – Complexitatea timpului : O(1)
Implementarea cozii Python
Coada în Python poate fi implementată în următoarele moduri:
- listă
- colecţii.deque
- coada.coada
Implementare folosind lista
În loc de enqueue() și dequeue(), este folosită funcția append() și 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> |
>
>Ieșire
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementare folosind collections.deque
Deque este preferat față de listă în cazurile în care avem nevoie de operații mai rapide de adăugare și pop de la ambele capete ale containerului, deoarece deque oferă o complexitate de timp O(1) pentru operațiunile de adăugare și pop în comparație cu lista care oferă O(n) complexitatea timpului.
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> |
>
>Ieșire
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementare folosind coada.Coda
conexiune java mysql
queue.Queue(maxsize) inițializează o variabilă la o dimensiune maximă de maxsize. O dimensiune maximă de zero „0” înseamnă o coadă infinită. Această coadă urmează regula FIFO.
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())> |
>
>Ieșire
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Coada prioritară
Cozi prioritare sunt structuri de date abstracte în care fiecare dată/valoare din coadă are o anumită prioritate. De exemplu, în companiile aeriene, bagajele cu titlul Business sau First-class ajung mai devreme decât restul. Priority Queue este o extensie a cozii cu următoarele proprietăți.
- Un element cu prioritate mare este scos din coadă înaintea unui element cu prioritate scăzută.
- Dacă două elemente au aceeași prioritate, acestea sunt servite în funcție de ordinea lor în coadă.
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]>>>>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())> |
>
>Ieșire
12 1 14 7 14 12 7 1>
coadă heap (sau heapq)
modulul heapq în Python furnizează structura de date heap care este utilizată în principal pentru a reprezenta o coadă prioritară. Proprietatea acestei structuri de date în Python este că de fiecare dată când cel mai mic element heap apare (min-heap). Ori de câte ori elementele sunt împinse sau sparte, structura heap este menținută. Elementul heap[0] returnează, de asemenea, cel mai mic element de fiecare dată.
Acceptă extragerea și inserarea celui mai mic element în timpii O(log n).
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))> |
>
>Ieșire
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>
Arborele binar
Un arbore este o structură de date ierarhică care arată ca figura de mai jos -
tree ---- j <-- root / f k / a h z <-- leaves>
Nodul cel mai de sus al arborelui se numește rădăcină, în timp ce nodurile cele mai de jos sau nodurile fără copii sunt numite nodurile frunzelor. Nodurile care sunt direct sub un nod sunt numite copii ale acestuia, iar nodurile care sunt direct deasupra unui nod sunt numite părinte.
Un arbore binar este un arbore ale cărui elemente pot avea aproape doi copii. Deoarece fiecare element dintr-un arbore binar poate avea doar 2 copii, de obicei îi numim copii stânga și dreapta. Un nod de arbore binar conține următoarele părți.
- Date
- Indicator către copilul stâng
- Indicator către copilul potrivit
Exemplu: Definirea clasei de nod
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> |
>
>
Acum să creăm un arbore cu 4 noduri în Python. Să presupunem că structura arborelui arată ca mai jos -
tree ---- 1 <-- root / 2 3 / 4>
Exemplu: Adăugarea de date în arbore
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'''> |
>
>
Traversarea copacului
Copacii pot fi traversați în diverse feluri. Următoarele sunt modalitățile utilizate în general pentru traversarea copacilor. Să luăm în considerare arborele de mai jos -
tree ---- 1 <-- root / 2 3 / 4 5>
Primele traversări de adâncime:
- În ordine (stânga, rădăcină, dreapta): 4 2 5 1 3
- Precomandă (rădăcină, stânga, dreapta): 1 2 4 5 3
- Post-comanda (stânga, dreapta, rădăcină): 4 5 2 3 1
Algoritm Inorder(arboresc)
- Traversați subarborele din stânga, adică apelați Inorder(subarborele stânga)
- Vizitați rădăcina.
- Traversați subarborele din dreapta, adică apelați Inorder (subarborele din dreapta)
Precomandă algoritm (arboresc)
- Vizitați rădăcina.
- Traversați subarborele din stânga, adică apelați Precomanda (subarborele stânga)
- Traversați subarborele din dreapta, adică apelați Precomanda (subarborele din dreapta)
Algoritm Ordin poștal(arboresc)
- Traversați subarborele din stânga, adică apelați Postorder(subarborele stânga)
- Traversați subarborele din dreapta, adică apelați Postorder (subarborele din dreapta)
- Vizitați rădăcina.
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)> |
>
>Ieșire
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>
Complexitatea timpului – O(n)
Lățimea-Primul nivel sau traversarea comenzii
Parcursul nivelului de ordine a unui copac este parcurgerea pe lățimea întâi pentru copac. Parcurgerea în ordinea nivelurilor a arborelui de mai sus este 1 2 3 4 5.
Pentru fiecare nod, mai întâi, nodul este vizitat și apoi nodurile sale secundare sunt puse într-o coadă FIFO. Mai jos este algoritmul pentru același -
- Creați o coadă goală q
- temp_node = rădăcină /*începe de la rădăcină*/
- Buclă în timp ce temp_node nu este NULL
- print temp_node->date.
- Puneți în coadă copiii lui temp_node (în primul rând copiii din stânga apoi din dreapta) la q
- Scoateți în coadă un nod din 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)>>>> > ># 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)> |
>
>Ieșire
Level Order Traversal of binary tree is - 1 2 3 4 5>
Complexitatea timpului: O(n)
Grafic
A grafic este o structură de date neliniară constând din noduri și muchii. Nodurile sunt uneori denumite și vârfuri, iar muchiile sunt linii sau arce care conectează oricare două noduri din grafic. Mai formal, un graf poate fi definit ca un graf constând dintr-un set finit de vârfuri (sau noduri) și un set de muchii care conectează o pereche de noduri.
În graficul de mai sus, mulțimea de vârfuri V = {0,1,2,3,4} și mulțimea de muchii E = {01, 12, 23, 34, 04, 14, 13}.
Următoarele două sunt cele mai frecvent utilizate reprezentări ale unui grafic.
- Matricea adiacentei
- Lista adiacentei
Matricea adiacentei
Matricea de adiacență este o matrice 2D de dimensiunea V x V unde V este numărul de vârfuri dintr-un grafic. Fie matricea 2D adj[][], un slot adj[i][j] = 1 indică faptul că există o muchie de la vârful i la vârful j. Matricea de adiacență pentru un grafic nedirecționat este întotdeauna simetrică. Matricea de adiacență este, de asemenea, utilizată pentru a reprezenta grafice ponderate. Dacă adj[i][j] = w, atunci există o muchie de la vârful i la vârful j cu greutatea 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())> |
>
>
Ieșire
Vârfurile graficului
[‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’]
Marginile graficului
[(„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)]
Matricea de adiacență a graficului
[[-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]]
Lista adiacentei
Este folosită o serie de liste. Mărimea tabloului este egală cu numărul de vârfuri. Fie matricea o matrice[]. Un tablou de intrare[i] reprezintă lista de vârfuri adiacente celui de-al i-lea vârf. Această reprezentare poate fi folosită și pentru a reprezenta un grafic ponderat. Greutățile muchiilor pot fi reprezentate ca liste de perechi. Mai jos este reprezentarea listei de adiacență a graficului de mai sus.
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()> |
>
>Ieșire
Adjacency list of vertex 0 head ->4 -> 1 Lista de adiacență a capului vârfului 1 -> 4 -> 3 -> 2 -> 0 Lista de adiacențe a capului vârfului 2 -> 3 -> 1 Lista de adiacență a capului vârfului 3 -> 4 -> 2 -> 1 Adiacență lista vârfului 4 cap -> 3 -> 1 -> 0>
Traversarea graficului
Breadth-First Search sau BFS
Lățimea-Prima traversare pentru un grafic este similar cu Breadth-First Traversal a unui arbore. Singura captură aici este că, spre deosebire de copaci, graficele pot conține cicluri, așa că putem ajunge din nou la același nod. Pentru a evita procesarea unui nod de mai multe ori, folosim o matrice booleană vizitată. Pentru simplitate, se presupune că toate vârfurile sunt accesibile de la vârful de pornire.
De exemplu, în graficul următor, începem traversarea de la vârful 2. Când ajungem la vârful 0, căutăm toate vârfurile adiacente ale acestuia. 2 este, de asemenea, un vârf adiacent de 0. Dacă nu marchem vârfurile vizitate, atunci 2 va fi procesat din nou și va deveni un proces care nu se încheie. O traversare pe lățime a următorului grafic este 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> |
>
>Ieșire
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Complexitatea timpului: O(V+E) unde V este numărul de vârfuri din grafic și E este numărul de muchii din grafic.
Depth First Search sau DFS
Adâncimea prima traversare pentru un grafic este similar cu Adâncimea prima traversare a unui arbore. Singura captură aici este, spre deosebire de copaci, graficele pot conține cicluri, un nod poate fi vizitat de două ori. Pentru a evita procesarea unui nod de mai multe ori, utilizați o matrice booleană vizitată.
Algoritm:
- Creați o funcție recursivă care preia indexul nodului și o matrice vizitată.
- Marcați nodul curent ca vizitat și imprimați nodul.
- Traversați toate nodurile adiacente și nemarcate și apelați funcția recursivă cu indexul nodului adiacent.
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>)> |
>
>Ieșire
Following is DFS from (starting from vertex 2) 2 0 1 3>
Complexitatea timpului: O(V + E), unde V este numărul de vârfuri și E este numărul de muchii din grafic.