Structures de données sont un moyen d’organiser les données afin qu’elles soient accessibles plus efficacement en fonction de la situation. Les structures de données sont les principes fondamentaux de tout langage de programmation autour duquel un programme est construit. Python aide à apprendre les principes fondamentaux de ces structures de données d'une manière plus simple que d'autres langages de programmation.

Dans cet article, nous discuterons des structures de données dans le langage de programmation Python et de la manière dont elles sont liées à certaines structures de données intégrées spécifiques telles que les tuples de liste, les dictionnaires, etc. ainsi qu'à certaines structures de données avancées telles que les arbres, les graphiques, etc.

Listes

Les listes Python sont comme les tableaux, déclarés dans d'autres langages, qui constituent une collection ordonnée de données. Il est très flexible car les éléments d’une liste n’ont pas besoin d’être du même type.

L'implémentation de Python List est similaire à Vectors en C++ ou ArrayList en JAVA. L'opération coûteuse consiste à insérer ou à supprimer l'élément depuis le début de la liste car tous les éléments doivent être déplacés. L'insertion et la suppression en fin de liste peuvent également devenir coûteuses dans le cas où la mémoire pré-allouée devient pleine.

Nous pouvons créer une liste en python comme indiqué ci-dessous.

Exemple : création d'une liste Python

Python3

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

Sortir

[1, 2, 3, 'GFG', 2.3] 

Les éléments de la liste sont accessibles via l'index attribué. Dans l'index de départ python de la liste, la séquence est 0 et l'index de fin est (si N éléments sont là) N-1.

Exemple : opérations de liste 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> ])>

Sortir

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 

Dictionnaire

Dictionnaire Python est comme les tables de hachage dans n'importe quel autre langage avec la complexité temporelle de O(1). Il s'agit d'une collection non ordonnée de valeurs de données, utilisée pour stocker des valeurs de données comme une carte qui, contrairement aux autres types de données qui ne contiennent qu'une seule valeur en tant qu'élément, le dictionnaire contient la paire clé:valeur. La valeur-clé est fournie dans le dictionnaire pour la rendre plus optimisée.

L'indexation du dictionnaire Python se fait à l'aide de clés. Ceux-ci sont de n'importe quel type hachable, c'est-à-dire un objet qui ne peut jamais changer comme des chaînes, des nombres, des tuples, etc. Nous pouvons créer un dictionnaire en utilisant des accolades ({}) ou compréhension du dictionnaire .

Exemple : opérations du dictionnaire 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)>

Sortir

Creating Dictionary: {'Name': 'Geeks', 1: [1, 2, 3, 4]} Accessing a element using key: Geeks Accessing a element using get: [1, 2, 3, 4] {1: 1, 2: 4, 3: 9, 4: 16, 5: 25} 

Tuple

Tuple Python est une collection d'objets Python un peu comme une liste, mais les tuples sont de nature immuable, c'est-à-dire que les éléments du tuple ne peuvent pas être ajoutés ou supprimés une fois créés. Tout comme une liste, un tuple peut également contenir des éléments de différents types.

En Python, les tuples sont créés en plaçant une séquence de valeurs séparées par une « virgule » avec ou sans l'utilisation de parenthèses pour le regroupement de la séquence de données.

Note: Les tuples peuvent également être créés avec un seul élément, mais c'est un peu délicat. Avoir un élément entre parenthèses n’est pas suffisant, il doit y avoir une « virgule » à la fin pour en faire un tuple.

Exemple : opérations sur les tuples 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> ])>

Sortir

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 

Ensemble

Ensemble Python est une collection non ordonnée de données qui est mutable et n'autorise aucun élément en double. Les ensembles sont essentiellement utilisés pour inclure des tests d’adhésion et éliminer les entrées en double. La structure de données utilisée ici est le hachage, une technique populaire pour effectuer l'insertion, la suppression et le parcours en O(1) en moyenne.

Si plusieurs valeurs sont présentes à la même position d'index, la valeur est ajoutée à cette position d'index pour former une liste chaînée. Dans, les ensembles CPython sont implémentés à l'aide d'un dictionnaire avec des variables factices, où les clés sont les membres définis avec de plus grandes optimisations de la complexité temporelle.

Définir la mise en œuvre :

Ensembles avec de nombreuses opérations sur une seule HashTable :

Exemple : opérations d'ensemble 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> )>

Sortir

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

Ensembles congelés

