Arbres
Couvrants
Definition : Un arbre couvrant d un graphe G=(V,E) est
un sous-graphe G=(V,E ) tel que
n G est un arbre
n E ⊆ E
Le poids d un arbre couvrant est défini par
W= ∑ M [i, j]
i , j∈E '
Arbres
couvrants
4
9
Arbre
couvrant
minimal
:
1
4
9
5
6
2
G
:
graphe
4
7
3
nconnexe
2
9
3
nvalué
8
10
nnon
orienté
9
9
Trouver
un
ensemble
d arrêtes:
9
8
18
n
connectant
tous
les
sommets
n
de
poids
minimal
Algorithme
de
Prim
:
Choisir
un
sommet
arbitraire
faire
croitre
un
arbre
à
par?r
de
ce
sommet
de
la
manière
la
plus
économique
possible
Arbres
couvrants
Algorithme
de
Prim
[Froidevaux]
Procedure Prim(s,G)
entier s; /* sommet initial*/
graph G =(S,A,C) /*sommets/arrêtes/cout*/
Variables :
graph T /* l abre en construction*/
int i, m, y ;
real : v ;
Set : M /* sommets non étudiés*/
int closer[1..N] /* plus proche sommet de T*/
real d[1..N] /* plus petite distance entre
un sommet et un sommet de l arbre*/
Arbres
couvrants
Algorithme
de
Prim
(suite)
T := graphe_vide!
M := ensemble_vide !
Pour i= 0 jusqu'à N Faire !
!d[i] := coût(s, i, G) /* ∝ si pas d arc */!
!closer[i] := s !
!M := Ajouter (i,M) !
Fin pour !
!
M := Supprimer (s,M) /* s = sommet de départ */!
!
Tant que M <> Ensemble_vide Faire !
!m := Choisir_min(M,d)!
!M := Supprimer (m,M) !
!z := closer[m] !
!v := coût (m,z,G) !
!T := Ajout arête <m,z> de coût v à T !
!Pour tout y successeur de m dans G !
! !Si y∈M et (cout(m,y,G) < d[y]) alors !
! ! !d[y] := coût(m,y,G) !
! ! !closer[y] := m !
! !Fin Si !
!Fin Pour !
Fin Tant que!
4
9
1
4
9
5
6
2
4
7
3
3
2
9
8
10
9
9
9
8
18
4
9
1
4
9
5
6
2
4
7
3
3
2
9
8
10
9
9
9
8
18
4
9
1
4
9
5
6
2
4
7
3
3
2
9
8
10
9
9
9
8
18
4
9
1
4
9
5
6
2
4
7
3
3
2
9
8
10
9
9
9
8
18
Etc…
Arbres
couvrants
Prim fonctionne par parcours de l arbre en choisissant
les poids minimum
Complexité : O( |V| x |E| )
M,d,closer modélisent en fait un ensemble d arrêtes.
Chaque arrête ne peut être choisie qu une fois
Pour chaque nouvelle arrête ajoutée, on recherche de nouveaux
successeurs (au plus |V| )
Peut être amélioré en O( |E| x log(|V|) ) si
M est modélisé par un tas
