Discussion :

[maxime93]

Bonjour ,
je cherche a faire un alogorithme de tri topologique de graphe et je galère pour ça...je comprends meme pas comment me procédé pour le faire...
si quelqu'un peu me donné un coup de main ..

merci d'avance

[Trap D]

Ben, je n'y connais rien, mais avec Google j'ai déjà trouvé ça
En espérant que ça t'aide

[Nemerle]

TrapD, tu fais la secrétaire maintenant?

[borisd]

Une manière de faire qui devrait fonctionner :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Pour chaque sommet i faire
  d[i] <- degré intérieur de i, niveau[i] <-0
Fin Pour
Pour i de 1 au nombre de sommets faire
  Chercher un sommet j tel que d[j]=0
  S'il n'en existe pas, le graphe comporte un cycle.
  Sinon
    d[j]<- -1
    Pour tout sommet x successeur de j faire
      d[x] <- d[x]-1 ; niveau[x] <- max(niveau[x],niveau[j]+1)
    Fin Pour
  Fin Si
Fin Pour

[mchk0123]

Une autre façon de faire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Compute and store the in degree d[j] for each j
  (this is the number of i's for which i -> j). 
 
Initialise a collection (typically a queue or a stack, doesn't matter which)
  C to {j : d[j] == 0}. 
While C is not empty: 
  Remove some element i from C. 
  Output i. 
  For each j such that i -> j, decrement d[d];
    if this zeros it, add j to C. 
    If we output n values in the previous step, the sort succeeded;
    otherwise it failed, and a loop exists in the input.

[borisd]

A part les erreurs d'indentation, j'ai du mal à voir la différence avec ma proposition