Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

L'algorithme de Tarjan / L'algorithme de Kosaraju

No description
by

fadoua jouili

on 18 November 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of L'algorithme de Tarjan / L'algorithme de Kosaraju

L'algorithme de Tarjan / L'algorithme de Kosaraju
Introduction
L'algothime de Tarjan
L'algorithme de Kosaraju
Conclusion
2 algorithmes pour décomposer un graphe en CFC
Fadoua Jouili
Farah Hamrouni

Principe
Basé sur l’algorithme de parcours en profondeur(DFS). Nécessite
2 parcours
du graphe :
1er parcours : DFS pour trouver un ordre de sommets.
2éme parcours : DFS de l'inverse du graphe dans l'ordre généré par le 1er parcours.

L'algorithme
entrée:
graphe G = (V, E)
sortie:
ensemble des composantes fortement connexes (ensembles de sommets)

1.
P = pile vide;
2.
tant que P ne contient pas tous les sommets faire
Choisir un sommet v arbitraire n'appartient pas à P;
DFS (v)
à chaque fois que DFS termine l'expansion d'un sommet u, Empiler(u,P);
3
.G'= Graphe transposé(G);
4.
tant que P est non vide faire
v = Dépiler (P);
si v est non visités alors DFS (v);
L'ensemble des sommets visités donnera la composante fortement connexe contenant

Exécution
Exemple
End
Start
Graphe G
Pile
2éme parcours: DFS de G'
Pile
1
2
3
4
5
H
G
C
E
F
1er parcours: DFS de G
Pile

1
2
3
4
5
H
G
C
E
F
6
7
8
D
B
A
Graphe G
Pile
1
2
3
H
G
C
E
F
D
B
A
4
5
6
7
8
CFC
C2
C1
C3
Une composante fortement connexe CFC d'un graphe orienté G est un sous-graphe de G tel que:
Pour tout couple (u, v) de sommets, il existe un chemin de u à v.
Plusieurs algorithmes décomposent en CFC en temps linéaire : L'algorithme de
Kosaraju
et de
Tarjan
.

L'algorithme
Principe
Nécessite
un seul parcours en profondeur
 depuis un sommet
Mettre ces racines dans une pile
Dépiler les sommets de la racine sommet pour former une CFC
Répéter s’il y a encore des sommets non explorés

Exécution
Exemple
complexité linéaire:
O(V+E)
complexité linéaire:
OΟ(V²)
Initialisations
P=pile vide ; n=0 ; k=0
Pour chaque sommet s Faire
pref[s]=0 ;
ret[s]=0 ;
dansPile[s]=Faux ;
comp[s]=0
Fin Pour

Calcul de toutes CFC
Pour chaque sommet s Faire
Si pref[s]=0 Alors
CFC(s)
Fin Si
Fin Pour
Calcul de CFC

Procedure CFC(x:sommet)
empiler(x,P) ;
dansPile[x]=Vrai n=n+1;
pref[x]=n ; m=pref[x]
Pour chaque successeur y de x Faire
Si pref[y]=0 Alors
CFC(y) m=min(pref[x],ret[y])
Sinon
Si dansPile[y] Alors
m=min(m,pref[y])
Fin Si
Fin Si
Fin Pour
ret[x]=m
Si ret[x]=pref[x] Alors
k=k+1
Repeter y=sommetPile[P] ;
depiler(P) ;
dansPile[y]=Faux comp[y]=k
Jusque y=x
Fin Si
Fin Procedure

End
Start
Graphe G
Pile
parcours: DFS de G
Pile
1
2
3
4
5
A
F
E
C
G
CFC
Kosaraju
2 parcours DFS
O(V²)

Tarjan
1 parcours DFS
O(V+E)

Tarjan
est
plus rapide
que
Kosaraju

6
H
Fils(A)= { F,B}
Fils(F)= {E}
Fils(E)= {C,F}
Fils(C)= {G}
Fils(G)={H}
Fils(H)={C} appartient à P
CFC1
H
G
C
CFC1
parcours: DFS de G
Pile
1
2
3
A
F
E
Fils(A)= { F,B}
Fils(F)= {E}
Fils(E)= {F} appartient à P
CFC2
E
F
CFC2
CFC1
parcours: DFS de G
Pile
A
B
D
Fils(A)= { B}
Fils(B)= {D}
Fils(D)= {A} appartient à P
CFC3
B
A
D
1
2
3
CFC1
CFC3
CFC2
CFC1
CFC3
CFC2
CFC1
Full transcript