Strutture dati sono un modo di organizzare i dati in modo che sia possibile accedervi in modo più efficiente a seconda della situazione. Le strutture dati sono i fondamenti di qualsiasi linguaggio di programmazione attorno al quale è costruito un programma. Python aiuta ad apprendere i fondamenti di queste strutture dati in modo più semplice rispetto ad altri linguaggi di programmazione.
In questo articolo discuteremo delle strutture dati nel linguaggio di programmazione Python e di come sono correlate ad alcune strutture dati specifiche integrate come tuple di elenchi, dizionari, ecc., nonché ad alcune strutture dati avanzate come alberi, grafici, ecc.
Elenchi
Gli elenchi Python sono proprio come gli array, dichiarati in altri linguaggi che sono una raccolta ordinata di dati. È molto flessibile poiché non è necessario che gli elementi di un elenco siano dello stesso tipo.
L'implementazione di Python List è simile a Vectors in C++ o ArrayList in JAVA. L'operazione costosa è inserire o eliminare l'elemento dall'inizio della Lista poiché è necessario spostare tutti gli elementi. L'inserimento e la cancellazione alla fine della lista possono diventare costosi anche nel caso in cui la memoria preallocata si riempia.
Possiamo creare un elenco in Python come mostrato di seguito.
Esempio: creazione dell'elenco Python
Python3
List> => [>1>,>2>,>3>,>'GFG'>,>2.3>]> print>(>List>)> |
>
>Produzione
[1, 2, 3, 'GFG', 2.3]>
È possibile accedere agli elementi dell'elenco tramite l'indice assegnato. Nell'indice iniziale dell'elenco Python, la sequenza è 0 e l'indice finale è (se sono presenti N elementi) N-1.
Esempio: operazioni su elenchi Python
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>])> |
>
come aprire un file con java
>Produzione
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>
Dizionario
Dizionario Python è come le tabelle hash in qualsiasi altro linguaggio con la complessità temporale di O(1). Si tratta di una raccolta non ordinata di valori di dati, utilizzata per archiviare valori di dati come una mappa, che, a differenza di altri tipi di dati che contengono solo un singolo valore come elemento, Dictionary contiene la coppia chiave:valore. Il valore-chiave è fornito nel dizionario per renderlo più ottimizzato.
L'indicizzazione del dizionario Python viene eseguita con l'aiuto delle chiavi. Questi sono di qualsiasi tipo hashable, ovvero un oggetto che non può mai cambiare come stringhe, numeri, tuple, ecc. Possiamo creare un dizionario utilizzando parentesi graffe ({}) o comprensione del dizionario .
Esempio: operazioni del dizionario Python
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)> |
>
>Produzione
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}> Tupla
Tupla Python è una raccolta di oggetti Python molto simile a un elenco ma le tuple sono di natura immutabile, ovvero gli elementi nella tupla non possono essere aggiunti o rimossi una volta creati. Proprio come una Lista, anche una Tupla può contenere elementi di vario tipo.
In Python, le tuple vengono create inserendo una sequenza di valori separati da 'virgola' con o senza l'uso di parentesi per il raggruppamento della sequenza di dati.
Nota: Le tuple possono anche essere create con un singolo elemento, ma è un po' complicato. Avere un elemento tra parentesi non è sufficiente, deve esserci una 'virgola' finale per renderlo una tupla.
Esempio: operazioni su tuple 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>])> |
>
>Produzione
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> Impostato
Insieme del pitone è una raccolta non ordinata di dati che è mutabile e non consente alcun elemento duplicato. I set vengono fondamentalmente utilizzati per includere il test di appartenenza e l'eliminazione delle voci duplicate. La struttura dei dati utilizzata in questo caso è l'hashing, una tecnica popolare per eseguire in media l'inserimento, l'eliminazione e l'attraversamento in O(1).
Se sono presenti più valori nella stessa posizione di indice, il valore viene aggiunto a quella posizione di indice per formare un elenco collegato. In, i set CPython vengono implementati utilizzando un dizionario con variabili fittizie, in cui gli esseri chiave vengono impostati dai membri con maggiori ottimizzazioni in base alla complessità temporale.
Imposta implementazione:
Set con numerose operazioni su una singola HashTable:
Esempio: operazioni sugli insiemi di 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>)> |
>
>Produzione
Set with the use of Mixed Values {1, 2, 'Geeks', 4, 6, 'For'} Elements of set: 1 2 Geeks 4 6 For True> Set congelati
I set congelati in Python sono oggetti immutabili che supportano solo metodi e operatori che producono un risultato senza influenzare il set o i set congelati a cui vengono applicati. Mentre gli elementi di un set possono essere modificati in qualsiasi momento, gli elementi del set congelato rimangono gli stessi dopo la creazione.
Se non vengono passati parametri, restituisce un frozenset vuoto.
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')> |
>
>Produzione
Normal Set {'a', 'c', 'b'} Frozen Set frozenset({'g', 'e', 'f'})> Corda
Le stringhe Python sono array di byte che rappresentano caratteri Unicode. In termini più semplici, una stringa è un array immutabile di caratteri. Python non ha un tipo di dati carattere, un singolo carattere è semplicemente una stringa con una lunghezza pari a 1.
Nota: Poiché le stringhe sono immutabili, la modifica di una stringa comporterà la creazione di una nuova copia.
Esempio: operazioni su stringhe 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>])> |
>
>Produzione
Creating String: Welcome to GeeksForGeeks First character of String is: W Last character of String is: s>
Bytearray
Python Bytearray fornisce una sequenza mutabile di numeri interi nell'intervallo 0 <= x < 256.
Esempio: operazioni su bytearray Python
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)> |
>
>Produzione
Creating Bytearray: bytearray(b'x0cx08x19x02') Accessing Elements: 8 After Modifying: bytearray(b'x0cx03x19x02') After Adding Elements: bytearray(b'x0cx03x19x02x1e')>
Fino ad ora abbiamo studiato tutte le strutture dati integrate nel nucleo di Python. Ora immergiamoci più in profondità in Python e vediamo il modulo delle collezioni che fornisce alcuni contenitori utili in molti casi e forniscono più funzionalità rispetto alle funzioni sopra definite.
Modulo Collezioni
Il modulo di raccolta Python è stato introdotto per migliorare la funzionalità dei tipi di dati integrati. Fornisce vari contenitori, vediamoli ciascuno nel dettaglio.
Contatori
Un contatore è una sottoclasse del dizionario. Viene utilizzato per mantenere il conteggio degli elementi in un iterabile sotto forma di un dizionario non ordinato in cui la chiave rappresenta l'elemento nell'iterabile e il valore rappresenta il conteggio di quell'elemento nell'iterabile. Ciò equivale a un sacchetto o un multiset di altre lingue.
Esempio: operazioni contatore 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)> |
>
>Produzione
Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1})> OrdinatoDict
UN OrdinatoDict è anch'esso una sottoclasse dei dizionari ma a differenza di un dizionario ricorda l'ordine in cui sono state inserite le chiavi.
Esempio: operazioni Python OrderedDict
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)> |
>
>Produzione
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 viene utilizzato per fornire alcuni valori predefiniti per la chiave che non esiste e non solleva mai un KeyError. I suoi oggetti possono essere inizializzati utilizzando il metodo DefaultDict() passando il tipo di dati come argomento.
Nota: default_factory è una funzione che fornisce il valore predefinito per il dizionario creato. Se questo parametro è assente viene sollevata l'eccezione KeyError.
Esempio: operazioni 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)> |
>
>Produzione
defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2})> ChainMap
Una ChainMap incapsula molti dizionari in una singola unità e restituisce un elenco di dizionari. Quando è necessario trovare una chiave, tutti i dizionari vengono cercati uno per uno finché non viene trovata la chiave.
Esempio: operazioni 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'>])> |
>
>
Produzione
ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1> KeyError: 'g'>
NamedTuple
UN NamedTuple restituisce un oggetto tupla con nomi per ciascuna posizione che mancano alle tuple ordinarie. Ad esempio, considera una tupla di nomi student in cui il primo elemento rappresenta fname, il secondo rappresenta lname e il terzo elemento rappresenta il DOB. Supponiamo che per chiamare fname invece di ricordare la posizione dell'indice puoi effettivamente chiamare l'elemento usando l'argomento fname, quindi sarà davvero facile accedere all'elemento tuple. Questa funzionalità è fornita da NamedTuple.
Esempio: operazioni 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)> |
>
>Produzione
The Student age using index is : 19 The Student name using keyname is : Nandini>
Riguardo a cosa
Deque (coda a doppia terminazione) è l'elenco ottimizzato per operazioni di aggiunta e pop più rapide da entrambi i lati del contenitore. Fornisce una complessità temporale O(1) per le operazioni di aggiunta e estrazione rispetto all'elenco con complessità temporale O(n).
Python Deque è implementato utilizzando elenchi doppiamente collegati, pertanto la prestazione per l'accesso casuale agli elementi è O(n).
Esempio: operazioni di deque Python
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)> |
git aggiungi tutto
>
>Produzione
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 è un contenitore simile a un dizionario che funge da wrapper attorno agli oggetti del dizionario. Questo contenitore viene utilizzato quando qualcuno desidera creare il proprio dizionario con alcune funzionalità modificate o nuove.
Esempio: 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>)> |
>
>
Produzione
Original Dictionary {'a': 1, 'b': 2, 'c': 3}> RuntimeError: Deletion not allowed>
Lista degli utenti
UserList è un contenitore simile a un elenco che funge da wrapper attorno agli oggetti dell'elenco. Ciò è utile quando qualcuno vuole creare il proprio elenco con alcune funzionalità modificate o aggiuntive.
Esempi: Elenco utenti Python
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()> |
>
>
Produzione
Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5]>
RuntimeError: Deletion not allowed>
Stringautente
UserString è un contenitore simile a una stringa e, proprio come UserDict e UserList, funge da wrapper attorno agli oggetti stringa. Viene utilizzato quando qualcuno desidera creare le proprie stringhe con alcune funzionalità modificate o aggiuntive.
Esempio: stringa utente Python
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)> |
>
>Produzione
Original String: Geeks String After Appending: Geekss String after Removing: Gkss>
Ora, dopo aver studiato tutte le strutture dati, vediamo alcune strutture dati avanzate come stack, coda, grafico, elenco collegato, ecc. che possono essere utilizzate in linguaggio Python.
Lista collegata
Una lista concatenata è una struttura dati lineare, in cui gli elementi non sono memorizzati in posizioni di memoria contigue. Gli elementi in un elenco collegato sono collegati utilizzando puntatori come mostrato nell'immagine seguente:
Una lista concatenata è rappresentata da un puntatore al primo nodo della lista concatenata. Il primo nodo è chiamato testa. Se l'elenco collegato è vuoto, il valore dell'intestazione è NULL. Ogni nodo in un elenco è composto da almeno due parti:
- Dati
- Puntatore (o riferimento) al nodo successivo
Esempio: definizione di un elenco collegato in Python
Python3
# Node class> class> Node:> ># Function to initialize the node object> >def> __init__(>self>, data):> >self>.data>=> data># Assign data> >self>.>next> => None> # Initialize> ># next as null> # Linked List class> class> LinkedList:> > ># Function to initialize the Linked> ># List object> >def> __init__(>self>):> >self>.head>=> None> |
>
>
Creiamo una semplice lista concatenata con 3 nodi.
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| nullo | | 3| null |> >+----+------+ +----+------+ +----+------+> >'''> >second.>next> => third;># Link second node with the third node> >'''> >Now next of second Node refers to third. So all three> >nodes are linked.> >list.head second third> >| | |> >| | |> >+----+------+ +----+------+ +----+------+> >| 1 | o-------->| 2| o-------->| 3| null |> >+----+------+ +----+------+ +----+------+> >'''> |
>
>
Attraversamento di elenchi collegati
Nel programma precedente abbiamo creato una semplice lista concatenata con tre nodi. Attraversiamo l'elenco creato e stampiamo i dati di ciascun nodo. Per l'attraversamento, scriviamo una funzione generica printList() che stampa qualsiasi elenco specificato.
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()> |
>
>Produzione
1 2 3>
Pila
UN pila è una struttura di dati lineare che memorizza gli elementi in modalità Last-In/First-Out (LIFO) o First-In/Last-Out (FILO). Nello stack, un nuovo elemento viene aggiunto a un'estremità e un elemento viene rimosso solo da quell'estremità. Le operazioni di inserimento ed eliminazione sono spesso chiamate push e pop.
Le funzioni associate allo stack sono:
- empty() – Restituisce se lo stack è vuoto – Complessità temporale: O(1) size() – Restituisce la dimensione dello stack – Complessità temporale: O(1) top() – Restituisce un riferimento all'elemento più in alto dello stack – Complessità temporale: O(1) push(a) – Inserisce l'elemento 'a' in cima allo stack – Complessità temporale: O(1) pop() – Elimina l'elemento più in alto dello stack – Complessità temporale: O( 1)
Implementazione dello stack Python
Lo stack in Python può essere implementato nei seguenti modi:
- elenco
- Collezioni.deque
- coda.LifoQueue
Implementazione utilizzando List
L'elenco delle strutture dati integrate in Python può essere utilizzato come uno stack. Invece di push(), append() viene utilizzato per aggiungere elementi in cima allo stack mentre pop() rimuove l'elemento in ordine 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> |
>
>Produzione
Initial stack ['g', 'f', 'g'] Elements popped from stack: g f g Stack after elements are popped: []>
Implementazione utilizzandocollections.deque:
Lo stack Python può essere implementato utilizzando la classe deque dal modulocollections. Deque è preferito alla lista nei casi in cui abbiamo bisogno di operazioni di accodamento e pop più veloci da entrambe le estremità del contenitore, poiché deque fornisce una complessità temporale O(1) per le operazioni di accodamento e pop rispetto a lista che fornisce O(n) complessità temporale.
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> |
>
>Produzione
Initial stack: deque(['g', 'f', 'g']) Elements popped from stack: g f g Stack after elements are popped: deque([])>
Implementazione utilizzando il modulo coda
Il modulo coda ha anche una coda LIFO, che è fondamentalmente uno stack. I dati vengono inseriti nella coda utilizzando la funzione put() e get() estrae i dati dalla coda.
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())> |
>
>Produzione
0 Full: True Size: 3 Elements popped from the stack g f g Empty: True>
Coda
Come pila, il coda è una struttura dati lineare che memorizza gli elementi in modalità FIFO (First In First Out). Con una coda, l'elemento aggiunto meno di recente viene rimosso per primo. Un buon esempio di coda è qualsiasi coda di consumatori per una risorsa in cui il consumatore arrivato per primo viene servito per primo.
Le operazioni associate alla coda sono:
- Accoda: aggiunge un elemento alla coda. Se la coda è piena, si parla di condizione di overflow – Complessità temporale: O(1) Dequeue: rimuove un elemento dalla coda. Gli elementi vengono estratti nello stesso ordine in cui vengono inseriti. Se la coda è vuota, si dice che sia una condizione di underflow – Complessità temporale: O(1) Front: prendi l'elemento in primo piano dalla coda – Complessità temporale: O(1) Rear: prendi l'ultimo elemento dalla coda – Complessità temporale : O(1)
Implementazione della coda Python
La coda in Python può essere implementata nei seguenti modi:
- elenco
- collezioni.deque
- coda.coda
Implementazione utilizzando l'elenco
Invece di enqueue() e dequeue(), vengono utilizzate le funzioni append() e 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> |
>
>Produzione
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []>
Implementazione utilizzandocollection.deque
Deque è preferito alla lista nei casi in cui abbiamo bisogno di operazioni di accodamento e pop più veloci da entrambe le estremità del contenitore, poiché deque fornisce una complessità temporale O(1) per le operazioni di accodamento e pop rispetto a lista che fornisce O(n) complessità temporale.
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> |
>
>Produzione
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])>
Implementazione utilizzando la coda.Queue
come eseguire uno script in Linux
coda.Queue(maxsize) inizializza una variabile su una dimensione massima di maxsize. Una dimensione massima pari a zero '0' indica una coda infinita. Questa coda segue la regola 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())> |
>
>Produzione
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False>
Coda prioritaria
Code prioritarie sono strutture di dati astratte in cui ogni dato/valore in coda ha una certa priorità. Ad esempio, nelle compagnie aeree, i bagagli con il titolo Business o First class arrivano prima degli altri. Priority Queue è un'estensione della coda con le seguenti proprietà.
- Un elemento con priorità alta viene rimosso dalla coda prima di un elemento con priorità bassa.
- Se due elementi hanno la stessa priorità, verranno serviti secondo il loro ordine in coda.
Python3
# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(>object>):> >def> __init__(>self>):> >self>.queue>=> []> >def> __str__(>self>):> >return> ' '>.join([>str>(i)>for> i>in> self>.queue])> ># for checking if the queue is empty> >def> isEmpty(>self>):> >return> len>(>self>.queue)>=>=> 0> ># for inserting an element in the queue> >def> insert(>self>, data):> >self>.queue.append(data)> ># for popping an element based on Priority> >def> delete(>self>):> >try>:> >max> => 0> >for> i>in> range>(>len>(>self>.queue)):> >if> self>.queue[i]>>self>.queue[>max>]:> >max> => i> >item>=> self>.queue[>max>]> >del> self>.queue[>max>]> >return> item> >except> IndexError:> >print>()> >exit()> if> __name__>=>=> '__main__'>:> >myQueue>=> PriorityQueue()> >myQueue.insert(>12>)> >myQueue.insert(>1>)> >myQueue.insert(>14>)> >myQueue.insert(>7>)> >print>(myQueue)> >while> not> myQueue.isEmpty():> >print>(myQueue.delete())> |
>
>Produzione
12 1 14 7 14 12 7 1>
Coda heap (o heapq)
modulo heapq in Python fornisce la struttura dei dati heap utilizzata principalmente per rappresentare una coda con priorità. La proprietà di questa struttura dati in Python è che ogni volta viene estratto l'elemento heap più piccolo (min-heap). Ogni volta che gli elementi vengono spinti o estratti, la struttura dell'heap viene mantenuta. L'elemento heap[0] restituisce ogni volta anche l'elemento più piccolo.
Supporta l'estrazione e l'inserimento dell'elemento più piccolo nei tempi 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))> |
>
>Produzione
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>
Albero binario
Un albero è una struttura di dati gerarchica simile alla figura seguente:
tree ---- j <-- root / f k / a h z <-- leaves>
Il nodo più in alto dell'albero è chiamato radice mentre i nodi più in basso o i nodi senza figli sono chiamati nodi foglia. I nodi che sono direttamente sotto un nodo sono chiamati i suoi figli e i nodi che sono direttamente sopra qualcosa sono chiamati il suo genitore.
Un albero binario è un albero i cui elementi possono avere quasi due figli. Poiché ogni elemento in un albero binario può avere solo 2 figli, in genere li chiamiamo figlio sinistro e figlio destro. Un nodo di albero binario contiene le seguenti parti.
- Dati
- Puntatore al bambino sinistro
- Puntatore al bambino giusto
Esempio: definizione della classe del nodo
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> |
>
>
Ora creiamo un albero con 4 nodi in Python. Supponiamo che la struttura ad albero sia simile alla seguente:
tree ---- 1 <-- root / 2 3 / 4>
Esempio: aggiunta di dati all'albero
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'''> |
>
>
Attraversamento degli alberi
Gli alberi possono essere attraversati in diversi modi. Di seguito sono riportati i modi generalmente utilizzati per attraversare gli alberi. Consideriamo l'albero sottostante:
tree ---- 1 <-- root / 2 3 / 4 5>
Prime traversate in profondità:
- In ordine (Sinistra, Radice, Destra): 4 2 5 1 3
- Preordine (radice, sinistra, destra): 1 2 4 5 3
- Postorder (Sinistra, Destra, Radice): 4 5 2 3 1
Algoritmo in ordine (albero)
- Attraversa il sottoalbero sinistro, ovvero chiama Inorder(left-subtree)
- Visita la radice.
- Attraversa il sottoalbero destro, ovvero chiama Inorder(right-subtree)
Preordine dell'algoritmo (albero)
- Visita la radice.
- Attraversa il sottoalbero sinistro, ovvero chiama Preorder(left-subtree)
- Attraversa il sottoalbero destro, ovvero chiama Preorder(right-subtree)
Algoritmo Vaglia postale(albero)
- Attraversa il sottoalbero sinistro, ovvero chiama Postorder(sottoalbero sinistro)
- Attraversa il sottoalbero destro, ovvero chiama Postorder(right-subtree)
- Visita la radice.
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)> |
>
>Produzione
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>
Complessità temporale – O(n)
Attraversamento dell'ordine di ampiezza o di livello
Attraversamento dell'ordine di livello di un albero è l'attraversamento in ampiezza per l'albero. L'attraversamento dell'ordine di livello dell'albero sopra è 1 2 3 4 5.
Per ciascun nodo, prima viene visitato il nodo e poi i suoi nodi figli vengono inseriti in una coda FIFO. Di seguito è riportato l'algoritmo per lo stesso:
- Creare una coda vuota q
- nodo_temp = root /*inizia da root*/
- Ciclo mentre temp_node non è NULL
- stampa nodo_temp->dati.
- Accoda i figli di temp_node (prima quelli a sinistra, poi quelli a destra) a q
- Togliere dalla coda un nodo da q
Python3
# Python program to print level> # order traversal using Queue> # A node structure> class> Node:> > ># A utility function to create a new node> >def> __init__(>self> ,key):> >self>.data>=> key> >self>.left>=> None> >self>.right>=> None> # Iterative Method to print the> # height of a binary tree> def> printLevelOrder(root):> > ># Base Case> >if> root>is> None>:> >return> > ># Create an empty queue> ># for level order traversal> >queue>=> []> ># Enqueue Root and initialize height> >queue.append(root)> >while>(>len>(queue)>>0>):> > ># Print front of queue and> ># remove it from queue> >print> (queue[>0>].data)> >node>=> queue.pop(>0>)> ># Enqueue left child> >if> node.left>is> not> None>:> >queue.append(node.left)> ># Enqueue right child> >if> node.right>is> not> None>:> >queue.append(node.right)> # Driver Program to test above function> root>=> Node(>1>)> root.left>=> Node(>2>)> root.right>=> Node(>3>)> root.left.left>=> Node(>4>)> root.left.right>=> Node(>5>)> print> (>'Level Order Traversal of binary tree is -'>)> printLevelOrder(root)> |
>
>Produzione
Level Order Traversal of binary tree is - 1 2 3 4 5>
Complessità temporale: O(n)
Grafico
UN grafico è una struttura dati non lineare costituita da nodi e spigoli. I nodi sono talvolta indicati anche come vertici e gli spigoli sono linee o archi che collegano due nodi qualsiasi nel grafico. Più formalmente un grafico può essere definito come un grafico costituito da un insieme finito di vertici (o nodi) e un insieme di archi che collegano una coppia di nodi.
Nel grafico sopra, l'insieme dei vertici V = {0,1,2,3,4} e l'insieme degli archi E = {01, 12, 23, 34, 04, 14, 13}.
Le due seguenti sono le rappresentazioni più comunemente utilizzate di un grafico.
- Matrice di adiacenza
- Elenco delle adiacenze
Matrice di adiacenza
La matrice di adiacenza è una matrice 2D di dimensione V x V dove V è il numero di vertici in un grafico. Sia l'array 2D adj[][], uno slot adj[i][j] = 1 indica che esiste un bordo dal vertice i al vertice j. La matrice di adiacenza per un grafo non orientato è sempre simmetrica. La matrice di adiacenza viene utilizzata anche per rappresentare grafici ponderati. Se adj[i][j] = w, allora esiste un arco dal vertice i al vertice j con peso 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())> |
>
>
Produzione
Vertici del grafico
['a B c D e F']
Bordi del grafico
[('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)]
Matrice di adiacenza del grafico
[[-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]]
Elenco delle adiacenze
Viene utilizzata una serie di elenchi. La dimensione dell'array è uguale al numero di vertici. Lascia che l'array sia un array[]. Una voce array[i] rappresenta l'elenco dei vertici adiacenti all'i-esimo vertice. Questa rappresentazione può essere utilizzata anche per rappresentare un grafico ponderato. I pesi degli archi possono essere rappresentati come elenchi di coppie. Di seguito è riportata la rappresentazione dell'elenco di adiacenza del grafico sopra.
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()> |
>
>Produzione
Adjacency list of vertex 0 head ->4 -> 1 Elenco di adiacenze della testa del vertice 1 -> 4 -> 3 -> 2 -> 0 Elenco di adiacenze della testa del vertice 2 -> 3 -> 1 Elenco di adiacenze della testa del vertice 3 -> 4 -> 2 -> 1 Adiacenza elenco dei vertici 4 testa -> 3 -> 1 -> 0>
Attraversamento del grafico
Ricerca in ampiezza o BFS
Traversata in ampiezza poiché un grafico è simile all'attraversamento in larghezza di un albero. L'unico problema qui è che, a differenza degli alberi, i grafici possono contenere cicli, quindi potremmo ritrovarci di nuovo sullo stesso nodo. Per evitare di elaborare un nodo più di una volta, utilizziamo un array visitato booleano. Per semplicità si assume che tutti i vertici siano raggiungibili dal vertice iniziale.
Ad esempio, nel grafico seguente, iniziamo l'attraversamento dal vertice 2. Quando arriviamo al vertice 0, cerchiamo tutti i suoi vertici adiacenti. 2 è anche un vertice adiacente di 0. Se non contrassegniamo i vertici visitati, 2 verrà elaborato nuovamente e diventerà un processo non terminato. Una traversata in ampiezza del grafico seguente è 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> |
>
>Produzione
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Complessità temporale: O(V+E) dove V è il numero di vertici nel grafico ed E è il numero di archi nel grafico.
Prima ricerca in profondità o DFS
Prima traversata in profondità per un grafico è simile alla prima traversata in profondità di un albero. L'unico problema qui è che, a differenza degli alberi, i grafici possono contenere cicli e un nodo può essere visitato due volte. Per evitare di elaborare un nodo più di una volta, utilizzare un array visitato booleano.
Algoritmo:
- Crea una funzione ricorsiva che accetta l'indice del nodo e un array visitato.
- Contrassegna il nodo corrente come visitato e stampa il nodo.
- Attraversa tutti i nodi adiacenti e non contrassegnati e chiama la funzione ricorsiva con l'indice del nodo adiacente.
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>)> |
>
>Produzione
Following is DFS from (starting from vertex 2) 2 0 1 3>
Complessità temporale: O(V + E), dove V è il numero di vertici ed E è il numero di archi nel grafico.