Discussion :

[Community Management]

Bonjour,

Nous mettons en place une page source pour la rubrique algorithme et nous avons besoin de votre participation.

Cette page contient des algorithmes en pseudo-code uniquement, les implémentations n'ont pas leur place ici !

SI vous désirez contribuer, sachez que nous organisons les sources algo comme ceci :

Entrée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
On présente ce que l'on donne à l'algorithme (un tableau, un arbre, ...)

Sortie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
On indique ce que doit nous retourner le tableau (le tableau trié par ex.)

Pseudo-Code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
L'algorithme !

Complexité :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
On indique une complexité ( mini , moy , max ).

Merci à tous ceux qui participeront.


La page source est accessible ici : http://algo.developpez.com/sources/

[millie]

les implémentations n'ont pas leur place ici

Le problème est que parfois, la complexité dépend de l'implémentation que l'on donne aux types abstraits. Donc j'imagine que dans ce cas il faut préciser ?

[PRomu@ld]

la complexité dépend de l'implémentation

En fait, si la complexité dépend de l'implémentation, celà veut dire que ton algo en est aussi dépendant donc ça apparaît aussitôt, il n'y a donc pas forcément besoin de le préciser. Mais si pour une application spécifique tu juges qu'il est bon de le préciser, fait-le.

[mattj]

Q: Comment parcourir un graphe en largeur d'abord?

R:

Pour parcourir un graphe en largeur d'abord, nous utiliserons une file dans laquelle on placera les différents sommets.

Idée générale:
1. On part avec une file contenant le noeud de départ
2. On défile le premier noeud pour le traiter
3. On place les voisins non marqués de ce noeud en bout de file, après les avoir marqué
4. Si la file n'est pas vide, on revient à l'étape 2

Algorithme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Entree: 
    Graphe G
    Noeud S  //noeud initial du parcours

Parcours_en_largeur(G,S)
    File F = FileVide();
    Enfiler(F, S);
    Marquer(S);
    tantque NON FileVide(F) faire
        Noeud N = Défiler(F);
        pour tout Noeud X dans Fils(N) faire
            si NonMarqué(X) alors 
                  Marquer(X);
                  Enfiler(F, X);
            finsi
       finpourtout
    fintantque

[PRomu@ld]

Le parcours en profondeur de graphe éxiste déjà dans la liste des sources :

http://algo.developpez.com/sources/?...aphe#graph_dfs

[mattj]

en effet mais il s'agit d'un parcours recursif...

[PRomu@ld]

D'accord. N'oublie pas de traiter le cas où on a un graphe non connexe.

[millie]

D'accord. N'oublie pas de traiter le cas où on a un graphe non connexe.

Je ne vois pas le problème si le graphe n'est pas connexe. Il fait un parcours à partir d'un sommet particulier, donc si le graphe a plusieurs composantes connexes, toutes les composantes qui ne correspondent pas à la composante du sommet S (de départ) ne seront jamais vu. Non ?

[PRomu@ld]

Oui, dans ce cas, c'est un parcours de composante connexe en profondeur, pas un parcours de graphe en profondeur (c'est comme ça que je le vois). Un parcours d'une structure de donnée générique doit passer en revue tous les objets de cette structure de donnée (un parcours, je le vois comme une sorte d'énumération des élements de la structure)

C'est juste une question d'application ou de définition, c'est pas bien grave.