Les ensembles gelés en Python sont des objets immuables qui prennent uniquement en charge les méthodes et les opérateurs qui produisent un résultat sans affecter le ou les ensembles gelés auxquels ils sont appliqués. Alors que les éléments d'un ensemble peuvent être modifiés à tout moment, les éléments de l'ensemble figé restent les mêmes après la création.

Si aucun paramètre n'est transmis, il renvoie un jeu gelé vide.

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

Sortir

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

Chaîne

Les chaînes Python sont des tableaux d'octets représentant des caractères Unicode. En termes plus simples, une chaîne est un tableau immuable de caractères. Python n'a pas de type de données caractère, un seul caractère est simplement une chaîne d'une longueur de 1.

Note: Les chaînes étant immuables, la modification d’une chaîne entraînera la création d’une nouvelle copie.

Exemple : opérations sur les chaînes 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> ])>

Sortir

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

Tableau d'octets

Python Bytearray donne une séquence mutable d'entiers compris entre 0 <= x < 256.

Exemple : opérations Python Bytearray

Python3

# Creating bytearray> a> => bytearray((> 12> ,> 8> ,> 25> ,> 2> ))> print> (> 'Creating Bytearray:'> )> print> (a)> # accessing elements> print> (> ' Accessing Elements:'> , a[> 1> ])> # modifying elements> a[> 1> ]> => 3> print> (> ' After Modifying:'> )> print> (a)> # Appending elements> a.append(> 30> )> print> (> ' After Adding Elements:'> )> print> (a)>

Sortir

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

Jusqu'à présent, nous avons étudié toutes les structures de données intégrées au cœur de Python. Plongeons maintenant plus en profondeur dans Python et voyons le module de collections qui fournit des conteneurs utiles dans de nombreux cas et offrent plus de fonctionnalités que les fonctions définies ci-dessus.

Module de recouvrement

Le module de collection Python a été introduit pour améliorer la fonctionnalité des types de données intégrés. Il fournit différents conteneurs, voyons chacun d’eux en détail.

Compteurs

Un compteur est une sous-classe du dictionnaire. Il est utilisé pour conserver le nombre d'éléments dans un itérable sous la forme d'un dictionnaire non ordonné où la clé représente l'élément dans l'itérable et la valeur représente le nombre de cet élément dans l'itérable. Cela équivaut à un sac ou à un multiensemble d’autres langues.

Exemple : opérations de compteur 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)>

Sortir

Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 3, 'C': 2}) Counter({'B': 5, 'A': 4, 'C': 2, 1: 1}) 

OrdonnéDict

Un OrdonnéDict est également une sous-classe de dictionnaire mais contrairement à un dictionnaire, il mémorise l'ordre dans lequel les clés ont été insérées.

Exemple : opérations 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)>

Sortir

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 

Dict par défaut

Dict par défaut est utilisé pour fournir des valeurs par défaut pour la clé qui n'existe pas et ne génère jamais de KeyError. Ses objets peuvent être initialisés à l'aide de la méthode DefaultDict() en passant le type de données en argument.

Note: default_factory est une fonction qui fournit la valeur par défaut du dictionnaire créé. Si ce paramètre est absent alors la KeyError est levée.

Exemple : opérations 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)>

Sortir

defaultdict(, {1: 2, 2: 3, 3: 1, 4: 2}) 

Carte de chaîne

Un ChainMap encapsule de nombreux dictionnaires dans une seule unité et renvoie une liste de dictionnaires. Lorsqu'il est nécessaire de trouver une clé, tous les dictionnaires sont recherchés un par un jusqu'à ce que la clé soit trouvée.

Exemple : opérations 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'> ])>

Sortir

ChainMap({'a': 1, 'b': 2}, {'c': 3, 'd': 4}, {'e': 5, 'f': 6}) 1 

KeyError: 'g' 

Tuple nommé

UN Tuple nommé renvoie un objet tuple avec des noms pour chaque position qui manquent aux tuples ordinaires. Par exemple, considérons un tuple de noms student où le premier élément représente fname, le deuxième représente lname et le troisième élément représente le DOB. Supposons que pour appeler fname au lieu de vous souvenir de la position de l'index, vous puissiez réellement appeler l'élément en utilisant l'argument fname, il sera alors très facile d'accéder à l'élément tuples. Cette fonctionnalité est fournie par NamedTuple.

Exemple : opérations 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)>

Sortir

The Student age using index is : 19 The Student name using keyname is : Nandini 

De quoi

