Estructures de dades són una manera d'organitzar les dades perquè es pugui accedir de manera més eficient en funció de la situació. Les estructures de dades són els fonaments de qualsevol llenguatge de programació al voltant del qual es construeix un programa. Python ajuda a aprendre els fonaments d'aquestes estructures de dades d'una manera més senzilla en comparació amb altres llenguatges de programació.
En aquest article, parlarem de les estructures de dades del llenguatge de programació Python i de com es relacionen amb algunes estructures de dades específiques integrades com ara tuples de llista, diccionaris, etc., així com algunes estructures de dades avançades com arbres, gràfics, etc.
Llistes
Les llistes de Python són com les matrius, declarades en altres idiomes, que és una col·lecció ordenada de dades. És molt flexible ja que els elements d'una llista no cal que siguin del mateix tipus.
La implementació de Python List és similar a Vectors en C++ o ArrayList en JAVA. L'operació costosa és inserir o suprimir l'element des de l'inici de la llista, ja que cal canviar tots els elements. La inserció i la supressió al final de la llista també poden arribar a ser costoses en el cas que la memòria prèviament assignada s'ompli.
Podem crear una llista en Python com es mostra a continuació.
Exemple: creació d'una llista de Python
Python 3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Sortida
[1, 2, 3, 'GFG', 2.3]>
Es pot accedir als elements de la llista mitjançant l'índex assignat. A l'índex inicial de Python de la llista, la seqüència és 0 i l'índex final és (si hi ha N elements) N-1.
Exemple: Operacions de llista de Python
Python 3
# 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>])> |
>
per què la interfície del marcador a Java
>Sortida
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>
Diccionari
Diccionari Python és com taules hash en qualsevol altre llenguatge amb la complexitat temporal de O(1). És una col·lecció no ordenada de valors de dades, que s'utilitza per emmagatzemar valors de dades com un mapa, que, a diferència d'altres tipus de dades que només contenen un valor únic com a element, el Diccionari conté el parell clau:valor. El valor-clau es proporciona al diccionari per optimitzar-lo.
La indexació del diccionari Python es fa amb l'ajuda de tecles. Són de qualsevol tipus hashable, és a dir, un objecte del qual mai no pot canviar com cadenes, números, tuples, etc. Podem crear un diccionari utilitzant claus ({}) o comprensió del diccionari .
Exemple: Operacions del diccionari Python
Python 3
# 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)> |
>
>Sortida
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
Tuple Python és una col·lecció d'objectes Python semblant a una llista, però les tuples són immutables per naturalesa, és a dir, els elements de la tupla no es poden afegir ni eliminar un cop creats. Igual que una llista, una tupla també pot contenir elements de diversos tipus.
A Python, les tuples es creen col·locant una seqüència de valors separats per 'coma' amb o sense l'ús de parèntesis per agrupar la seqüència de dades.
Nota: Les tuples també es poden crear amb un sol element, però és una mica complicat. Tenir un element entre parèntesis no és suficient, hi ha d'haver una 'coma' al final per convertir-lo en una tupla.
Exemple: Operacions de tuple Python
Python 3
# 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>])> |
>
>Sortida
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> Conjunt
Conjunt de Python és una col·lecció de dades no ordenada que és mutable i no permet cap element duplicat. Els conjunts s'utilitzen bàsicament per incloure proves de pertinença i eliminar entrades duplicades. L'estructura de dades que s'utilitza en això és Hashing, una tècnica popular per dur a terme la inserció, la supressió i el recorregut en O(1) de mitjana.
Si hi ha diversos valors a la mateixa posició d'índex, el valor s'afegeix a aquesta posició d'índex per formar una llista enllaçada. En, els conjunts de CPython s'implementen utilitzant un diccionari amb variables simulades, on els éssers clau els membres configuren amb majors optimitzacions a la complexitat del temps.
Implementació del conjunt:
Conjunts amb nombroses operacions en una sola Taula Hash:
Exemple: operacions de conjunt de Python
Python 3
# 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>)> |
>
>Sortida
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Conjunts congelats
Els conjunts congelats en Python són objectes immutables que només admeten mètodes i operadors que produeixen un resultat sense afectar el conjunt o conjunts congelats als quals s'apliquen. Tot i que els elements d'un conjunt es poden modificar en qualsevol moment, els elements del conjunt congelat segueixen sent els mateixos després de la creació.
Si no es passa cap paràmetre, retorna un conjunt congelat buit.
Python 3
# 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')> |
>
>Sortida
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Corda
Les cadenes de Python són matrius de bytes que representen caràcters Unicode. En termes més senzills, una cadena és una matriu immutable de caràcters. Python no té un tipus de dades de caràcter, un únic caràcter és simplement una cadena amb una longitud d'1.
Nota: Com que les cadenes són immutables, modificar una cadena donarà lloc a la creació d'una còpia nova.
Exemple: operacions de cadenes de Python
Python 3
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>])> |
>
>Sortida
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray proporciona una seqüència mutable de nombres enters en el rang 0 <= x < 256.
Exemple: Operacions de Python Bytearray
Python 3
# 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)> |
>
>Sortida
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Fins ara hem estudiat totes les estructures de dades que s'incorporen al nucli Python. Ara aprofundim més en Python i vegeu el mòdul de col·leccions que proporciona alguns contenidors que són útils en molts casos i ofereixen més funcions que les funcions definides anteriorment.
Mòdul Col·leccions
Es va introduir el mòdul de recollida de Python per millorar la funcionalitat dels tipus de dades integrats. Proporciona diversos contenidors, veurem cadascun d'ells amb detall.
Comptadors
Un comptador és una subclasse del diccionari. S'utilitza per mantenir el recompte dels elements en un iterable en forma de diccionari no ordenat on la clau representa l'element a l'iterable i el valor representa el recompte d'aquest element a l'iterable. Això és equivalent a una bossa o conjunt d'altres idiomes.
Exemple: Operacions de comptador de Python
Python 3
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)> |
>
>Sortida
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> OrderedDict
An OrderedDict també és una subclasse de diccionari, però a diferència d'un diccionari, recorda l'ordre en què es van inserir les claus.
Exemple: Operacions OrderedDict de Python
Python 3
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)> |
>
>Sortida
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 s'utilitza per proporcionar alguns valors per defecte per a la clau que no existeix i que mai genera un KeyError. Els seus objectes es poden inicialitzar mitjançant el mètode DefaultDict() passant el tipus de dades com a argument.
Nota: default_factory és una funció que proporciona el valor predeterminat per al diccionari creat. Si aquest paràmetre està absent, es genera KeyError.
Exemple: operacions Python DefaultDict
Python 3
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)> |
>
>Sortida
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> ChainMap
Un ChainMap encapsula molts diccionaris en una sola unitat i retorna una llista de diccionaris. Quan cal trobar una clau, es cerquen tots els diccionaris un per un fins que es troba la clau.
Exemple: Operacions Python ChainMap
Python 3
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'>])> |
>
>
Sortida
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
NamedTuple
A NamedTuple retorna un objecte de tupla amb noms per a cada posició que no tenen les tuples normals. Per exemple, considereu una tupla que anomena student on el primer element representa fname, el segon representa lname i el tercer element representa el DOB. Suposem que per cridar a fname en lloc de recordar la posició de l'índex, podeu cridar l'element utilitzant l'argument fname, llavors serà molt fàcil accedir a l'element tuples. Aquesta funcionalitat la proporciona NamedTuple.
Exemple: Operacions Python NamedTuple
Python 3
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)> |
>
>Sortida
The Student age using index is : 19 The Student name using keyname is : Nandini>
Dec
Deque (cua doblement acabada) és la llista optimitzada per a operacions d'afegir i pop més ràpides des dels dos costats del contenidor. Proporciona complexitat de temps O(1) per a operacions d'afegir i pop en comparació amb la llista amb complexitat de temps O(n).
Python Deque s'implementa mitjançant llistes doblement enllaçades, per tant, el rendiment per accedir a l'atzar als elements és O(n).
Exemple: Operacions Python Deque
Python 3
# 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)> |
df loc
>
>Sortida
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 és un contenidor semblant a un diccionari que actua com a embolcall al voltant dels objectes del diccionari. Aquest contenidor s'utilitza quan algú vol crear el seu propi diccionari amb alguna funcionalitat modificada o nova.
Exemple: Python UserDict
Python 3
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>)> |
>
>
Sortida
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Llista d'usuaris
UserList és un contenidor semblant a una llista que actua com a embolcall al voltant dels objectes de la llista. Això és útil quan algú vol crear la seva pròpia llista amb alguna funcionalitat modificada o addicional.
Exemples: Python UserList
Python 3
# 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()> |
>
>
Sortida
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
Cadena d'usuari
UserString és un contenidor semblant a una cadena i, igual que UserDict i UserList, actua com un embolcall al voltant dels objectes de cadena. S'utilitza quan algú vol crear les seves pròpies cadenes amb alguna funcionalitat modificada o addicional.
Exemple: Python UserString
Python 3
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)> |
>
>Sortida
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Ara, després d'estudiar totes les estructures de dades, veurem algunes estructures de dades avançades com ara pila, cua, gràfic, llista enllaçada, etc. que es poden utilitzar en Python Language.
Llista enllaçada
Una llista enllaçada és una estructura de dades lineal, en la qual els elements no s'emmagatzemen en ubicacions de memòria contigües. Els elements d'una llista enllaçada s'enllaçen mitjançant punters tal com es mostra a la imatge següent:
Una llista enllaçada es representa amb un punter al primer node de la llista enllaçada. El primer node s'anomena cap. Si la llista enllaçada està buida, el valor del capçalera és NULL. Cada node d'una llista consta d'almenys dues parts:
- Dades
- Punter (o referència) al següent node
Exemple: definició de llista enllaçada a Python
Python 3
# 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> |
>
>
Creem una llista enllaçada senzilla amb 3 nodes.
Python 3
# 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 |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Travessia de llista enllaçada
Al programa anterior, hem creat una llista enllaçada senzilla amb tres nodes. Recorrem la llista creada i imprimim les dades de cada node. Per a la travessa, escrivim una funció de propòsit general printList() que imprimeixi qualsevol llista determinada.
Python 3
# 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()> |
>
>Sortida
1 2 3>
Pila
A pila és una estructura de dades lineal que emmagatzema els elements de manera Últim entrant/Primer sortit (LIFO) o First-In/Last-Out (FILO). A la pila, s'afegeix un element nou en un extrem i només s'elimina un element d'aquest extrem. Les operacions d'inserció i supressió sovint s'anomenen push i pop.
Les funcions associades a la pila són:
- empty() – Retorna si la pila està buida – Complexitat temporal: O(1) size() – Retorna la mida de la pila – Complexitat temporal: O(1) top() – Retorna una referència a l'element superior de la pila – Complexitat temporal: O(1) push(a) – Insereix l'element 'a' a la part superior de la pila – Complexitat temporal: O(1) pop() – Elimina l'element superior de la pila – Complexitat temporal: O( 1)
Implementació de la pila de Python
La pila a Python es pot implementar de les maneres següents:
- llista
- Col·leccions.deque
- queue.LifoQueue
Implementació mitjançant List
La llista d'estructura de dades integrada de Python es pot utilitzar com a pila. En lloc de push(), append() s'utilitza per afegir elements a la part superior de la pila, mentre que pop() elimina l'element en ordre LIFO.
Python 3
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> |
>
>Sortida
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementació mitjançant collections.deque:
La pila de Python es pot implementar mitjançant la classe deque del mòdul de col·leccions. Es prefereix Deque a la llista en els casos en què necessitem operacions d'afegir i pop més ràpides des dels dos extrems del contenidor, ja que deque proporciona una complexitat de temps O(1) per a les operacions d'afegir i pop en comparació amb la llista que proporciona O (n) complexitat temporal.
Python 3
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> |
>
>Sortida
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementació mitjançant mòdul de cua
El mòdul de cua també té una cua LIFO, que bàsicament és una pila. Les dades s'insereixen a la cua mitjançant la funció put() i get() treu les dades de la cua.
Python 3
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())> |
>
>Sortida
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Cua
Com a pila, el cua és una estructura de dades lineal que emmagatzema elements de manera FIFO (First In First Out). Amb una cua, primer s'elimina l'element afegit menys recentment. Un bon exemple de la cua és qualsevol cua de consumidors per a un recurs on el consumidor que ha arribat primer és atès primer.
Les operacions associades a la cua són:
- Cua: afegeix un element a la cua. Si la cua està plena, aleshores es diu que és una condició de desbordament – Complexitat temporal: O(1) Decua: elimina un element de la cua. Els elements apareixen en el mateix ordre en què s'empenyen. Si la cua està buida, es diu que és una condició de desbordament inferior - Complexitat temporal: O(1) Front: Obteniu l'element frontal de la cua - Complexitat temporal: O (1) Posterior: Obteniu l'últim element de la cua - Complexitat temporal : O(1)
Implementació de la cua Python
La cua a Python es pot implementar de les maneres següents:
- llista
- col·leccions.deque
- cua.cua
Implementació mitjançant llista
En lloc d'enqueue() i dequeue(), s'utilitza la funció append() i pop().
Python 3
# 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> |
>
>Sortida
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementació mitjançant collections.deque
Deque es prefereix a la llista en els casos en què necessitem operacions d'afegir i pop més ràpides des dels dos extrems del contenidor, ja que deque proporciona una complexitat de temps O(1) per a les operacions d'afegir i pop en comparació amb la llista que proporciona O (n) complexitat temporal.
Python 3
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> |
>
>Sortida
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementació mitjançant el queue.Queue
caràcter a cadena java
queue.Queue(maxsize) inicialitza una variable a una mida màxima de maxsize. Una mida màxima de zero '0' significa una cua infinita. Aquesta cua segueix la regla FIFO.
Python 3
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())> |
>
>Sortida
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Cua de prioritats
Cues de prioritat són estructures de dades abstractes on cada dada/valor de la cua té una certa prioritat. Per exemple, a les companyies aèries, l'equipatge amb el títol Business o First class arriba abans que la resta. Priority Queue és una extensió de la cua amb les propietats següents.
- Un element amb prioritat alta es retira de la cua abans d'un element amb prioritat baixa.
- Si dos elements tenen la mateixa prioritat, es serveixen segons el seu ordre a la cua.
Python 3
# 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())> |
>
>Sortida
12 1 14 7 14 12 7 1>
Cua de pila (o heapq)
mòdul heapq a Python proporciona l'estructura de dades de pila que s'utilitza principalment per representar una cua de prioritat. La propietat d'aquesta estructura de dades a Python és que cada vegada que apareix l'element més petit de l'munt (min-heap). Sempre que s'empenyen o esclaten elements, es manté l'estructura de pila. L'element heap[0] també retorna l'element més petit cada vegada.
Admet l'extracció i inserció de l'element més petit en els temps O(log n).
Python 3
# 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))> |
>
>Sortida
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>
Arbre binari
Un arbre és una estructura de dades jeràrquica que s'assembla a la figura següent:
tree ---- j <-- root / f k / a h z <-- leaves>
El node superior de l'arbre s'anomena arrel, mentre que els nodes més baixos o els nodes sense fills s'anomenen nodes fulla. Els nodes que estan directament sota un node s'anomenen els seus fills i els nodes que estan directament a sobre d'alguna cosa s'anomenen els seus pares.
Un arbre binari és un arbre els elements del qual poden tenir gairebé dos fills. Com que cada element d'un arbre binari només pot tenir 2 fills, normalment els anomenem els fills esquerre i dret. Un node d'arbre binari conté les parts següents.
- Dades
- Punter al fill esquerre
- Apuntador al nen correcte
Exemple: Definició de classe de nodes
Python 3
# 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> |
>
>
Ara creem un arbre amb 4 nodes a Python. Suposem que l'estructura de l'arbre és com a continuació:
tree ---- 1 <-- root / 2 3 / 4>
Exemple: afegir dades a l'arbre
Python 3
# 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'''> |
>
>
Travessa d'arbres
Els arbres es poden travessar de diferents maneres. A continuació es mostren les maneres generalment utilitzades per travessar arbres. Considerem l'arbre següent:
tree ---- 1 <-- root / 2 3 / 4 5>
Primers recorreguts de profunditat:
- Inordre (esquerra, arrel, dreta): 4 2 5 1 3
- Preordenació (arrel, esquerra, dreta): 1 2 4 5 3
- Postordre (esquerra, dreta, arrel): 4 5 2 3 1
Inorde d'algorisme (arbre)
- Travessa el subarbre esquerre, és a dir, crida a Inorder (subarbre esquerre)
- Visita l'arrel.
- Travessa el subarbre dret, és a dir, crida a Inorder (subarbre dret)
Preordenació d'algoritmes (arbre)
- Visita l'arrel.
- Travessa el subarbre esquerre, és a dir, crida a Preorder (subarbre esquerre)
- Travessa el subarbre dret, és a dir, crida a Preorder (subarbre dret)
Algoritme Ordre postal (arbre)
- Travessa el subarbre esquerre, és a dir, crida a Postorder (subarbre esquerre)
- Travessa el subarbre dret, és a dir, crida a Postorder (subarbre dret)
- Visita l'arrel.
Python 3
# 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)> |
>
>Sortida
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>
Complexitat temporal - O(n)
Travessia d'ordre d'amplada o de primer nivell
Recorregut per ordres a nivell d'un arbre és el primer recorregut de l'amplada per a l'arbre. El recorregut per ordre de nivell de l'arbre anterior és 1 2 3 4 5.
Per a cada node, primer, es visita el node i després els seus nodes fills es posen en una cua FIFO. A continuació es mostra l'algorisme per al mateix:
- Creeu una cua buida q
- temp_node = arrel /*començar des de l'arrel*/
- Bucle mentre temp_node no és NULL
- imprimir temp_node->dades.
- Col·loqueu a la cua els fills de temp_node (primer els fills esquerre i després dret) a q
- Treu la cua d'un node de q
Python 3
# 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)> |
>
>Sortida
Level Order Traversal of binary tree is - 1 2 3 4 5>
Complexitat temporal: O(n)
Gràfic
A gràfic és una estructura de dades no lineal que consta de nodes i arestes. Els nodes de vegades també s'anomenen vèrtexs i les arestes són línies o arcs que connecten dos nodes qualsevol del gràfic. Més formalment, un gràfic es pot definir com un gràfic que consisteix en un conjunt finit de vèrtexs (o nodes) i un conjunt d'arestes que connecten un parell de nodes.
En el gràfic anterior, el conjunt de vèrtexs V = {0,1,2,3,4} i el conjunt d'arestes E = {01, 12, 23, 34, 04, 14, 13}.
Les dues següents són les representacions més utilitzades d'un gràfic.
- Matriu d'adjacència
- Llista d'adjacència
Matriu d'adjacència
La matriu d'adjacència és una matriu 2D de mida V x V on V és el nombre de vèrtexs d'un gràfic. Sigui la matriu 2D adj[][], una ranura adj[i][j] = 1 indica que hi ha una vora des del vèrtex i fins al vèrtex j. La matriu d'adjacència per a un gràfic no dirigit és sempre simètrica. La matriu d'adjacència també s'utilitza per representar gràfics ponderats. Si adj[i][j] = w, aleshores hi ha una aresta des del vèrtex i fins al vèrtex j amb pes w.
Python 3
# 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())> |
>
>
Sortida
Vèrtexs del gràfic
['a', 'b', 'c', 'd', 'e', 'f']
Vores del gràfic
[('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)]
Matriu d'adjacència del gràfic
[[-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]]
Llista d'adjacència
S'utilitza una matriu de llistes. La mida de la matriu és igual al nombre de vèrtexs. Sigui la matriu una matriu[]. Una matriu d'entrada[i] representa la llista de vèrtexs adjacents al vèrtex i-è. Aquesta representació també es pot utilitzar per representar un gràfic ponderat. Els pesos de les vores es poden representar com a llistes de parells. A continuació es mostra la representació de la llista d'adjacència del gràfic anterior.
Python 3
# 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()> |
>
>Sortida
Adjacency list of vertex 0 head ->4 -> 1 Llista d'adjacència del capçalera del vèrtex 1 -> 4 -> 3 -> 2 -> 0 Llista d'adjacència del capçal del vèrtex 2 -> 3 -> 1 Llista d'adjacència del capçal del vèrtex 3 -> 4 -> 2 -> 1 Adjacència llista de capçalera del vèrtex 4 -> 3 -> 1 -> 0>
Travessia gràfica
Breadth-First Search o BFS
Travessia de l'amplada primer perquè un gràfic és similar a l'amplada-primer recorregut d'un arbre. L'únic problema aquí és que, a diferència dels arbres, els gràfics poden contenir cicles, de manera que podem tornar al mateix node. Per evitar processar un node més d'una vegada, utilitzem una matriu booleana visitada. Per simplificar, s'assumeix que tots els vèrtexs són accessibles des del vèrtex inicial.
Per exemple, en el gràfic següent, comencem el recorregut des del vèrtex 2. Quan arribem al vèrtex 0, busquem tots els seus vèrtexs adjacents. 2 també és un vèrtex adjacent de 0. Si no marquem els vèrtexs visitats, llavors 2 es processarà de nou i es convertirà en un procés no final. Un recorregut d'amplada-primer del gràfic següent és 2, 0, 3, 1.
Python 3
# 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> |
>
>Sortida
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Complexitat temporal: O(V+E) on V és el nombre de vèrtexs del gràfic i E és el nombre d'arestes del gràfic.
Cerca en profunditat o DFS
Primer recorregut de profunditat perquè un gràfic és similar a la profunditat primer recorregut d'un arbre. L'únic problema aquí és que, a diferència dels arbres, els gràfics poden contenir cicles, un node es pot visitar dues vegades. Per evitar processar un node més d'una vegada, utilitzeu una matriu booleana visitada.
Algorisme:
- Creeu una funció recursiva que prengui l'índex del node i una matriu visitada.
- Marqueu el node actual com a visitat i imprimiu el node.
- Travessa tots els nodes adjacents i no marcats i crida a la funció recursiva amb l'índex del node adjacent.
Python 3
# 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>)> |
>
>Sortida
Following is DFS from (starting from vertex 2) 2 0 1 3>
Complexitat temporal: O(V + E), on V és el nombre de vèrtexs i E és el nombre d'arestes del gràfic.