Quand utiliser les files ?

Bonjour, quand et pourquoi utiliser une file? Une Pile?

Par exemple, dans les algorithmes de parcours de graphe (Dijkstra...) il y a une file et je ne comprends pas pourquoi...
Pourriez-vous m'aider, s'il vous plaît?
Grand merci à vous.:D

:salut:

Une file est une structure de données FIFO : le premier élément arrivé sera le premier élément sorti. Au contraire, la pile fonctionne dans l'ordre inverse, LIFO : le premier élément arrivé dans la pile sera le dernier que tu pourras récupérer.

Pour Dijkstra, tu effectues un parcours en largeur de ton graphe : le nœud de départ, puis tous ses voisins, puis tous les voisins de ces voisins, etc. (Au contraire, un parcours en profondeur continue à s’éloigner, à parcourir d'abord les enfants du nœud courant.) Pour ce parcours en largeur, tu dois utiliser une file : quand tu commences au niveau de ta source, tu explores un voisin, puis tu stockes les autres voisins pour exploration immédiate dans une file. Chaque fois que tu vois un nœud, tu places tous ses voisins pas déjà explorés à la fin de la file. Ainsi, tu parcourras bien tous les nœuds du graphe "en largeur".

Les expressions 'en largeur' et 'en profondeur' sont claires, mais j'ai bien peur que notre ami ne les comprenne pas.

Quand on parcours un arbre en largeur, on va recenser tous les points qui sont à une distance de 1 du point de départ, puis tous les points qui sont à une distance de 2 du point de départ, puis tous les points ç une distance de 3 , etc, etc, etc,
Alors que dans un parcours en profondeur, on va parcourir une branche, et on va aller jusqu'au bout de cette branche, et quand on en aura fini avec cette branche, on attaquera une autre branche.
Par exemple, si on prend un cas classique : sur un damier 8x8, avec des cases notées de A1 à H8, on part de la case A1, et on veut 'visiter' chaque case.
On va forcément commencer par dire que les 2 voisins de A1 sont les cases A2 et B1. on va donc mettre ces 2 cases dans une file ou dans une pile.
file = {(B1, 1);(A2,1)} : Dans ma file, je donne la case visitée, et la distance par rapport à la case A1.
à l'étape suivante, on va avoir : file = {(A2,1);(B2,2);(C1,2)}
Et à la 3ème étape, on va avoir : file = {(B2,2);(C1,2);(A3,2)} On parcourt en largeur, on a tous les éléments à 1 pas de l'origine, puis tous les éléments à 2 pas de l'origine ... ...

Dans le cas d'un parcours en profondeur, on va avoir :
pile = {(B1, 1);(A2,1)}
Puis pile = {(B1,1);(B2,1);(A3,2)}
Puis pile = {(B1,1);(B2,1);(B2,3);(A3,3)} : à chaque nouveau mouvement, on prend la dernière case recensée, et on recherche ses voisins.
Puis pile = {(B1,1);(B2,1);(B2,3);(B3,4);(A4,4)} : On a dans notre recensement des points à une distance de 1 de l'origine, et aussi des points à une distance de 2, ou de 3 ou même de 4 !

Où peut-on utiliser les files encore? :calim2:

Une file d'attente à un guichet (ou pour accéder à une ressource partagée, en général ; dans le même genre, le traitement des événements comme des clics qui arrivent à une application), un système peu efficace de gestion des caches (dès qu'il est rempli, on élimine la première entrée arrivée ; voir anomalie de Bellady pour l'efficacité moyenne).