Deque (file d'attente à double extrémité) est la liste optimisée pour des opérations d'ajout et de pop plus rapides des deux côtés du conteneur. Il fournit une complexité temporelle O(1) pour les opérations d'ajout et de pop par rapport à la liste avec une complexité temporelle O(n).

Python Deque est implémenté à l'aide de listes doublement liées, donc les performances d'accès aléatoire aux éléments sont O(n).

Exemple : opérations Python Deque

Python3

# importing 'collections' for deque operations> import> collections> # initializing deque> de> => collections.deque([> 1> ,> 2> ,> 3> ])> # using append() to insert element at right end> # inserts 4 at the end of deque> de.append(> 4> )> # printing modified deque> print> (> 'The deque after appending at right is : '> )> print> (de)> # using appendleft() to insert element at left end> # inserts 6 at the beginning of deque> de.appendleft(> 6> )> # printing modified deque> print> (> 'The deque after appending at left is : '> )> print> (de)> # using pop() to delete element from right end> # deletes 4 from the right end of deque> de.pop()> # printing modified deque> print> (> 'The deque after deleting from right is : '> )> print> (de)> # using popleft() to delete element from left end> # deletes 6 from the left end of deque> de.popleft()> # printing modified deque> print> (> 'The deque after deleting from left is : '> )> print> (de)>

Sortir

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

UtilisateurDict

UserDict est un conteneur de type dictionnaire qui agit comme un wrapper autour des objets du dictionnaire. Ce conteneur est utilisé lorsque quelqu'un souhaite créer son propre dictionnaire avec des fonctionnalités modifiées ou nouvelles.

Exemple : 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> )>

Sortir

Original Dictionary {'a': 1, 'b': 2, 'c': 3} 

RuntimeError: Deletion not allowed 

Liste d'utilisateur

UserList est un conteneur de type liste qui agit comme un wrapper autour des objets de la liste. Ceci est utile lorsque quelqu'un souhaite créer sa propre liste avec des fonctionnalités modifiées ou supplémentaires.

Exemples : liste d'utilisateurs 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()>

Sortir

Original List [1, 2, 3, 4] After Insertion [1, 2, 3, 4, 5] 

RuntimeError: Deletion not allowed 

Chaîne d'utilisateur

UserString est un conteneur de type chaîne et, tout comme UserDict et UserList, il agit comme un wrapper autour des objets chaîne. Il est utilisé lorsque quelqu'un souhaite créer ses propres chaînes avec des fonctionnalités modifiées ou supplémentaires.

Exemple : chaîne d'utilisateur 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)>

Sortir

Original String: Geeks String After Appending: Geekss String after Removing: Gkss 

Maintenant, après avoir étudié toutes les structures de données, voyons quelques structures de données avancées telles que la pile, la file d'attente, le graphique, la liste chaînée, etc. qui peuvent être utilisées dans le langage Python.

Liste liée

Une liste chaînée est une structure de données linéaire dans laquelle les éléments ne sont pas stockés dans des emplacements mémoire contigus. Les éléments d'une liste chaînée sont liés à l'aide de pointeurs, comme indiqué dans l'image ci-dessous :

Une liste chaînée est représentée par un pointeur vers le premier nœud de la liste chaînée. Le premier nœud est appelé la tête. Si la liste chaînée est vide, alors la valeur de la tête est NULL. Chaque nœud d'une liste se compose d'au moins deux parties :

• Données
• Pointeur (ou référence) vers le nœud suivant

Exemple : définir une liste chaînée en 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>

Créons une simple liste chaînée avec 3 nœuds.

Python3

# A simple Python program to introduce a linked list> # Node class> class> Node:> > # Function to initialise the node object> > def> __init__(> self> , data):> > self> .data> => data> # Assign data> > self> .> next> => None> # Initialize next as null> # Linked List class contains a Node object> class> LinkedList:> > # Function to initialize head> > def> __init__(> self> ):> > self> .head> => None> # Code execution starts here> if> __name__> => => '__main__'> :> > # Start with the empty list> > list> => LinkedList()> > list> .head> => Node(> 1> )> > second> => Node(> 2> )> > third> => Node(> 3> )> > '''> > Three nodes have been created.> > We have references to these three blocks as head,> > second and third> > list.head second third> > | | |> > | | |> > +----+------+ +----+------+ +----+------+> > | 1 | None | | 2 | None | | 3 | None |> > +----+------+ +----+------+ +----+------+> > '''> > list> .head.> next> => second;> # Link first node with second> > '''> > Now next of first Node refers to second. So they> > both are linked.> > list.head second third> > | | |> > | | |> > +----+------+ +----+------+ +----+------+> > | 1 | o-------->| 2 | nul | | 3 | nul |> > +----+------+ +----+------+ +----+------+> > '''> > second.> next> => third;> # Link second node with the third node> > '''> > Now next of second Node refers to third. So all three> > nodes are linked.> > list.head second third> > | | |> > | | |> > +----+------+ +----+------+ +----+------+> > | 1 | o-------->| 2 | o-------->| 3 | nul |> > +----+------+ +----+------+ +----+------+> > '''>

