g 2 algos:
^M= matrice de le fermeture transitive de G
1-----------------------------------------------------
Données: G:Graphe, M:matrice d'adjacence
Résultat: vrai(il existe un circuit) faux sinon
Code :
- Debut
- calcul de ^M //O(n^3)
- pour k<-1 à n faire //O(n)
- si ^M[k][k]=1 alors retourner vrai
- fin pour
- retourner faux
- Fin
|
2-----------------------------------------------------
Données G, M
Résultat vrai ou faux
Code :
- Debut
- M*<-M
- Tantque (il existe dans M* une ligne i de 0 et M*!=0) faire
- supprimer dans M* la ligne i et la colonne i
- soit M** la nouvelle mat
- M*<-M**
- Fin Tantque
- Cas: M*=0 => G sans circuit retourne vrai
- M* n'a plus d'element => idem
- M* a des elements non nuls => retourne faux
- Fin
|
pour les erreurs, voir mon prof d'algo/graphes. 
