Notes de maths de niveau A : D1 ± Algorithme de Prim dans le tableau

Forme

L'algorithme de Prim pour l'arbre couvrant minimum est également adapté à une utilisation sur les distances.
tables, ou l'équivalent pour le problème. Cela est utile pour les grands problèmes où
Dessiner le diagramme de réseau serait difficile ou chronophage.

Le fait que des tables puissent être utilisées rend l'algorithme plus adapté à l'automatisation que
L'algorithme de Kruskal. La raison en est que les données utilisées devraient être triées.
à utiliser avec l'algorithme de Kruskal. Avec l'algorithme de Prim, cependant, c'est seulement le
valeur minimale qui est d'intérêt, donc aucun tri n'est normalement nécessaire.

L'algorithme de Prim a les étapes suivantes.

1. Choisissez un nœud de départ. Rayez la ligne correspondant à ce nœud.

2. Étiquetez la colonne correspondant à ce nœud (1). Cherchez le minimum
nombre dans la colonne (1) et mettre des parenthèses autour.
3. Barrer la ligne de cette valeur minimale. Trouvez le nœud de cette ligne et étiquetez-le.
la colonne correspondante (2).
4. Recherchez le nombre minimum dans les colonnes (1) ou (2). Encerclez-le, rayez-le.
ligne, étiquetez la colonne et continuez de cette manière jusqu'à ce que toutes les colonnes soient
étiqueté.
5. La longueur de l'arbre couvrant minimal est la somme des nombres entre crochets.

Le tableau des distances pour le tableau ci-dessus est

 Un B C D E F G

Un - 4 5 - - - 11

B 4 - neuf 6 - - -

C 5 9 - - 1 - 2

D - 6 - - - 10 -

E - - 1 - - 4 -

F - - - 10 4 - 10

G 11 - 2 - - 10 -

L'arbre couvrant minimal aura la même longueur peu importe le nœud à partir duquel nous commençons.
est après tout, le minimum. Je commencerai par C, car BC est la longueur minimale.

(1)

A B C D E F G

Un - 4 5 - - - 11

B 4 - 9 6 - - -

C 5 9 - - 1 - 2

D - 6 - - - 10 -

E - - (1) - - 4 -

F - - - 10 4 - 10

G 11 - 2 - - 10 -

Le plus petit nombre libre dans la colonne (1) dans la colonne (1) est 1, correspondant à E. Croiser
sortez la ligne E et étiquetez la colonne E comme (2).
 (1) (2)

Un B C D E F G

A - 4 5 - - - 11

B 4 - 9 6 - - -

C 5 9 - - 1 - 2

D - 6 - - - dix -

E - - (1) - - 4 -

F - - - 10 4 - 10

G 11 - 2 - - 10 -

Maintenant, cherchez le plus petit nombre libre dans la colonne (1) ou (2). C'est 2 dans la ligne G.
Barrez la ligne G et étiquetez la colonne G comme (3).

(1) (2) (3)

Un B C D E F G

Un - 4 5 - - - 11

B 4 - 9 6 - - -

C 5 9 - - 1 - 2

D - 6 - - - 10 -

E - - (1) - - 4 -

F - - - 10 4 - 10

G 11 - (2) - - 10 -
Cherchez le plus petit nombre libre dans les colonnes (1), (2) ou (3). C'est 4 dans la ligne F. Barrez
ligne F et étiquetez la colonne F comme (4).

(1) (2) (4) (3)

Un B C D E F G

A - 4 5 - - - 11

B 4 - 9 6 - - -

C 5 9 - - 1 - 2

D - 6 - - - 10 -

E - - (1) - - 4 -

F - - - 10 (4) - 10

G 11 - (2) - - 10 -

Cherchez le plus petit numéro libre dans les colonnes (1), (2), (3) ou (4). C'est 5 dans la ligne A.
Rayer la ligne A et étiqueter la colonne A comme (5).

(5) (1) (2) (4) (3)

Un B C D E F G

Un - 4 (5) - - - 11

B 4 - 9 6 - - -

C 5 9 - - 1 - 2

D - 6 - - - 10 -

E - - (1) - - 4 -

F - - - 10 (4) - 10
 G 11 - (2) - - dix -

Le plus petit nombre libre dans les colonnes (1), (2), (3), (4) ou (5) est 4 dans la ligne B. Barrer
ligne B et étiquetez la colonne B comme (6).

(5) (6) (1) (2) (4) (3)

Un B C D E F G

A - 4 (5) - - - 11

B (4) - 9 6 - - -

C 5 9 - - 1 - 2

D - 6 - - - 10 -

E - - (1) - - 4 -

F - - - dix (4) - 10

G 11 - (2) - - 10 -

Le plus petit nombre libre dans les colonnes (1), (2), (3), (4), (5) ou (6) est 6 dans la ligne D. Croisez
sortir la ligne D et étiqueter la colonne D comme (7).

(5) (6) (1) (7) (2) (4) (3)

Un B C D E F G

A - 4 (5) - - - 11

B (4) - 9 6 - - -

C 5 9 - - 1 - 2
 D - (6) - - - 10 -

E - - (1) - - 4 -

F - - - 10 (4) - 10

G 11 - (2) - - 10 -

La longueur de l'arbre couvrant minimal est de 1+2+4+4+5+6=22

Home Maths and Physics Notes Home A Level Maths Notes Home D1 Maths Notes
Accueil

Agence de Tuteurs pour Forum Étudiant