Aquest tutorial és una guia amigable per a principiants aprenentatge d'estructures de dades i algorismes utilitzant Python. En aquest article, parlarem de les estructures de dades integrades, com ara llistes, tuples, diccionaris, etc., i algunes estructures de dades definides per l'usuari, com ara llistes enllaçades , arbres , gràfics , etc. i algorismes de recorregut i de cerca i ordenació amb l'ajuda d'exemples i preguntes pràctiques bons i ben explicats.

Llistes

Llistes de Python són col·leccions ordenades de dades igual que les matrius en altres llenguatges de programació. Permet diferents tipus d'elements a la llista. 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.

Exemple: creació d'una llista de Python

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

[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, una seqüència és 0 i l'índex final és (si hi ha N elements) N-1.

Exemple: Operacions de llista de Python

# Creating a List with # the use of multiple values List = ['Geeks', 'For', 'Geeks'] print('
List containing multiple values: ') print(List) # Creating a Multi-Dimensional List # (By Nesting a list inside a List) List2 = [['Geeks', 'For'], ['Geeks']] print('
Multi-Dimensional List: ') print(List2) # accessing a element from the # list using index number print('Accessing element from the list') print(List[0]) print(List[2]) # accessing a element using # negative indexing print('Accessing element using negative indexing') # print the last element of list print(List[-1]) # print the third last element of list print(List[-3])>

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

Tuple

Tuples Python són semblants a les llistes però les tuples ho són immutable a la naturalesa, és a dir, un cop creat no es pot modificar. 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: Per crear una tupla d'un element ha d'haver una coma al final. Per exemple, (8,) crearà una tupla que contingui 8 com a element.

Exemple: Operacions de tuple Python

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

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 mutable que no permet cap duplicació. 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

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

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

Conjunts congelats

Conjunts congelats a 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ó.

Exemple: conjunt Python Frozen

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

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

Corda

Cordes de Python és la matriu immutable de bytes que representen caràcters Unicode. 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

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

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

Diccionari

Diccionari Python és una col·lecció de dades no ordenada que emmagatzema dades en el format de parella clau:valor. És com taules hash en qualsevol altre idioma amb la complexitat temporal de O(1). 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ó de diccionari.

Exemple: Operacions del diccionari Python

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

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

Matriu

Una matriu és una matriu 2D on cada element és estrictament de la mateixa mida. Per crear una matriu farem servir el paquet NumPy .

Exemple: operacions de matriu Python NumPy

import numpy as np a = np.array([[1,2,3,4],[4,55,1,2], [8,3,20,19],[11,2,22,21]]) m = np.reshape(a,(4, 4)) print(m) # Accessing element print('
Accessing Elements') print(a[1]) print(a[2][0]) # Adding Element m = np.append(m,[[1, 15,13,11]],0) print('
Adding Element') print(m) # Deleting Element m = np.delete(m,[1],0) print('
Deleting Element') print(m)>

Sortida

[[ 1 2 3 4]  [ 4 55 1 2]  [ 8 3 20 19]  [11 2 22 21]] Accessing Elements [ 4 55 1 2] 8 Adding Element [[ 1 2 3 4]  [ 4 55 1 2]  [ 8 3 20 19]  [11 2 22 21]  [ 1 15 13 11]] Deleting Element [[ 1 2 3 4]  [ 8 3 20 19]  [11 2 22 21]  [ 1 15 13 11]]>

Bytearray

Python Bytearray proporciona una seqüència mutable de nombres enters en el rang 0 <= x < 256.

Exemple: Operacions de Python Bytearray

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

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

Llista enllaçada

A 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

# 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.

# 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 llist = LinkedList() llist.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  llist.head second third  | | |  | | |  +----+------+ +----+------+ +----+------+  | 1 | None | | 2 | None | | 3 | None |  +----+------+ +----+------+ +----+------+  ''' llist.head.next = second; # Link first node with second  '''  Now next of first Node refers to second. So they  both are linked.  llist.head second third  | | |  | | |  +----+------+ +----+------+ +----+------+  | 1 | o-------->| 2 | nul | | 3 | nul |  +----+------+ +----+------+ +----+------+ ''' segon.següent = tercer ; # Enllaceu el segon node amb el tercer node ''' Ara el següent del segon node fa referència al tercer. Així, els tres nodes estan enllaçats.  llist.head segon terç | | |  | | |  +----+------+ +----+------+ +----+------+ | 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.

# 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 llist = LinkedList() llist.head = Node(1) second = Node(2) third = Node(3) llist.head.next = second; # Link first node with second second.next = third; # Link second node with the third node llist.printList()>

1 2 3>

Més articles a la llista enllaçada

• Inserció de llista enllaçada
• Supressió de la llista enllaçada (eliminació d'una clau determinada)
• Supressió de la llista enllaçada (eliminació d'una clau en una posició determinada)
• Cerca la longitud d'una llista enllaçada (iterativa i recursiva)
• Cerca un element en una llista enllaçada (iterativa i recursiva)
• Nè node des del final d'una llista enllaçada
• Invertir una llista enllaçada

A pila és una estructura de dades lineal que emmagatzema elements de manera Últim en entrar/Primer en sortir (LIFO) o Primer en entrar/últim en sortir (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.

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>

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

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.

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

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

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.

# 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] retorna l'element excepte IndexError: print() exit() if __name__ == '__main__': myQueue = PriorityQueue( ) myQueue.insert(12) myQueue.insert(1) myQueue.insert(14) myQueue.insert(7) print(myQueue) mentre no myQueue.isEmpty(): print(myQueue.delete())>

12 1 14 7 14 12 7 1>

Munt

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 és que sempre dóna l'element més petit (munt mínim) sempre que l'element apareix. Sempre que els elements s'empenyen o esclaten, 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).

En general, els Heaps poden ser de dos tipus:

• Max-Heap: En un Max-Heap, la clau present al node arrel ha de ser la més gran entre les claus presents a tots els seus fills. La mateixa propietat ha de ser recursivament certa per a tots els subarbres d'aquest arbre binari.
• Min-Heap: En un Min-Heap, la clau present al node arrel ha de ser mínima entre les claus presents a tots els seus fills. La mateixa propietat ha de ser recursivament certa per a tots els subarbres d'aquest arbre binari.

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

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>

Més articles sobre Heap

• Munt binari
• K'è element més gran d'una matriu
• K'th element més petit/més gran de la matriu no ordenada
• Ordena una matriu gairebé ordenada
• K-th Suma més gran Subbarray contigu
• Suma mínima de dos nombres formats a partir de dígits d'una matriu

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.

A 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

# 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 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:

com convertir un nombre enter en una cadena en java

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

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 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): # Imprimeix la part davantera de la cua i # elimina-la de la impressió de la cua (queue[0].data) node = queue.pop(0) # Enqueue left child if node.left no és Cap: queue.append(node.left ) # Posa a la cua el fill dret si node.right no és Cap: queue.append(node.right) # Programa del controlador per provar a sobre de la funció root = Node(1) root.left = Node (2) root.right = Node (3) root.left.left = Node (4) root.left.right = Node (5) print ('El recorregut de l'ordre de nivell de l'arbre binari és -') printLevelOrder(arrel)>

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

Complexitat temporal: O(n)

Més articles sobre l'arbre binari

• Inserció en un arbre binari
• Supressió en un arbre binari
• Travessament de l'arbre en ordre sense recurrència
• Inorder Tree Traversal sense recursivitat i sense pila!
• Imprimeix el recorregut de la comanda posterior a partir de les travesses Inorder i Preorder donades
• Trobeu el recorregut posterior a la comanda de BST des del recorregut de la comanda prèvia

Arbre de cerca binari és una estructura de dades d'arbre binari basada en nodes que té les propietats següents:

# A utility function to search a given key in BST def search(root,key): # Base Cases: root is null or key is present at root if root is None or root.val == key: return root # Key is greater than root's key if root.val < key: return search(root.right,key) # Key is smaller than root's key return search(root.left,key)>

# Python program to demonstrate # insert operation in binary search tree # A utility class that represents # an individual node in a BST class Node: def __init__(self, key): self.left = None self.right = None self.val = key # A utility function to insert # a new node with the given key def insert(root, key): if root is None: return Node(key) else: if root.val == key: return root elif root.val < key: root.right = insert(root.right, key) else: root.left = insert(root.left, key) return root # A utility function to do inorder tree traversal def inorder(root): if root: inorder(root.left) print(root.val) inorder(root.right) # Driver program to test the above functions # Let us create the following BST # 50 # /  # 30 70 # /  /  # 20 40 60 80 r = Node(50) r = insert(r, 30) r = insert(r, 20) r = insert(r, 40) r = insert(r, 70) r = insert(r, 60) r = insert(r, 80) # Print inorder traversal of the BST inorder(r)>

20 30 40 50 60 70 80>

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.

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

# 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(' 
') # Programa controlador a la classe de gràfic anterior si __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()>

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

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

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.

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

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

Més articles sobre gràfic

• Representacions gràfics utilitzant set i hash
• Trobeu el vèrtex mare en un gràfic
• Primera cerca iterativa de profunditat
• Compteu el nombre de nodes a un nivell donat en un arbre mitjançant BFS
• Compta tots els camins possibles entre dos vèrtexs

El procés en què una funció s'anomena directament o indirectament a si mateixa s'anomena recursivitat i la funció corresponent s'anomena a funció recursiva . Mitjançant els algorismes recursius, certs problemes es poden resoldre amb força facilitat. Alguns exemples d'aquests problemes són Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

def fact(n):  # base case  if (n <= 1)   return 1  else   return n*fact(n-1)>

# A Python 3 program to # demonstrate working of # recursion def printFun(test): if (test < 1): return else: print(test, end=' ') printFun(test-1) # statement 2 print(test, end=' ') return # Driver Code test = 3 printFun(test)>

3 2 1 1 2 3>

• Recursió
• Recursió en Python
• Preguntes pràctiques per a la recursivitat | Set 1
• Preguntes pràctiques per a la recursivitat | Set 2
• Preguntes pràctiques per a la recursivitat | Set 3
• Preguntes pràctiques per a la recursivitat | Set 4
• Preguntes pràctiques per a la recursivitat | Set 5
• Preguntes pràctiques per a la recursivitat | Set 6
• Preguntes pràctiques per a la recursivitat | Set 7

>>> Més

Programació dinàmica

Programació dinàmica és principalment una optimització sobre la recursivitat simple. Sempre que veiem una solució recursiva que tingui crides repetides per a les mateixes entrades, podem optimitzar-la mitjançant la programació dinàmica. La idea és simplement emmagatzemar els resultats dels subproblemes, de manera que no els haguem de tornar a calcular quan sigui necessari més endavant. Aquesta senzilla optimització redueix les complexitats temporals d'exponencial a polinomi. Per exemple, si escrivim una solució recursiva simple per als nombres de Fibonacci, obtenim una complexitat temporal exponencial i si l'optimitzem emmagatzemant solucions de subproblemes, la complexitat del temps es redueix a lineal.

Tabulació vs memorització

Hi ha dues maneres diferents d'emmagatzemar els valors perquè els valors d'un subproblema es puguin reutilitzar. Aquí, parlarem de dos patrons de resolució de problemes de programació dinàmica (DP):

• Tabulació: De baix a dalt
• Memorització: De dalt a baix

Tabulació

Com el propi nom indica començar des de baix i acumulant respostes fins a dalt. Parlem en termes de transició estatal.

Anem a descriure un estat per al nostre problema DP com a dp[x] amb dp[0] com a estat base i dp[n] com a estat de destinació. Per tant, hem de trobar el valor de l'estat de destinació, és a dir, dp[n].

Si comencem la nostra transició des del nostre estat base, és a dir, dp[0], i seguim la nostra relació de transició d'estat per arribar al nostre estat de destinació dp[n], l'anomenem enfocament de baix a dalt, ja que és bastant clar que vam començar la nostra transició des de l'estat de destinació. l'estat base inferior i ha arribat a l'estat desitjat superior.

Ara, per què en diem mètode de tabulació?

Per saber-ho, primer escrivim un codi per calcular el factorial d'un nombre mitjançant l'enfocament de baix a dalt. Una vegada més, com a procediment general per resoldre un DP, primer definim un estat. En aquest cas, definim un estat com dp[x], on dp[x] és trobar el factorial de x.

Ara, és bastant obvi que dp[x+1] = dp[x] * (x+1)

# Tabulated version to find factorial x. dp = [0]*MAXN # base case dp[0] = 1; for i in range(n+1):  dp[i] = dp[i-1] * i>

Memoització

Una vegada més, anem a descriure-ho en termes de transició estatal. Si necessitem trobar el valor d'algun estat, digueu dp[n] i en comptes de començar des de l'estat base, és a dir, dp[0], demanem la nostra resposta als estats que poden arribar a l'estat de destinació dp[n] després de la transició d'estat. relació, llavors és la moda de dalt a baix de DP.

Aquí, comencem el nostre viatge des de l'estat de destinació superior i calculem la seva resposta tenint en compte els valors dels estats que poden arribar a l'estat de destinació, fins que arribem a l'estat base més baix.

Una vegada més, escrivim el codi del problema factorial de la manera de dalt a baix

# Memoized version to find factorial x. # To speed up we store the values # of calculated states # initialized to -1 dp[0]*MAXN # return fact x! def solve(x):  if (x==0)  return 1  if (dp[x]!=-1)  return dp[x]  return (dp[x] = x * solve(x-1))>

Més articles sobre Programació Dinàmica

• Propietat òptima de la subestructura
• Propietat de subproblemes superposats
• Nombres de Fibonacci
• Subconjunt amb suma divisible per m
• Subseqüència creixent de suma màxima
• Subcadena comuna més llarga

>>> Més

Algorismes de cerca

Cerca lineal

• Comenceu des de l'element més esquerre d'arr[] i compareu x amb cada element d'arr[]
• Si x coincideix amb un element, retorna l'índex.
• Si x no coincideix amb cap dels elements, retorna -1.

# Python3 code to linearly search x in arr[]. # If x is present then return its location, # otherwise return -1 def search(arr, n, x): for i in range(0, n): if (arr[i] == x): return i return -1 # Driver Code arr = [2, 3, 4, 10, 40] x = 10 n = len(arr) # Function call result = search(arr, n, x) if(result == -1): print('Element is not present in array') else: print('Element is present at index', result)>

Element is present at index 3>

La complexitat temporal de l'algorisme anterior és O(n).

Per a més informació, consulteu Cerca lineal .

Cerca binària

Cerqueu una matriu ordenada dividint repetidament l'interval de cerca per la meitat. Comenceu amb un interval que cobreixi tota la matriu. Si el valor de la clau de cerca és menor que l'element que hi ha al mig de l'interval, reduïu l'interval a la meitat inferior. En cas contrari, reduïu-lo a la meitat superior. Comproveu repetidament fins que es trobi el valor o l'interval estigui buit.

# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch (arr, l, r, x): # Check base case if r>= l: mid = l + (r - l) // 2 # Si l'element està present al centre si arr[mid] == x: return mid # Si l'element és més petit que mig, llavors només pot estar present al subbarrat esquerre elif arr[mid]> x: return binarySearch(arr, l, mid-1, x) # En cas contrari, l'element només pot estar present # al subbarrat dret else: return binarySearch(arr, mid + 1, r, x ) else: # L'element no és present a la matriu retorna -1 # Codi del controlador arr = [ 2, 3, 4, 10, 40 ] x = 10 # Resultat de la trucada de funció = binarySearch(arr, 0, len(arr)-1 , x) si resultat != -1: imprimeix ('L'element és present a l'índex % d' % resultat) sinó: imprimeix ('L'element no és present a la matriu')>

Element is present at index 3>

La complexitat temporal de l'algorisme anterior és O(log(n)).

Per a més informació, consulteu Cerca binària .

Algorismes d'ordenació

Ordenació de la selecció

El ordenació de selecció L'algoritme ordena una matriu trobant repetidament l'element mínim (tenint en compte l'ordre ascendent) de la part no ordenada i posant-lo al principi. En cada iteració de l'ordenació per selecció, l'element mínim (tenint en compte l'ordre ascendent) de la subbarra no ordenada es selecciona i es mou a la subbarra ordenada.

Diagrama de flux de l'ordenació de la selecció:

# Python program for implementation of Selection # Sort import sys A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)): # Find the minimum element in remaining # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # Canvia l'element mínim trobat amb # el primer element A[i], A[min_idx] = A[min_idx], A[i] # Codi del controlador per provar a sobre d'imprimir ('Matriu ordenat ') per a i a l'interval(len(A)): print('%d' %A[i]),>

Sorted array 11 12 22 25 64>

Complexitat temporal: O (n²) ja que hi ha dos bucles imbricats.

Espai auxiliar: O(1)

Classificació de bombolles

Classificació de bombolles és l'algorisme d'ordenació més senzill que funciona intercanviant repetidament els elements adjacents si estan en ordre incorrecte.

Il·lustració:

# Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already in place for j in range(0, n-i-1): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Codi del controlador a provar a sobre arr = [64, 34, 25, 12, 22, 11 , 90] bubbleSort(arr) print ('La matriu ordenada és:') per a i en rang(len(arr)): print ('%d' %arr[i]),>

Sorted array is: 11 12 22 25 34 64 90>

Complexitat temporal: O (n²)

Ordenació d'inserció

Per ordenar una matriu de mida n en ordre ascendent utilitzant ordenació d'inserció :

• Itera des de arr[1] fins a arr[n] per la matriu.
• Compareu l'element actual (clau) amb el seu predecessor.
• Si l'element clau és més petit que el seu predecessor, compareu-lo amb els elements anteriors. Mou els elements més grans una posició cap amunt per fer espai per a l'element intercanviat.

Il·lustració:

# Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j>= 0 i clau< arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ('% d' % arr[i])>

 5 6 11 12 13>

Complexitat temporal: O (n²))

Fusionar Ordenar

Igual que QuickSort, Fusionar Ordenar és un algorisme Divide and Conquer. Divideix la matriu d'entrada en dues meitats, s'anomena per les dues meitats i després fusiona les dues meitats ordenades. La funció merge() s'utilitza per combinar dues meitats. La fusió (arr, l, m, r) és un procés clau que suposa que arr[l..m] i arr[m+1..r] s'ordenen i fusiona les dues submatrius ordenades en una sola.

MergeSort(arr[], l, r) If r>l 1. Trobeu el punt mitjà per dividir la matriu en dues meitats: mig m = l+ (r-l)/2 2. Truqueu mergeSort per a la primera meitat: truqueu mergeSort(arr, l, m) 3. Truqueu mergeSort per a la segona meitat: truqueu mergeSort(arr, m+1, r) 4. Combina les dues meitats ordenades al pas 2 i 3: crida a merge(arr, l, m, r)>

# Python program for implementation of MergeSort def mergeSort(arr): if len(arr)>1: # Trobar la meitat de la matriu mid = len(arr)//2 # Dividir els elements de la matriu L = arr[:mid] # en 2 meitats R = arr[mid:] # Ordenar la primera meitat mergeSort(L) # Ordenant la segona meitat mergeSort(R) i = j = k = 0 # Copieu les dades a les matrius temporals L[] i R[] mentre i< len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # Checking if any element was left while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 # Code to print the list def printList(arr): for i in range(len(arr)): print(arr[i], end=' ') print() # Driver Code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] print('Given array is', end='
') printList(arr) mergeSort(arr) print('Sorted array is: ', end='
') printList(arr)>

Given array is 12 11 13 5 6 7 Sorted array is: 5 6 7 11 12 13>

Complexitat temporal: O(n(inici de sessió))

QuickSort

Com Merge Sort, QuickSort és un algorisme Divide and Conquer. Tria un element com a pivot i particiona la matriu donada al voltant del pivot triat. Hi ha moltes versions diferents de quickSort que trien el pivot de diferents maneres.

Trieu sempre el primer element com a pivot.

• Trieu sempre l'últim element com a pivot (implementat a continuació)
• Trieu un element aleatori com a pivot.
• Trieu la mediana com a pivot.

El procés clau de quickSort és partition(). L'objectiu de les particions és, donada una matriu i un element x de la matriu com a pivot, posar x a la seva posició correcta en una matriu ordenada i posar tots els elements més petits (menys que x) abans de x, i posar tots els elements més grans (més grans que x) després x. Tot això s'ha de fer en temps lineal.

/* low -->Índex inicial, alt --> Índex final */ quickSort(arr[], low, high) { si (baix { /* pi és un índex de partició, arr[pi] ara està al lloc correcte */ pi = partition(arr, low, high); quickSort(arr, low, pi - 1 // Abans de pi quickSort(arr, pi + 1, high);
 
 
    Algoritme de partició    
 
Hi pot haver moltes maneres de fer particions, seguint  pseudocodi  adopta el mètode indicat al llibre CLRS. La lògica és senzilla, partim de l'element més esquerre i fem un seguiment de l'índex d'elements més petits (o iguals a) com i. Mentre es recorre, si trobem un element més petit, intercanviem l'element actual amb arr[i]. En cas contrari, ignorarem l'element actual.
  
# Python3 implementation of QuickSort # This Function handles sorting part of quick sort # start and end points to first and last element of # an array respectively def partition(start, end, array): # Initializing pivot's index to start pivot_index = start pivot = array[pivot_index] # This loop runs till start pointer crosses # end pointer, and when it does we swap the # pivot with element on end pointer while start < end: # Increment the start pointer till it finds an # element greater than pivot while start < len(array) and array[start] <= pivot: start += 1 # Decrement the end pointer till it finds an # element less than pivot while array[end]>pivot: final -= 1 # Si l'inici i el final no s'han creuat, # intercanvia els números a l'inici i al final si (inici< end): array[start], array[end] = array[end], array[start] # Swap pivot element with element on end pointer. # This puts pivot on its correct sorted place. array[end], array[pivot_index] = array[pivot_index], array[end] # Returning end pointer to divide the array into 2 return end # The main function that implements QuickSort def quick_sort(start, end, array): if (start < end): # p is partitioning index, array[p] # is at right place p = partition(start, end, array) # Sort elements before partition # and after partition quick_sort(start, p - 1, array) quick_sort(p + 1, end, array) # Driver code array = [ 10, 7, 8, 9, 1, 5 ] quick_sort(0, len(array) - 1, array) print(f'Sorted array: {array}')>
   
  Sortida  
Sorted array: [1, 5, 7, 8, 9, 10]>
 
    Complexitat temporal:    O(n(inici de sessió))
 
ShellSort
 ShellSort és principalment una variació de l'Ordenació d'inserció. En l'ordenació d'inserció, movem els elements només una posició per davant. Quan un element s'ha de moure molt més endavant, hi ha molts moviments. La idea de shellSort és permetre l'intercanvi d'elements llunyans. A shellSort, fem la matriu ordenada per h per a un gran valor de h. Continuem reduint el valor de h fins que es converteixi en 1. Es diu que una matriu està ordenada per h si totes les subllistes de cada hthl'element està ordenat.
Python 3 
# Python3 program for implementation of Shell Sort def shellSort(arr): gap = len(arr) // 2 # initialize the gap while gap>0: i = 0 j = gap # comproveu la matriu d'esquerra a dreta # fins a l'últim índex possible de j mentre j< len(arr): if arr[i]>arr[j]: arr[i],arr[j] = arr[j],arr[i] i += 1 j += 1 # ara, mirem enrere des de l'índex i cap a l'esquerra # intercanviem els valors que no estan en l'ordre correcte. k = i mentre que k - bretxa> -1: si arr[k - bretxa]> arr[k]: arr[k-gap],arr[k] = arr[k],arr[k-gap] k -= 1 gap //= 2 # controlador per comprovar el codi arr2 = [12, 34, 54, 2, 3] print('input array:',arr2) shellSort(arr2) print('sorted array', arr2)>>>  
  Sortida      Complexitat temporal:    O (n2).