Parcours de liste chaînée

Dans le programme précédent, nous avons créé une simple liste chaînée avec trois nœuds. Parcourons la liste créée et imprimons les données de chaque nœud. Pour le parcours, écrivons une fonction à usage général printList() qui imprime n'importe quelle liste donnée.

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

Sortir

1 2 3 

Empiler

UN empiler est une structure de données linéaire qui stocke les éléments selon la méthode Last-In/First-Out (LIFO) ou First-In/Last-Out (FILO). Dans la pile, un nouvel élément est ajouté à une extrémité et un élément est supprimé à cette extrémité uniquement. Les opérations d'insertion et de suppression sont souvent appelées push et pop.

Les fonctions associées à la pile sont :

empty() – Renvoie si la pile est vide – Complexité temporelle : O(1) size() – Renvoie la taille de la pile – Complexité temporelle : O(1) top() – Renvoie une référence à l'élément le plus haut de la pile – Complexité temporelle : O(1) push(a) – Insère l'élément 'a' en haut de la pile – Complexité temporelle : O(1) pop() – Supprime l'élément le plus haut de la pile – Complexité temporelle : O( 1)

Implémentation de la pile Python

Stack en Python peut être implémenté des manières suivantes :

• liste
• Collections.deque
• file d'attente.LifoQueue

Implémentation à l'aide de List

La liste de structures de données intégrée de Python peut être utilisée comme pile. Au lieu de push(), append() est utilisé pour ajouter des éléments en haut de la pile tandis que pop() supprime l'élément dans l'ordre 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>

Sortir

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

Implémentation à l'aide de collections.deque :

La pile Python peut être implémentée à l'aide de la classe deque du module collections. Deque est préféré à la liste dans les cas où nous avons besoin d'opérations d'ajout et de pop plus rapides depuis les deux extrémités du conteneur, car deque fournit une complexité temporelle O(1) pour les opérations d'ajout et de pop par rapport à la liste qui fournit O(n) complexité temporelle.

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>

Sortir

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

Implémentation à l'aide du module de file d'attente

Le module de file d'attente dispose également d'une file d'attente LIFO, qui est essentiellement une pile. Les données sont insérées dans la file d'attente à l'aide de la fonction put() et get() extrait les données de la file d'attente.

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

Sortir

0 Full: True Size: 3 Elements popped from the stack g f g Empty: True 

File d'attente

En tant que pile, le file d'attente est une structure de données linéaire qui stocke les éléments selon le principe premier entré, premier sorti (FIFO). Avec une file d'attente, l'élément ajouté le moins récemment est supprimé en premier. Un bon exemple de file d'attente est n'importe quelle file d'attente de consommateurs pour une ressource dans laquelle le consommateur arrivé en premier est servi en premier.

Les opérations associées à la file d'attente sont :

Mettre en file d'attente : ajoute un élément à la file d'attente. Si la file d'attente est pleine, on parle alors d'une condition de débordement – ​​Complexité temporelle : O(1) Supprimer la file d'attente : supprime un élément de la file d'attente. Les éléments sont affichés dans le même ordre dans lequel ils ont été poussés. Si la file d'attente est vide, on dit alors qu'il s'agit d'une condition de sous-débordement – ​​Complexité temporelle : O(1) Avant : obtenez l'élément de premier plan de la file d'attente – Complexité temporelle : O(1) Arrière : obtenez le dernier élément de la file d'attente – Complexité temporelle :O(1)

Implémentation de la file d'attente Python

La file d'attente en Python peut être implémentée des manières suivantes :

• liste
• collections.deque
• queue.Queue

Implémentation à l'aide d'une liste

Au lieu de enqueue() et dequeue(), les fonctions append() et pop() sont utilisées.

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>

Sortir

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

Implémentation à l'aide de collections.deque

Deque est préféré à la liste dans les cas où nous avons besoin d'opérations d'ajout et de pop plus rapides depuis les deux extrémités du conteneur, car deque fournit une complexité temporelle O(1) pour les opérations d'ajout et de pop par rapport à la liste qui fournit O(n) complexité temporelle.

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>

