ΠΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π³ΡΠ°ΡΠ° ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΡΠΈΠΌΠ°
ΠΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ (ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π, Π) Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ. Π‘Π½Π°ΡΠ°Π»Π° ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²ΠΎΠ΄ΠΈΡ ΠΏΠΎΡΡΠ΄ΠΎΠΊ Π³ΡΠ°ΡΠ°, ΡΡΠΎΠ±Ρ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΌΠΎΠ³Π»Π° ΡΡΠΎΡΠΌΠΈΡΠΎΠ²Π°ΡΡ ΡΠ°Π±Π»ΠΈΡΡ Π²Π²ΠΎΠ΄Π° Π΄Π°Π½Π½ΡΡ (ΠΌΠ°ΡΡΠΈΡΠ° Π²Π΅ΡΠΎΠ²) Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎΠΌ ΡΡΡΠΎΠΊ ΠΈ ΡΡΠΎΠ»Π±ΡΠΎΠ². ΠΡΠΈ ΡΡΠΎΠΌ Π²ΡΠ΅ ΠΊΠ½ΠΎΠΏΠΊΠΈ, ΠΊΡΠΎΠΌΠ΅ ΠΊΠ½ΠΎΠΏΠΊΠΈ «Π‘Π΄Π΅Π»Π°ΡΡ ΡΠ°Π±Π»ΠΈΡΡ» Π½Π΅Π΄ΠΎΡΡΡΠΏΠ½Ρ Π΄Π»Ρ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ. ΠΠ°ΡΠ΅ΠΌ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²ΠΎΠ΄ΠΈΡ Π² ΡΠ°Π±Π»ΠΈΡΡ Π΄Π°Π½Π½ΡΠ΅, ΠΏΡΠΈ ΡΡΠΎΠΌ ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ ΠΎΡΡΠ°Π²Π»ΡΡΡ ΠΏΡΡΡΡΠ΅ ΡΡΠ΅ΠΉΠΊΠΈ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
ΠΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π³ΡΠ°ΡΠ° ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΡΠΈΠΌΠ° (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠΎΡΡΠ½ΠΈΡΠ΅Π»ΡΠ½Π°Ρ Π·Π°ΠΏΠΈΡΠΊΠ°
ΠΊ ΠΊΡΡΡΠΎΠ²ΠΎΠΌΡ ΠΏΡΠΎΠ΅ΠΊΡΡ ΡΠ΅ΠΌΠ°: ΠΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π³ΡΠ°ΡΠ° ΠΌΠ΅ΡΠΎΠ΄ΠΎΠΌ ΠΡΠΈΠΌΠ°
ΠΡΠΈ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΆΠ΅Π»Π΅Π·Π½ΡΡ Π΄ΠΎΡΠΎΠ³, Π»ΠΈΠ½ΠΈΠΉ ΡΠ»Π΅ΠΊΡΡΠΎΠΏΠ΅ΡΠ΅Π΄Π°ΡΠΈ ΠΈ Π΄ΡΡΠ³ΠΈΡ Π»ΠΈΠ½ΠΈΠΉ ΠΊΠΎΠΌΠΌΡΠ½ΠΈΠΊΠ°ΡΠΈΠΈ Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠ° ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΡΠ΅ΡΠΈ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌΠΈ Π·Π°ΡΡΠ°ΡΠ°ΠΌΠΈ. Π ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² ΡΠ°ΠΊΠ°Ρ Π·Π°Π΄Π°ΡΠ° ΡΡΠΏΠ΅ΡΠ½ΠΎ ΡΠ΅ΡΠ°Π΅ΡΡΡ ΠΏΡΡΠ΅ΠΌ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°. ΠΠ°Π½Π½Π°Ρ Π·Π°Π΄Π°ΡΠ° ΠΈΠΌΠ΅Π΅Ρ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΡΠ΅ΡΠ΅Π½ΠΈΡ. ΠΠ΄ΠΈΠ½ ΠΈΠ· Π½ΠΈΡ — Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΠΈΠΌΠ°. Π‘ΡΡΡ ΡΡΠΎΠ³ΠΎ ΠΌΠ΅ΡΠΎΠ΄Π° Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΠΌ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠΈ ΠΊ ΠΎΡΡΠΎΠ²Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ, «Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ³ΠΎ» ΡΠ΅Π±ΡΠ° (ΡΠ΅Π±ΡΠ°, ΠΊΠΎΡΠΎΡΠΎΠ΅ Π½Π΅ ΠΎΠ±ΡΠ°Π·ΡΠ΅Ρ ΡΠΈΠΊΠ»Π°). Π Π΄Π°Π½Π½ΠΎΠΉ ΡΠ°Π±ΠΎΡΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°, Π±Π°Π·ΠΈΡΡΡΡΠ°ΡΡΡ Π½Π° Π°Π»Π³ΠΎΡΠΈΡΠΌΠ΅ ΠΡΠΈΠΌΠ°, ΠΊΠΎΡΠΎΡΠ°Ρ Π²ΡΡΠΈΡΠ»ΡΠ΅Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΎΡΡΠΎΠ²Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° ΠΈ Π΄Π΅Π»Π°Π΅Ρ Π²ΠΈΠ·ΡΠ°Π»ΠΈΠ·Π°ΡΠΈΡ Π³ΡΠ°ΡΠ°.
1. ΠΡΡΠΎΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΡΠΏΡΠ°Π²ΠΊΠ°
ΠΠ·Π²Π΅ΡΡΠ½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π²ΠΎΡΡ ΠΎΠ΄ΠΈΡ ΠΊ ΠΠΎΠΉΡΠ΅Ρ Ρ Π―ΡΠ½ΠΈΠΊΡ (Vojtech Jarnik). ΠΠ½ Π±ΠΎΠ»ΡΡΠ΅ ΠΈΠ·Π²Π΅ΡΡΠ΅Π½ ΠΏΠΎΠ΄ ΠΈΠΌΠ΅Π½Π΅ΠΌ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΡΠΈΠΌΠ° (Robert Prim). Π . ΠΡΠΈΠΌ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎ ΠΎΡ Π―ΡΠ½ΠΈΠΊΠ° ΠΏΡΠΈΠ΄ΡΠΌΠ°Π» Π΅Π³ΠΎ Π² 1956 ΠΈ ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΠ» Π±ΠΎΠ»Π΅Π΅ ΠΏΠΎΠ΄ΡΠΎΠ±Π½ΠΎΠ΅ ΠΈ Π΄Π΅ΡΠ°Π»ΡΠ½ΠΎΠ΅ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠ΅, ΡΠ΅ΠΌ ΠΏΠ΅ΡΠ²ΠΎΠΎΡΠΊΡΡΠ²Π°ΡΠ΅Π»Ρ. ΠΡΠ΅ ΡΠ°Π· ΡΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΎΡΠΊΡΡΠ» ΠΠ΄ΡΠ³Π΅Ρ ΠΠ΅ΠΉΠΊΡΡΡΠ° (Edsger Wybe Dijkstra) Π² 1958 Π³ΠΎΠ΄Ρ, Π½ΠΎ Π½Π°Π·Π²Π°Π½ΠΈΠ΅ ΠΎΡΡΠ°Π»ΠΎΡΡ Π·Π° ΠΡΠΈΠΌΠΎΠΌ, Ρ. ΠΊ. Ρ ΠΠ΅ΠΉΠΊΡΡΡΡ ΡΠΆΠ΅ Π±ΡΠ» Π°Π»Π³ΠΎΡΠΈΡΠΌ Ρ Π΅Π³ΠΎ ΠΈΠΌΠ΅Π½Π΅ΠΌ (ΠΏΠΎΠΈΡΠΊ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΡ ΠΏΡΡΠ΅ΠΉ Π² ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΌ Π³ΡΠ°ΡΠ΅). ΠΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΌΠΎΠΆΠ½ΠΎ ΠΎΡΠ½Π΅ΡΡΠΈ ΠΊ Π³ΡΡΠΏΠΏΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ², ΠΏΠΎΡΡΡΠΎΠ΅Π½Π½ΡΡ Π½Π° Π½Π°ΡΠ°ΡΠΈΠ²Π°Π½ΠΈΠΈ Π΄Π΅ΡΠ΅Π²Π°: ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄Π½Π° Π½Π΅ΡΡΠΈΠ²ΠΈΠ°Π»ΡΠ½Π°Ρ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΠ° (ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡ ΡΠΎΠ±ΠΎΠΉ ΠΎΠ΄ΠΈΠ½ΠΎΡΠ½ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ), ΠΈ ΠΎΠ½Π° ΠΏΠΎΡΡΠ΅ΠΏΠ΅Π½Π½ΠΎ Π½Π°ΡΠ°ΡΠΈΠ²Π°Π΅ΡΡΡ Π΄ΠΎΠ±Π°Π²Π»Π΅Π½ΠΈΠ΅ΠΌ «Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΡ » ΡΠ΅Π±Π΅Ρ. ΠΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΠΆΠ°ΡΠ½ΠΈΠΊΠ°-ΠΡΠΈΠΌΠ° ΠΌΠΎΠΆΠ΅Ρ Π΄ΠΎΡΡΠΈΠ³Π°ΡΡ O (E+VlogV) ΠΏΡΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ ΡΠΈΠ±ΠΎΠ½Π°ΡΡΠΈΠ΅Π²ΡΡ ΠΊΡΡ.
2. ΠΠΎΡΡΡΠΎΠ΅Π½ΠΈΠ΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π°
Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΎΠ±ΡΡΡ ΡΡ Π΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ ΠΆΠ°Π΄Π½ΠΎΠΉ ΡΡΡΠ°ΡΠ΅Π³ΠΈΠΈ. ΠΡΠ°ΠΊ, ΠΏΡΡΡΡ Π΄Π°Π½ ΡΠ²ΡΠ·Π½ΡΠΉ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ G (V; E) c n Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΠΈ Π²Π΅ΡΠΎΠ²Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ w: E > R.
ΠΡΠΊΠΎΠΌΡΠΉ ΠΎΡΡΠΎΠ² ΡΡΡΠΎΠΈΡΡΡ ΠΏΠΎΡΡΠ΅ΠΏΠ΅Π½Π½ΠΎ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΠΎΠ΄Π³ΡΠ°Ρ Π ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° G, ΠΊΠΎΡΠΎΡΡΠΉ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΠΎΠΌΠ΅ΠΆΡΡΠΎΡΠ½ΡΠΌ ΠΎΡΡΠΎΠ²Π½ΡΠΌ Π»Π΅ΡΠΎΠΌ. ΠΠ·Π½Π°ΡΠ°Π»ΡΠ½ΠΎ G ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· n Π²Π΅ΡΡΠΈΠ½-ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ, Π½Π΅ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π½ΡΡ Π΄ΡΡΠ³ Ρ Π΄ΡΡΠ³ΠΎΠΌ (n Π΄Π΅ΡΠ΅Π²ΡΠ΅Π² ΠΈΠ· ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ). ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ Π² A Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΡΡΡ ΠΎΠ΄Π½ΠΎ Π½ΠΎΠ²ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ. ΠΡΠ°Ρ A Π²ΡΠ΅Π³Π΄Π° ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΠ΄Π³ΡΠ°ΡΠΎΠΌ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π°. ΠΡΠ΅ΡΠ΅Π΄Π½ΠΎΠ΅ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΠΌΠΎΠ΅ ΡΠ΅Π±ΡΠΎ e=(u, v) Π²ΡΠ±ΠΈΡΠ°Π΅ΡΡΡ ΡΠ°ΠΊ, ΡΡΠΎΠ±Ρ Π½Π΅ Π½Π°ΡΡΡΠΈΡΡ ΡΡΠΎΠ³ΠΎ ΡΠ²ΠΎΠΉΡΡΠ²Π°: A? {e} ΡΠΎΠΆΠ΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Π±ΡΡΡ ΠΏΠΎΠ΄Π³ΡΠ°ΡΠΎΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ. Π’Π°ΠΊΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠΌ.
ΠΠΎΡ ΠΊΠ°ΠΊ Π²ΡΠ³Π»ΡΠ΄ΠΈΡ ΠΎΠ±ΡΠΈΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π°:
MST-GENERIC (G, w)
1: A < 0
2: while (ΠΏΠΎΠΊΠ°) A Π½Π΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΎΡΡΠΎΠ²ΠΎΠΌ
3: do Π½Π°ΠΉΡΠΈ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ (u, v)? E Π΄Π»Ρ A
4: A < A? {(u, v)}
5: return A
ΠΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ A, ΠΎΠ½ Π΄ΠΎΠ»ΠΆΠ΅Π½ ΠΎΡΡΠ°Π²Π°ΡΡΡΡ ΠΏΠΎΠ΄Π³ΡΠ°ΡΠΎΠΌ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π° ΠΏΠΎΡΠ»Π΅ Π»ΡΠ±ΠΎΠ³ΠΎ ΡΠΈΡΠ»Π° ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ. ΠΠΎΠ½Π΅ΡΠ½ΠΎ, Π³Π»Π°Π²Π½ΡΠΉ Π²ΠΎΠΏΡΠΎΡ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΠΊΠ°ΠΊ ΠΈΡΠΊΠ°ΡΡ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Π½Π° ΡΠ°Π³Π΅ 3. ΠΠΎΠ½ΡΡΠ½ΠΎ, ΡΡΠΎ ΡΠ°ΠΊΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Π²ΡΠ΅Π³Π΄Π° ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ, Π΅ΡΠ»ΠΈ A Π΅ΡΠ΅ Π½Π΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΎΡΡΠΎΠ²ΠΎΠΌ (Π»ΡΠ±ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ ΠΎΡΡΠΎΠ²Π°, Π½Π΅ Π²Ρ ΠΎΠ΄ΡΡΠ΅Π΅ Π² A). ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ ΡΠ°ΠΊ ΠΊΠ°ΠΊ A Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΡ ΡΠΈΠΊΠ»ΠΎΠ², ΡΠΎ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΡΠ΅Π±ΡΠΎΠΌ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΡΡ ΡΠ°Π·Π»ΠΈΡΠ½ΡΠ΅ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΡ ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ (ΠΈΠ·Π½Π°ΡΠ°Π»ΡΠ½ΠΎ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ Π² ΠΎΡΠ΄Π΅Π»ΡΠ½ΡΡ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΠ°Ρ , Π² ΠΊΠΎΠ½ΡΠ΅ A — ΠΎΠ΄Π½Π° ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΠ°). Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ ΡΠΈΠΊΠ» Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ (n-1) ΡΠ°Π·.
ΠΠ°Π»Π΅Π΅ ΠΏΡΠΈΠ²ΠΎΠ΄ΠΈΡΡΡ ΠΎΠ±ΡΠ΅Π΅ ΠΏΡΠ°Π²ΠΈΠ»ΠΎ ΠΎΡΡΡΠΊΠ°Π½ΠΈΡ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΡ ΡΠ΅Π±Π΅Ρ. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ Π΄ΠΎΠΊΠ°Π·Π°Π½Π° ΡΠ΅ΠΎΡΠ΅ΠΌΠ°, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΠΎΠΌΠΎΠΆΠ΅Ρ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠ΅ ΡΠ΅Π±ΡΠ°. ΠΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ Π΄ΠΎΠΊΠ°ΠΆΠ΅ΠΌ ΠΌΠ°Π»Π΅Π½ΡΠΊΡΡ Π»Π΅ΠΌΠΌΡ:
ΠΠ΅ΠΌΠΌΠ°: ΠΏΡΡΡΡ Π’ — ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΎΡΡΠΎΠ²Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ. Π’ΠΎΠ³Π΄Π° Π»ΡΠ±ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Π΅ ΠΈΠ· T — Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅.
ΠΠΎΠΊ-Π²ΠΎ: Π² Π’ — (n-1) ΡΠ΅Π±ΡΠΎ. ΠΠ° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ Generic-MST ΠΌΡ Π΄ΠΎΠ±Π°Π²Π»ΡΠ»ΠΈ ΠΎΠ΄Π½ΠΎ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ. ΠΡΠ΅Π³ΠΎ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΎ (n-1) ΡΠ°Π³ΠΎΠ², ΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, Π²ΡΠ΅ ΡΠ΅Π±ΡΠ° Π² T — Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠ΅ ΠΏΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ.
Π’Π΅ΠΎΡΠ΅ΠΌΠ°: ΠΡΡΡΡ G (V; E) — ΡΠ²ΡΠ·Π½ΡΠΉ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ ΠΈ Π½Π° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π΅ Π ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π° Π²Π΅ΡΠΎΠ²Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ w. ΠΡΡΡΡ, Π — Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΠΎΠ΄Π³ΡΠ°Ρ G, ΡΠ²Π»ΡΡΡΠΈΠΉΡΡ Π² ΡΠΎ ΠΆΠ΅ Π²ΡΠ΅ΠΌΡ ΠΏΠΎΠ΄Π³ΡΠ°ΡΠΎΠΌ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° T. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΡ ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ Π ΠΈΠ· Π. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ E (K) ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ° G, ΡΠΎΠ»ΡΠΊΠΎ ΠΎΠ΄ΠΈΠ½ ΠΊΠΎΠ½Π΅Ρ ΠΊΠΎΡΠΎΡΡΡ Π»Π΅ΠΆΠΈΡ Π² Π. Π’ΠΎΠ³Π΄Π° ΡΠ΅Π±ΡΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ Π²Π΅ΡΠ° ΠΈΠ· E (K) Π±ΡΠ΄Π΅Ρ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠΌ.
ΠΠΎΠΊ-Π²ΠΎ: ΠΡΡΡΡ e=(u, v) — ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΏΠΎ Π²Π΅ΡΡ ΡΠ΅Π±ΡΠΎ ΠΈΠ· E(K). ΠΡΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΎΡΡΠΎΠ² T Π½Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ e (Π² ΠΏΡΠΎΡΠΈΠ²Π½ΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π΄ΠΎΠΊΠ°Π·ΡΠ²Π°Π΅ΠΌΠΎΠ΅ ΡΡΠ²Π΅ΡΠΆΠ΄Π΅Π½ΠΈΠ΅ ΠΎΡΠ΅Π²ΠΈΠ΄Π½ΠΎ ΠΏΠΎ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ Π²ΡΡΠ΅ Π»Π΅ΠΌΠΌΠ΅). Π’.ΠΊ. T ΡΠ²ΡΠ·Π΅Π½, Π² Π½Π΅ΠΌ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π½Π΅ΠΊΠΎΡΠΎΡΡΠΉ (Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΡΠΉ) Π°ΡΠΈΠΊΠ»ΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΏΡΡΡ p ΠΈΠ· u Π² v, ΠΈ e Π·Π°ΠΌΡΠΊΠ°Π΅Ρ Π΅Π³ΠΎ Π² ΡΠΈΠΊΠ». ΠΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΊΠΎΠ½ΡΠΎΠ² e Π»Π΅ΠΆΠΈΡ Π² K, Π° Π΄ΡΡΠ³ΠΎΠΉ Π² V K, Π² ΠΏΡΡΠΈ p ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Ρ ΠΎΡΡ Π±Ρ ΠΎΠ΄Π½ΠΎ ΡΠ΅Π±ΡΠΎ e'=(x, y), ΠΊΠΎΡΠΎΡΠΎΠ΅ ΠΎΠ±Π»Π°Π΄Π°Π΅Ρ ΡΠ΅ΠΌ ΠΆΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²ΠΎΠΌ. ΠΡΠΎ ΡΠ΅Π±ΡΠΎ Π½Π΅ Π»Π΅ΠΆΠΈΡ Π² A, Ρ. ΠΊ. Π² A ΠΏΠΎΠΊΠ° ΡΡΠΎ Π½Π΅Ρ ΡΠ΅Π±Π΅Ρ ΠΌΠ΅ΠΆΠ΄Ρ K ΠΈ V K. Π£Π΄Π°Π»ΠΈΠΌ ΠΈΠ· T ΡΠ΅Π±ΡΠΎ e' ΠΈ Π΄ΠΎΠ±Π°Π²ΠΈΠΌ e. Π’Π°ΠΊ ΠΊΠ°ΠΊ w(e') < w(e), ΠΌΡ ΠΏΠΎΠ»ΡΡΠΈΠΌ ΠΎΡΡΠΎΠ²Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ T', ΡΡΠΌΠΌΠ°ΡΠ½ΡΠΉ Π²Π΅Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΠΌΠ΅Π½ΡΡΠ΅ ΡΡΠΌΠΌΠ°ΡΠ½ΠΎΠ³ΠΎ Π²Π΅ΡΠ° T. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, T Π½Π΅ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΠΎΡΡΠΎΠ²ΠΎΠΌ. ΠΡΠΎΡΠΈΠ²ΠΎΡΠ΅ΡΠΈΠ΅. Π‘Π»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎ, T ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ e.
Π ΡΠ²ΡΠ·ΠΈ Ρ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½Π½ΠΎΠΉ ΡΠ΅ΠΎΡΠ΅ΠΌΠΎΠΉ Π²Π²Π΅Π΄Π΅ΠΌ ΡΠ»Π΅Π΄ΡΡΡΠ΅Π΅
ΠΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΠ΅. ΠΠ΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠΌ ΡΠ΅Π±ΡΠΎΠΌ e ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΠΎ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΡ ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ Π ΠΈΠ·, Π Π½Π°Π·ΠΎΠ²Π΅ΠΌ ΡΠ΅Π±ΡΠΎ Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ Π²Π΅ΡΠΎΠΌ, ΡΠΎΠ²Π½ΠΎ ΠΎΠ΄ΠΈΠ½ ΠΊΠΎΠ½Π΅Ρ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π»Π΅ΠΆΠΈΡ Π² Π.
3. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΡΠΈΠΌΠ°
ΠΠ°ΠΊ ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΠ°ΡΠΊΠ°Π»Π°, Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΠΈΠΌΠ° ΡΠ»Π΅Π΄ΡΠ΅Ρ ΠΎΠ±ΡΠ΅ΠΉ ΡΡ Π΅ΠΌΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π°: Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΠΌΡ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΠΌ ΠΊ ΡΡΡΠΎΡΡΠ΅ΠΌΡΡΡ ΠΎΡΡΠΎΠ²Ρ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΡΠΈΠΌΠ° ΠΎΡΠ½ΠΎΡΠΈΡΡΡ ΠΊ Π³ΡΡΠΏΠΏΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π½Π°ΡΠ°ΡΠΈΠ²Π°Π½ΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π°: Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ Π½Π΅ Π±ΠΎΠ»Π΅Π΅ ΠΎΠ΄Π½ΠΎΠΉ Π½Π΅ΡΡΠΈΠ²ΠΈΠ°Π»ΡΠ½ΠΎΠΉ (Π½Π΅ ΡΠΎΡΡΠΎΡΡΠ΅ΠΉ ΠΈΠ· ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ) ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΡ ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ, ΠΈ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΊ Π½Π΅ΠΉ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΡΡΡ ΡΠ΅Π±ΡΠΎ Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅Π³ΠΎ Π²Π΅ΡΠ°, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠ΅Π΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΡ Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΠΌΠΈ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ. ΠΠΎ ΡΠ΅ΠΎΡΠ΅ΠΌΠ΅ ΡΠ°ΠΊΠΎΠ΅ ΡΠ΅Π±ΡΠΎ ΡΠ²Π»ΡΠ΅ΡΡΡ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠΌ.
ΠΡΠΈ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ Π½Π°Π΄ΠΎ ΡΠΌΠ΅ΡΡ Π½Π° ΠΊΠ°ΠΆΠ΄ΠΎΠΌ ΡΠ°Π³Π΅ Π±ΡΡΡΡΠΎ Π²ΡΠ±ΠΈΡΠ°ΡΡ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΡΠ΄ΠΎΠ±Π½ΠΎ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΠΎΡΠ΅ΡΠ΅Π΄ΡΡ Ρ ΠΏΡΠΈΠΎΡΠΈΡΠ΅ΡΠ°ΠΌΠΈ (ΠΊΡΡΠ΅ΠΉ). ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠ»ΡΡΠ°Π΅Ρ Π½Π° Π²Ρ ΠΎΠ΄ Π³ΡΠ°Ρ G ΠΈ Π΅Π³ΠΎ ΠΊΠΎΡΠ΅Π½Ρ r — Π²Π΅ΡΡΠΈΠ½Π°, Π½Π° ΠΊΠΎΡΠΎΡΠΎΠΉ Π±ΡΠ΄Π΅Ρ Π½Π°ΡΠ°ΡΠΈΠ²Π°ΡΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΎΡΡΠΎΠ². ΠΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ G, Π΅ΡΠ΅ Π½Π΅ ΠΏΠΎΠΏΠ°Π²ΡΠΈΠ΅ Π² Π΄Π΅ΡΠ΅Π²ΠΎ, Ρ ΡΠ°Π½ΡΡΡΡ Π² ΠΎΡΠ΅ΡΠ΅Π΄ΠΈ Ρ ΠΏΡΠΈΠΎΡΠΈΡΠ΅ΡΠΎΠΌ Π©. ΠΡΠΈΠΎΡΠΈΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½Ρ v ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅ΡΡΡ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ key[v], ΠΊΠΎΡΠΎΡΠΎΠ΅ ΡΠ°Π²Π½ΠΎ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ Π²Π΅ΡΡ ΡΠ΅Π±Π΅Ρ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠΈΡ v Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π°. ΠΠΎΠ»Π΅ p[v] Π΄Π»Ρ Π²Π΅ΡΡΠΈΠ½ Π΄Π΅ΡΠ΅Π²Π° ΡΠΊΠ°Π·ΡΠ²Π°Π΅Ρ Π½Π° ΡΠΎΠ΄ΠΈΡΠ΅Π»Ρ, Π° Π΄Π»Ρ Π²Π΅ΡΡΠΈΠ½ ΠΈΠ· ΠΎΡΠ΅ΡΠ΅Π΄ΠΈ, ΡΠΊΠ°Π·ΡΠ²Π°Π΅Ρ Π½Π° Π½ΠΎΠ΄Ρ Π΄Π΅ΡΠ΅Π²Π°, Π² ΠΊΠΎΡΠΎΡΠΎΡ Π²Π΅Π΄Π΅Ρ ΡΠ΅Π±ΡΠΎ Ρ Π²Π΅ΡΠΎΠΌ key[v] (ΠΎΠ΄Π½ΠΎ ΠΈΠ· ΡΠ°ΠΊΠΈΡ ΡΠ΅Π±Π΅Ρ, Π΅ΡΠ»ΠΈ ΠΈΡ Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ).
Π’ΠΎΠ³Π΄Π° Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΠΈΠΌΠ° Π²ΡΠ³Π»ΡΠ΄ΠΈΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ:
MST-PRIM (G, w, r)
1: Π© < V[G]
2: foreach (Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ) Π²Π΅ΡΡΠΈΠ½Ρ u? Π©
3: do key[u] < ?
4: key[r] < 0
5: p[r] = NIL
6: while (ΠΏΠΎΠΊΠ°) Π©? 0
7: do u < EXTRACT-MIN (Π©)
8: foreach (Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ) Π²Π΅ΡΡΠΈΠ½Ρ v? Adj (u)
9: do if v? Π© ΠΈ w (u, v) < key[v] then
10: p[v] < u
11: key[v] < w (u, v)
ΠΠ° ΡΠΈΡΡΠ½ΠΊΠ°Ρ 1−8 ΠΏΠΎΠΊΠ°Π·Π°Π½Π° ΡΡ Π΅ΠΌΠ° ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΡΠΈΠΌΠ° Ρ ΠΊΠΎΡΠ½Π΅ΠΌ r.
Π ΠΈΡΡΠ½ΠΎΠΊ 1 — ΠΠ°ΡΠ°Π»ΡΠ½Π°Ρ ΡΠ°Π·Π°. ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΠΏΠΎΠΊΡΡΠ²Π°ΡΡΠΈΠΉ Π»Π΅Ρ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· ΠΊΠΎΡΠ½Ρ ΠΈ ΠΏΡΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΡΠ΅Π±Π΅Ρ
Π ΠΈΡΡΠ½ΠΎΠΊ 2 — Π Π΅Π±ΡΠΎ Ρ Π²Π΅ΡΠΎΠΌ 6 ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΌ ΡΠ΅Π±ΡΠΎ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠΈΠΌ ΠΊΠΎΡΠ΅Π½Ρ Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΠΌΠΈ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ. ΠΠΎΠ±Π°Π²Π»ΡΠ΅ΠΌ Π΅Π³ΠΎ ΠΊ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΌΡ ΠΎΡΡΠΎΠ²Ρ.
Π ΠΈΡΡΠ½ΠΎΠΊ 3 — Π‘Π»Π΅Π΄ΡΡΡΠ΅Π΅ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Ρ Π²Π΅ΡΠΎΠΌ 11. ΠΠΎΠ±Π°Π²Π»ΡΠ΅ΠΌ Π΅Π³ΠΎ
Π ΠΈΡ. 4
Π ΠΈΡΡΠ½ΠΎΠΊ 5
Π ΠΈΡΡΠ½ΠΎΠΊ 6
Π ΠΈΡΡΠ½ΠΎΠΊ 7
Π ΠΈΡΡΠ½ΠΎΠΊ 8 — Π Π΅Π±ΡΠ° Ρ Π²Π΅ΡΠΎΠΌ 17, 19 ΠΈ 25 — Π½Π΅ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΡΠ΅. ΠΡ ΠΊΠΎΠ½ΡΡ Π»Π΅ΠΆΠ°Ρ Π² ΠΎΠ΄Π½ΠΎΠΉ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½ΡΠ΅ ΡΠ²ΡΠ·Π½ΠΎΡΡΠΈ. Π Π΅Π±ΡΠΎ Ρ Π²Π΅ΡΠΎΠΌ 21 — Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΠ΅, ΠΏΠΎΡΡΠΎΠΌΡ Π΄ΠΎΠ±Π°Π²Π»ΡΠ΅ΠΌ Π΅Π³ΠΎ. ΠΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ΅ ΠΎΡΡΠΎΠ²Π½ΠΎΠ΅ Π΄Π΅ΡΠ΅Π²ΠΎ ΠΏΠΎΡΡΡΠΎΠ΅Π½ΠΎ.
ΠΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΡΠΈΠΌΠ° Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ ΡΠΎΠ³ΠΎ, ΠΊΠ°ΠΊ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½Π° ΠΎΡΠ΅ΡΠ΅Π΄Ρ Ρ ΠΏΡΠΈΠΎΡΠΈΡΠ΅ΡΠ°ΠΌΠΈ Π©. ΠΡΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ Π΄Π²ΠΎΠΈΡΠ½ΡΡ ΠΊΡΡΡ, ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·Π°ΡΠΈΡ Π² ΡΡΡΠΎΠΊΠ°Ρ 1−4 ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O (V). ΠΠ°Π»Π΅Π΅ ΡΠΈΠΊΠ» Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ |V| ΡΠ°Π·, ΠΈ ΠΊΠ°ΠΆΠ΄Π°Ρ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ EXTRACT-MIN Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ Π²ΡΠ΅ΠΌΡ O (VlogV). Π¦ΠΈΠΊΠ» for Π² ΡΡΡΠΎΠΊΠ°Ρ 8−11 Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ Π² ΠΎΠ±ΡΠ΅ΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ O (E), ΠΏΠΎΡΠΊΠΎΠ»ΡΠΊΡ ΡΡΠΌΠΌΠ° ΡΡΠ΅ΠΏΠ΅Π½Π΅ΠΉ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° ΡΠ°Π²Π½Π° 2|E|. ΠΡΠΎΠ²Π΅ΡΠΊΡ ΠΏΡΠΈΠ½Π°Π΄Π»Π΅ΠΆΠ½ΠΎΡΡΠΈ Π² ΡΡΡΠΎΠΊΠ΅ 9 ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ Π·Π° Π²ΡΠ΅ΠΌΡ O (1), Π΅ΡΠ»ΠΈ Ρ ΡΠ°Π½ΠΈΡΡ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΎΡΠ΅ΡΠ΅Π΄ΠΈ Π΅ΡΠ΅ ΠΈ ΠΊΠ°ΠΊ Π±ΠΈΡΠΎΠ²ΡΠΉ Π²Π΅ΠΊΡΠΎΡ ΡΠ°Π·ΠΌΠ΅ΡΠ° |V|. ΠΡΠΈΡΠ²Π°ΠΈΠ²Π°Π½ΠΈΠ΅ Π² ΡΡΡΠΎΠΊΠ΅ 11 ΠΏΠΎΠ΄ΡΠ°Π·ΡΠΌΠ΅Π²Π°Π΅Ρ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΠΈ ΡΠΌΠ΅Π½ΡΡΠ΅Π½ΠΈΡ ΠΊΠ»ΡΡΠ° (DECREASE-KEY), ΠΊΠΎΡΠΎΡΠ°Ρ Π΄Π»Ρ Π΄Π²ΠΎΠΈΡΠ½ΠΎΠΉ ΠΊΡΡΠΈ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½Π° Π·Π° Π²ΡΠ΅ΠΌΡ O (logV). Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ Π²ΡΠ΅Π³ΠΎ ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌ O (VlogV+ElogV)=O (ElogV).
ΠΡΡΡΡΡ ΠΎΡΠ΅Π½ΠΊΡ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΠ»ΡΡΠΈΡΡ, Π΅ΡΠ»ΠΈ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ ΡΠΈΠ±ΠΎΠ½Π°ΡΡΠΈΠ΅Π²Ρ ΠΊΡΡΠΈ. Π‘ ΠΏΠΎΠΌΠΎΡΡΡ ΡΠΈΠ±ΠΎΠ½Π°ΡΡΠΈΠ΅Π²ΡΡ ΠΊΡΡ ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΠΏΠΎΠ»Π½ΠΈΡΡ ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ EXTRACT-MIN Π·Π° ΡΡΠ΅ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ O (logV), Π° ΠΎΠΏΠ΅ΡΠ°ΡΠΈΡ DECREASE-KEY — Π·Π° ΡΡΠ΅ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ O (1). Π ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΡΠΌΠΌΠ°ΡΠ½ΠΎΠ΅ Π²ΡΠ΅ΠΌΡ ΡΠ°Π±ΠΎΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΡΠΈΠΌΠ° ΡΠΎΡΡΠ°Π²ΠΈΡ O (E+VlogV).
4. Π‘ΠΎΡΡΠ°Π²Π»Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΎΡΡΠΎΠ²Π½ΠΎΠΉ Π΄Π΅ΡΠ΅Π²ΠΎ Π³ΡΠ°Ρ
ΠΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ (ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π, Π) Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ. Π‘Π½Π°ΡΠ°Π»Π° ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²ΠΎΠ΄ΠΈΡ ΠΏΠΎΡΡΠ΄ΠΎΠΊ Π³ΡΠ°ΡΠ°, ΡΡΠΎΠ±Ρ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΌΠΎΠ³Π»Π° ΡΡΠΎΡΠΌΠΈΡΠΎΠ²Π°ΡΡ ΡΠ°Π±Π»ΠΈΡΡ Π²Π²ΠΎΠ΄Π° Π΄Π°Π½Π½ΡΡ (ΠΌΠ°ΡΡΠΈΡΠ° Π²Π΅ΡΠΎΠ²) Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎΠΌ ΡΡΡΠΎΠΊ ΠΈ ΡΡΠΎΠ»Π±ΡΠΎΠ². ΠΡΠΈ ΡΡΠΎΠΌ Π²ΡΠ΅ ΠΊΠ½ΠΎΠΏΠΊΠΈ, ΠΊΡΠΎΠΌΠ΅ ΠΊΠ½ΠΎΠΏΠΊΠΈ «Π‘Π΄Π΅Π»Π°ΡΡ ΡΠ°Π±Π»ΠΈΡΡ» Π½Π΅Π΄ΠΎΡΡΡΠΏΠ½Ρ Π΄Π»Ρ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ. ΠΠ°ΡΠ΅ΠΌ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²ΠΎΠ΄ΠΈΡ Π² ΡΠ°Π±Π»ΠΈΡΡ Π΄Π°Π½Π½ΡΠ΅, ΠΏΡΠΈ ΡΡΠΎΠΌ ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ ΠΎΡΡΠ°Π²Π»ΡΡΡ ΠΏΡΡΡΡΠ΅ ΡΡΠ΅ΠΉΠΊΠΈ Π² ΡΠ°Π±Π»ΠΈΡΠ΅. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π±ΡΠ΄Π΅Ρ ΠΈΠ½ΡΠ΅ΡΠΏΡΠ΅ΡΠΈΡΠΎΠ²Π°ΡΡ ΡΡΠΎ ΠΊΠ°ΠΊ ΠΎΡΡΡΡΡΡΠ²ΠΈΠ΅ ΡΠ΅Π±ΡΠ° ΠΌΠ΅ΠΆΠ΄Ρ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ. ΠΠΎΠ³Π΄Π° Π΄Π°Π½Π½ΡΠ΅ Π±ΡΠ΄ΡΡ Π²Π²Π΅Π΄Π΅Π½Ρ, Π½ΡΠΆΠ½ΠΎ Π½Π°ΠΆΠ°ΡΡ Π½Π° ΠΊΠ½ΠΎΠΏΠΊΡ «Π Π°ΡΡΡΠΈΡΠ°ΡΡ Π΄Π΅ΡΠ΅Π²ΠΎ», ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΠΎΡΠ»Π΅ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΎΠΉ ΡΠ°Π±Π»ΠΈΡΡ ΡΡΠ°Π½Π΅Ρ Π°ΠΊΡΠΈΠ²Π½ΠΎΠΉ. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠ°ΡΡΡΠΈΡΠ°Π΅Ρ ΠΌΠ°ΡΡΠΈΡΡ Π²Π΅ΡΠΎΠ² Π΄Π»Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° ΠΈ Π½Π°ΡΠΈΡΡΠ΅Ρ ΠΈΡΠΊΠΎΠΌΡΠΉ Π³ΡΠ°Ρ (Π΄Π»ΠΈΠ½Ρ ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ° Π½Π΅ Π±ΡΠ΄ΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΠ΅ Π²Π΅ΡΠΎΠ²). ΠΡΠΈ ΡΡΠΎΠΌ ΡΠ°Π±Π»ΠΈΡΠ° Π²Π²ΠΎΠ΄Π° ΠΈ Π²ΡΠ΅ ΠΊΠ½ΠΎΠΏΠΊΠΈ, ΠΊΡΠΎΠΌΠ΅ ΠΊΠ½ΠΎΠΏΠΊΠΈ «ΠΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΡΡ», ΡΡΠ°Π½ΡΡ Π½Π΅Π΄ΠΎΡΡΡΠΏΠ½Ρ Π΄Π»Ρ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ. ΠΡΠΈ Π½Π°ΠΆΠ°ΡΠΈΠΈ Π½Π° ΡΡΡ Π΅Π΄ΠΈΠ½ΡΡΠ²Π΅Π½Π½ΡΡ Π°ΠΊΡΠΈΠ²Π½ΡΡ ΠΊΠ½ΠΎΠΏΠΊΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΏΠ΅ΡΠ΅ΠΉΠ΄Π΅Ρ Π² ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅.
Π’Π΅ΠΏΠ΅ΡΡ ΠΎ ΡΠΎΠΌ, ΠΊΠ°ΠΊ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠ΅Π°Π»ΠΈΠ·ΡΠ΅Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΠΈΠΌΠ°.
Π‘Π½Π°ΡΠ°Π»Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠΎΠ·Π΄Π°Π΅Ρ Π½Π΅ΠΊΠΈΠΉ ΠΌΠ°ΡΡΠΈΠ² a[10] (ΠΏΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ, ΡΡΠΎ ΡΠΈΡΠ»ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° ΠΌΠ΅Π½ΡΡΠ΅ ΠΈΠ»ΠΈ ΡΠ°Π²Π½ΠΎ 10). ΠΡΠΎΡ ΠΌΠ°ΡΡΠΈΠ² ΠΈΠ½ΠΈΡΠΈΠ°Π»ΠΈΠ·ΠΈΡΡΠ΅ΡΡΡ: ΠΊΠ°ΠΆΠ΄ΠΎΠΌΡ a[i] [j] ΠΏΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΡΡΡ 1000 (ΠΏΡΠ΅Π΄ΠΏΠΎΠ»Π°Π³Π°Π΅ΡΡΡ, ΡΡΠΎ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½Π°Ρ Π΄Π»ΠΈΠ½Π° ΡΠ΅Π±ΡΠ° ΠΌΠ΅Π½ΡΡΠ΅ 1000). ΠΠΎΡΠΎΠΌ Π΄Π°Π½Π½ΡΠ΅ ΠΈΠ· ΡΠ°Π±Π»ΠΈΡΡ Π²Π²ΠΎΠ΄Π° ΠΊΠΎΠΏΠΈΡΡΡΡΡΡ Π² ΠΌΠ°ΡΡΠΈΠ². ΠΡΠΈ ΡΡΠΎΠΌ Π΅ΡΠ»ΠΈ Π² ΡΡΠ΅ΠΉΠΊΠ΅ ΡΠ°Π±Π»ΠΈΡΡ Π½ΠΈΡΠ΅Π³ΠΎ Π½Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡΡΡ Π² ΠΌΠ°ΡΡΠΈΠ² Π½ΠΈΡΠ΅Π³ΠΎ Π½Π΅ ΠΊΠΎΠΏΠΈΡΡΠ΅ΡΡΡ. ΠΠ°ΡΠ΅ΠΌ Π΄Π΅Π»Π°Π΅ΡΡΡ ΡΠΈΠΊΠ», ΠΊΠΎΡΠΎΡΡΠΉ ΠΏΡΠ΅ΡΡΠ²Π°Π΅ΡΡΡ ΡΠΎΠ»ΡΠΊΠΎ ΡΠΎΠ³Π΄Π°, ΠΊΠΎΠ³Π΄Π° Π²ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π° ΡΡΠ°Π½ΡΡ ΡΠ½ΠΎΠ²Π° ΡΠ°Π²Π½Ρ 1000. ΠΠ°ΠΊ ΡΠ°Π±ΠΎΡΠ°Π΅Ρ ΡΠΈΠΊΠ»? Π‘Π½Π°ΡΠ°Π»Π° Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π° (ΠΈΠ· ΠΎΠ±Π»Π°ΡΡΠΈ Π²ΡΡΠ΅ Π³Π»Π°Π²Π½ΠΎΠΉ Π΄ΠΈΠ°Π³ΠΎΠ½Π°Π»ΠΈ ΠΌΠ°ΡΡΠΈΡΡ Π²Π²ΠΎΠ΄Π°). ΠΠ½ Π·Π°ΠΏΠΎΠΌΠΈΠ½Π°Π΅ΡΡΡ (ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ buf) ΠΈ Π΅ΠΌΡ ΠΏΡΠΈΡΠ²Π°ΠΈΠ²Π°Π΅ΡΡΡ 1000. Π‘ΠΎΠ³Π»Π°ΡΠ½ΠΎ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΡΠΈΠΌΠ°, Π΅ΡΠ»ΠΈ ΡΠ΅Π±ΡΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠ΅Π΅ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π²ΡΡΠ΅ΡΠΊΠΈΠ²Π°Π΅ΡΡΡ, Π° ΡΠΈΠΊΠ» Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ Ρ Π½Π°ΡΠ°Π»Π°. ΠΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠ΅Π΅ ΡΠ΅Π±ΡΠΎ ΠΈΠ»ΠΈ Π½Π΅Ρ? ΠΡΠ²Π΅Ρ Π½Π° ΡΡΠΎΡ Π²ΠΎΠΏΡΠΎΡ Π½Π°Ρ ΠΎΠ΄ΠΈΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ. Π‘ΠΎΠ·Π΄Π°Π΅ΡΡΡ ΠΌΠ°ΡΡΠΈΠ² Π² n ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ². ΠΠ°ΠΆΠ΄ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΡΠ°Π²Π΅Π½ 1 ΠΈΠ»ΠΈ 0. ΠΠΎΠ³Π΄Π° Π²Π΅ΡΡΠΈΠ½Π° Π²ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² Π΄Π΅ΡΠ΅Π²ΠΎ, Π² ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΠ²Π° Ρ Π΅Π΅ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ Π·Π°ΠΏΠΈΡΡΠ²Π°Π΅ΡΡΡ 1 (ΠΈΠ·Π½Π°ΡΠ°Π»ΡΠ½ΠΎ Π²ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ°ΡΡΠΈΠ²Π°, ΠΊΡΠΎΠΌΠ΅ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ ΡΠ°Π²Π½Ρ 0). Π§ΡΠΎΠ±Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠ΅Π΅ ΡΠ΅Π±ΡΠΎ ΠΈΠ»ΠΈ Π½Π΅Ρ, Π½ΡΠΆΠ½ΠΎ ΠΏΠΎΡΠΌΠΎΡΡΠ΅ΡΡ, Π½Π°Ρ ΠΎΠ΄ΡΡΡΡ Π»ΠΈ Π΅Π΄ΠΈΠ½ΠΈΡΡ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ (Π½ΠΎΠΌΠ΅ΡΠ° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΡΠ°Π²Π½Ρ Π½ΠΎΠΌΠ΅ΡΠ°ΠΌ Π²Π΅ΡΡΠΈΠ½ ΡΠ΅Π±ΡΠ°). ΠΡΠ»ΠΈ Π½ΠΎΠΌΠ΅ΡΠ°ΠΌ Π²Π΅ΡΡΠΈΠ½ ΡΠ΅Π±ΡΠ° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΠΎΠ±Π΅ Π΅Π΄ΠΈΠ½ΠΈΡΠ°, Π·Π½Π°ΡΠΈΡ, ΡΠ΅Π±ΡΠΎ Π½Π΅ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠ΅Π΅. ΠΡΠ»ΠΈ ΡΡΠΎ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ Π½Π΅ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ — ΡΠ΅Π±ΡΠΎ ΠΏΠΎΠ΄Ρ ΠΎΠ΄ΡΡΠ΅Π΅. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΡΠ΅ΠΊΡΠ°ΡΠ°Π΅Ρ ΡΠ°Π±ΠΎΡΡ, ΠΊΠΎΠ³Π΄Π° Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ Π²ΠΊΠ»ΡΡΠ΅Π½Ρ Π² Π½ΠΎΠ²ΡΠΉ Π³ΡΠ°Ρ.
ΠΡΠ΄Π΅Π»ΡΠ½ΠΎ ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΠ΄Π΅Π»ΠΈΡΡ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ ΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π³ΡΠ°ΡΠ°. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠΎΠ·Π΄Π°Π΅Ρ Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°Ρ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° (krug [10]). ΠΠ΅ΡΡΠΈΠ½Ρ ΡΠ°ΡΠΏΠΎΠ»Π°Π³Π°ΡΡΡΡ Π½Π° ΠΎΠΊΡΡΠΆΠ½ΠΎΡΡΠΈ Π½Π° ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠΌ ΡΠ°ΡΡΡΠΎΡΠ½ΠΈΠΈ Π΄ΡΡΠ³ ΠΎΡ Π΄ΡΡΠ³Π°. Π’Π°ΠΊΠΎΠΉ ΡΠΏΠΎΡΠΎΠ± ΠΎΡΠ΅Π½Ρ ΡΠ΄ΠΎΠ±Π½ΡΠΉ, ΠΏΠΎΡΠΎΠΌΡ ΡΡΠΎ Π½Π΅ Π½Π°Π΄ΠΎ Π±Π΅ΡΠΏΠΎΠΊΠΎΠΈΡΡΡΡ ΠΎ ΡΠΎΠΌ, ΡΡΠΎ ΡΠ΅Π±ΡΠ° Π±ΡΠ΄ΡΡ Π½Π°ΡΠ»Π°ΠΈΠ²Π°ΡΡΡΡ ΠΎΠ΄Π½ΠΎ Π½Π° Π΄ΡΡΠ³ΠΎΠ΅.
5. Π’Π΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
Π’Π΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΏΡΠΎΠ²ΠΎΠ΄ΠΈΠ»ΠΎΡΡ Π½Π° ΡΠ°ΠΌΡΡ ΡΠ°Π·Π½ΡΡ Π²Π°ΡΠΈΠ°Π½ΡΠ°Ρ ΠΌΠ°ΡΡΠΈΡΡ Π²Π΅ΡΠΎΠ². Π ΠΏΡΠΎΡΠ΅ΡΡΠ΅ ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΎΡΠΈΠ±ΠΎΠΊ Π½Π΅ ΠΎΠ±Π½Π°ΡΡΠΆΠ΅Π½ΠΎ.
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π»Π°ΡΡ Π½Π° ΡΠ»Π΅Π΄ΡΡΡΠΈΡ ΠΏΡΠΈΠΌΠ΅ΡΠ°Ρ :
ΠΠ°ΡΡΠΈΡΠ° Π²Π΅ΡΠΎΠ²
ΠΡΠ΄Π°Π½ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ
ΠΠ°ΡΡΠΈΡΠ° Π²Π΅ΡΠΎΠ²
ΠΡΠ΄Π°Π½ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ
ΠΠ°ΡΡΠΈΡΠ° Π²Π΅ΡΠΎΠ²
ΠΡΠ΄Π°Π½ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ
ΠΠ°ΡΡΠΈΡΠ° Π²Π΅ΡΠΎΠ²
ΠΡΠ΄Π°Π½ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ
ΠΠ°ΡΡΠΈΡΠ° Π²Π΅ΡΠΎΠ²
ΠΡΠ΄Π°Π½ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ
ΠΠ° ΡΠΈΡΡΠ½ΠΊΠ΅ 9 ΠΈΠ·ΠΎΠ±ΡΠ°ΠΆΠ΅Π½ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
Π ΠΈΡΡΠ½ΠΎΠΊ 9 — ΠΠΊΠ½ΠΎ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
Π Ρ ΠΎΠ΄Π΅ ΠΏΡΠΎΠ΄Π΅Π»Π°Π½Π½ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ Π±ΡΠ»Π° Π½Π°ΠΏΠΈΡΠ°Π½Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°, ΡΠ΅Π°Π»ΠΈΠ·ΡΡΡΠ°Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΡΠΈΠΌΠ°. Π ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π²ΡΠ΄Π°Π΅Ρ ΠΌΠ°ΡΡΠΈΡΡ Π²Π΅ΡΠΎΠ² ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° Π³ΡΠ°ΡΠ°, ΠΈ ΠΈΠ·ΠΎΠ±ΡΠ°ΠΆΠ°Π΅Ρ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΉ Π³ΡΠ°Ρ.
Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½Π½ΡΡ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠΎΠ²
1. http://works.tarefer.ru
2. http://www.intuit.ru
3. http://www.offzone.litehosting.ru
ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π
ΠΠΈΡΡΠΈΠ½Π³ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
// ;
#include
#pragma hdrstop
#include «Unit21.h»
// ;
#pragma package (smart_init)
#include «math.h»
#pragma resource «*.dfm»
TForm1 *Form1;
int n=3;
// ;
__fastcall TForm1: TForm1 (TComponent* Owner)
: TForm (Owner)
{
}
// ;
void __fastcall TForm1: Button1Click (TObject *Sender)
{
n=StrToInt (Edit1->Text);
StringGrid1->ColCount=n;
StringGrid1->RowCount=n;
StringGrid2->ColCount=n;
StringGrid2->RowCount=n;
StringGrid1->Visible=true;
BitBtn1->Enabled=true;
Button1->Enabled=false;
}
// ;
void __fastcall TForm1: BitBtn1Click (TObject *Sender)
{
BitBtn2->Enabled=true;
BitBtn1->Enabled=false;
Button1->Enabled=false;
StringGrid2->Visible=true;
int a[10] [10];
int mas[3] [10];
int kmas=0;
int versh[10];
for (int i=0; i
versh[i]=0;
versh[1]=1;
for (int i=0; i
for (int j=0; j
a[i] [j]=1000;
// *******
for (int i=0; i
for (int j=0; j
if (StringGrid1->Cells[i] [j]≠"") a[i] [j]=StrToInt (StringGrid1->Cells[i] [j]);
// **********
int k=n-1;
while (k≠0)
{
int buf=1000;
int x, y;
for (int i=1; i
for (int j=0; j
{
if ((a[i] [j]
{buf=a[i] [j]; x=i; y=j;}
}
if (versh[x]==1) versh[y]=1; else versh[x]=1;
a[x] [y]=1000;
mas[0] [kmas]=x;
mas[1] [kmas]=y;
mas[2] [kmas]=buf;
kmas++;
// *****
k -;
}
/// ***********************
for (int i=0; i
StringGrid2->Cells [mas[0] [i]] [mas[1] [i]]=IntToStr (mas[2] [i]);
// **********
// ΡΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅
int krug[2] [10];
Form1->Canvas->Pen->Color=clBlack;
for (int i=0; i
{
krug[0] [i]=400+100*sin (6.28*i/n);
krug[1] [i]=400+100*cos (6.28*i/n);
}
for (int i=0; i
{
Form1->Canvas->MoveTo (krug[0] [mas[0] [i]], krug[1] [mas[0] [i]]);
Form1->Canvas->LineTo (krug[0] [mas[1] [i]], krug[1] [mas[1] [i]]);
}
}
// ;
void __fastcall TForm1: BitBtn2Click (TObject *Sender)
{
Button1->Enabled=true;
StringGrid1->Visible=false;
StringGrid2->Visible=false;
BitBtn2->Enabled=false;
Form1->Canvas->Pen->Color=clBtnFace;
Form1->Canvas->Rectangle (295, 295,505, 505);
}
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠ΅ΡΡΠΈΡΠΎΠ²Π°Π»Π°ΡΡ Π½Π° ΡΠ»Π΅Π΄ΡΡΡΠΈΡ ΠΏΡΠΈΠΌΠ΅ΡΠ°Ρ :
ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π
ΠΠ½ΡΡΡΡΠΊΡΠΈΡ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ ΠΠ³ΡΠ°Π½ΠΈΡΠ΅Π½ΠΈΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ:
— ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° Π½Π΅ Π±ΠΎΠ»Π΅Π΅ 10;
— Π΄Π»ΠΈΠ½Π° ΡΠ΅Π±ΡΠ° — ΡΠ΅Π»ΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ, ΠΌΠ΅Π½ΡΡΠ΅ 1000.
ΠΠΎΡΡΠ΄ΠΎΠΊ ΡΠ°Π±ΠΎΡΡ:
1) ΠΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Π²Π²ΠΎΠ΄ΠΈΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°
2) ΠΠ°ΠΆΠΈΠΌΠ°Π΅ΡΡΡ ΠΊΠ½ΠΎΠΏΠΊΠ° «Π‘Π΄Π΅Π»Π°ΡΡ ΡΠ°Π±Π»ΠΈΡΡ»
3) ΠΠ²ΠΎΠ΄ΡΡΡΡ Π΄Π°Π½Π½ΡΠ΅ Π² ΡΠ°Π±Π»ΠΈΡΡ
4) ΠΠ°ΠΆΠΈΠΌΠ°Π΅ΡΡΡ ΠΊΠ½ΠΎΠΏΠΊΠ° «Π Π°ΡΡΡΠΈΡΠ°ΡΡ Π΄Π΅ΡΠ΅Π²ΠΎ»
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠΎΡΡΠ°Π²Π»ΡΠ΅Ρ ΠΌΠ°ΡΡΠΈΡΡ Π²Π΅ΡΠΎΠ² Π΄Π»Ρ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΡΠΎΠ²Π½ΠΎΠ³ΠΎ Π΄Π΅ΡΠ΅Π²Π° ΠΈ ΠΈΠ·ΠΎΠ±ΡΠ°ΠΆΠ°Π΅Ρ ΠΈΡΠΊΠΎΠΌΡΠΉ Π³ΡΠ°Ρ.
5) ΠΡΠ»ΠΈ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Ρ ΠΎΡΠ΅Ρ ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΡΡ ΡΠ°Π±ΠΎΡΡ Ρ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΎΠΉ, ΠΎΠ½ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π½Π°ΠΆΠ°ΡΡ Π½Π° ΠΊΠ½ΠΎΠΏΠΊΡ «ΠΡΠΎΠ΄ΠΎΠ»ΠΆΠΈΡΡ»
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π²Π΅ΡΠ½Π΅ΡΡΡ Π² ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