Sortir

Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([]) 

Implémentation à l'aide de queue.Queue

queue.Queue(maxsize) initialise une variable à une taille maximale de maxsize. Une taille maximale de zéro « 0 » signifie une file d'attente infinie. Cette file d'attente suit la règle 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())>

Sortir

0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False 

File d'attente de priorité

Files d'attente prioritaires sont des structures de données abstraites où chaque donnée/valeur dans la file d'attente a une certaine priorité. Par exemple, dans les compagnies aériennes, les bagages portant le titre Business ou First class arrivent plus tôt que les autres. La file d'attente prioritaire est une extension de la file d'attente avec les propriétés suivantes.

• Un élément de priorité élevée est retiré de la file d'attente avant un élément de priorité faible.
• Si deux éléments ont la même priorité, ils sont servis selon leur ordre dans la file d'attente.

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

Sortir

12 1 14 7 14 12 7 1 

File d'attente de tas (ou heapq)

module heapq en Python fournit la structure de données de tas qui est principalement utilisée pour représenter une file d'attente prioritaire. La propriété de cette structure de données en Python est qu'à chaque fois, le plus petit élément du tas est sauté (min-heap). Chaque fois que des éléments sont poussés ou sautés, la structure du tas est conservée. L'élément heap[0] renvoie également le plus petit élément à chaque fois.

Il prend en charge l'extraction et l'insertion du plus petit élément dans les temps 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))>

Sortir

The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1 

Arbre binaire

Un arbre est une structure de données hiérarchique qui ressemble à la figure ci-dessous :

 tree ---- j  <-- root /  f k /   a h z  <-- leaves 

Le nœud le plus haut de l’arborescence est appelé racine tandis que les nœuds les plus bas ou les nœuds sans enfants sont appelés nœuds feuilles. Les nœuds qui se trouvent directement sous un nœud sont appelés ses enfants et les nœuds qui se trouvent directement au-dessus de quelque chose sont appelés son parent.

Un arbre binaire est un arbre dont les éléments peuvent avoir presque deux enfants. Étant donné que chaque élément d’un arbre binaire ne peut avoir que 2 enfants, nous les nommons généralement enfants gauche et droit. Un nœud d'arbre binaire contient les parties suivantes.

• Données
• Pointeur vers l'enfant gauche
• Pointeur vers le bon enfant

Exemple : définition d'une classe de nœud

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>

Créons maintenant un arbre à 4 nœuds en Python. Supposons que la structure arborescente ressemble à ci-dessous :

 tree ---- 1  <-- root /  2 3 / 4 

Exemple : ajout de données à l'arborescence

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

Traversée des arbres

Les arbres peuvent être traversés en différentes manières. Voici les méthodes généralement utilisées pour parcourir les arbres. Considérons l'arbre ci-dessous -

 tree ---- 1  <-- root /  2 3 /  4 5 

Premières traversées en profondeur :

• Dans l'ordre (Gauche, Racine, Droite) : 4 2 5 1 3
• Précommande (Racine, Gauche, Droite) : 1 2 4 5 3
• Post-ordre (Gauche, Droite, Racine) : 4 5 2 3 1

Ordre de l'algorithme (arbre)

• Parcourez le sous-arbre gauche, c'est-à-dire appelez Inorder (sous-arbre gauche)
• Visitez la racine.
• Parcourez le sous-arbre droit, c'est-à-dire appelez Inorder (sous-arbre droit)

Précommande d'algorithme (arbre)

• Visitez la racine.
• Parcourez le sous-arbre gauche, c'est-à-dire appelez Preorder(left-subtree)
• Parcourez le sous-arbre droit, c'est-à-dire appelez Preorder (sous-arbre droit)

Algorithme Mandat postal (arbre)

• Parcourez le sous-arbre gauche, c'est-à-dire appelez Postorder (sous-arbre gauche)
• Parcourez le sous-arbre droit, c'est-à-dire appelez Postorder (sous-arbre droit)
• Visitez la racine.

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

Sortir

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 

Complexité temporelle – O(n)

Traversée d'ordre en largeur ou en niveau

Parcours de l'ordre de niveau d'un arbre est un parcours en largeur d'abord pour l'arbre. Le parcours d’ordre de niveau de l’arbre ci-dessus est 1 2 3 4 5.

Pour chaque nœud, le nœud est d'abord visité, puis ses nœuds enfants sont placés dans une file d'attente FIFO. Vous trouverez ci-dessous l’algorithme pour le même –

• Créer une file d'attente vide q
• temp_node = root /*démarrer à partir de root*/
• Boucle pendant que temp_node n'est pas NULL
  • print temp_node->data.
  • Mettre les enfants de temp_node en file d'attente (premiers enfants à gauche puis à droite) vers q
  • Retirer un nœud de 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)>

Sortir

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

Complexité temporelle : O(n)

Graphique

UN graphique est une structure de données non linéaire composée de nœuds et d'arêtes. Les nœuds sont parfois également appelés sommets et les arêtes sont des lignes ou des arcs qui relient deux nœuds quelconques du graphique. Plus formellement, un graphe peut être défini comme un graphe constitué d'un ensemble fini de sommets (ou nœuds) et d'un ensemble d'arêtes qui relient une paire de nœuds.

Dans le graphique ci-dessus, l'ensemble des sommets V = {0,1,2,3,4} et l'ensemble des arêtes E = {01, 12, 23, 34, 04, 14, 13}.

Les deux représentations suivantes sont les représentations graphiques les plus couramment utilisées.

• Matrice de contiguïté
• Liste de contiguïté

Matrice de contiguïté

La matrice d'adjacence est un tableau 2D de taille V x V où V est le nombre de sommets dans un graphique. Soit le tableau 2D adj[][], un emplacement adj[i][j] = 1 indique qu'il y a une arête du sommet i au sommet j. La matrice de contiguïté d'un graphe non orienté est toujours symétrique. La matrice de contiguïté est également utilisée pour représenter des graphiques pondérés. Si adj[i][j] = w, alors il y a une arête du sommet i au sommet j avec un poids 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())>

Sortir

Sommets du graphique

['a B c d e F']

Bords du graphique

[('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 de contiguïté du graphique

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

Liste de contiguïté

Un tableau de listes est utilisé. La taille du tableau est égale au nombre de sommets. Soit le tableau un tableau[]. Un tableau d'entrée[i] représente la liste des sommets adjacents au ième sommet. Cette représentation peut également être utilisée pour représenter un graphique pondéré. Les poids des arêtes peuvent être représentés sous forme de listes de paires. Voici la représentation de liste de contiguïté du graphique ci-dessus.

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

Sortir

Adjacency list of vertex 0 head ->4 -> 1 Liste de contiguïté de la tête du sommet 1 -> 4 -> 3 -> 2 -> 0 Liste de contiguïté de la tête du sommet 2 -> 3 -> 1 Liste de contiguïté de la tête du sommet 3 -> 4 -> 2 -> 1 Adjacence liste des sommets 4 tête -> 3 -> 1 -> 0 

Traversée du graphique

Recherche en largeur d'abord ou BFS

Traversée en largeur car un graphique est similaire au parcours en largeur d'abord d'un arbre. Le seul problème ici est que, contrairement aux arbres, les graphiques peuvent contenir des cycles, nous pouvons donc revenir au même nœud. Pour éviter de traiter un nœud plus d'une fois, nous utilisons un tableau booléen visité. Pour simplifier, on suppose que tous les sommets sont accessibles à partir du sommet de départ.

Par exemple, dans le graphique suivant, nous commençons le parcours à partir du sommet 2. Lorsque nous arrivons au sommet 0, nous recherchons tous les sommets adjacents de celui-ci. 2 est également un sommet adjacent de 0. Si nous ne marquons pas les sommets visités, alors 2 sera à nouveau traité et deviendra un processus sans fin. Un parcours en largeur du graphique suivant est 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>

Sortir

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1 

Complexité temporelle : O(V+E) où V est le nombre de sommets du graphe et E est le nombre d'arêtes du graphe.

Recherche en profondeur d'abord ou DFS

Première traversée en profondeur car un graphique est similaire au Depth First Traversal d’un arbre. Le seul problème ici est que, contrairement aux arbres, les graphiques peuvent contenir des cycles, un nœud peut être visité deux fois. Pour éviter de traiter un nœud plus d'une fois, utilisez un tableau booléen visité.

Algorithme:

• Créez une fonction récursive qui prend l'index du nœud et un tableau visité.
• Marquez le nœud actuel comme visité et imprimez le nœud.
• Parcourez tous les nœuds adjacents et non marqués et appelez la fonction récursive avec l'index du nœud adjacent.

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

Sortir

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

Complexité temporelle : O(V + E), où V est le nombre de sommets et E est le nombre d'arêtes du graphe.