Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΡ ΡΠΈΠΊΠ»ΠΎΠ² Π³ΡΠ°ΡΠ° ΡΡΠ΅Π΄ΡΡΠ²Π°ΠΌΠΈ ΡΠ·ΡΠΊΠ° Π‘++
ΠΠ°Π·Π²Π°Π½Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΌΠΎΠ³ΡΡ Π½Π°ΠΉΡΠΈ ΡΠ²ΠΎΠΈ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°Ρ Π΄Π»Ρ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΡΡ ΠΈ ΠΊΠΎΠΌΠΌΡΠ½ΠΈΠΊΠ°ΡΠΈΠΎΠ½Π½ΡΡ ΡΠ΅ΡΠ΅ΠΉ, ΡΠ°ΠΊΠΈΡ ΠΊΠ°ΠΊ: ΠΆΠ΅Π»Π΅Π·Π½ΠΎΠ΄ΠΎΡΠΎΠΆΠ½ΠΎΠΉ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ ΡΠ΅ΡΠΈ, Π³Π΄Π΅ Π²Π΅ΡΡΠΈΠ½Ρ — ΡΡΠ°Π½ΡΠΈΠΈ, ΡΠ²ΡΠ·ΠΈ — Π΄ΠΎΡΠΎΠ³ΠΈ, ΡΠ°ΠΊΡΠΎΠΌΠΎΡΠΎΡΠ½Π°Ρ ΡΠ΅ΡΡ: Π²Π΅ΡΡΠΈΠ½Ρ — ΠΌΠ΅ΡΡΠ° ΡΡΠΎΡΠ½ΠΊΠΈ Π°Π²ΡΠΎΠΌΠΎΠ±ΠΈΠ»Π΅ΠΉ, ΡΠ²ΡΠ·ΠΈ — ΠΏΡΡΠΈ ΠΏΠΎΠ΄ΡΠ΅Π·Π΄Π°; ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΏΠΎΡΠΎΠΊΠ° Π²Π΅ΡΠ΅ΡΡΠ²Π° ΠΏΠΎ ΡΠΈΡΡΠ΅ΠΌΠ΅ ΡΡΡΠ± Π² ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ ΠΏΡΠ½ΠΊΡ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΈ Ρ. Π΄. ΠΠ° ΠΎΡΠ½ΠΎΠ²Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΏΠΎΠΈΡΠΊΠ° Π² ΡΠΈΡΠΈΠ½Ρ Π² Π³ΡΠ°ΡΠ΅… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
Π Π΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΡ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ² ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΡ ΡΠΈΠΊΠ»ΠΎΠ² Π³ΡΠ°ΡΠ° ΡΡΠ΅Π΄ΡΡΠ²Π°ΠΌΠΈ ΡΠ·ΡΠΊΠ° Π‘++ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
Π‘ΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅ ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ ΠΠ΅ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠ²Π΅Π΄Π΅Π½ΠΈΡ ΠΈΠ· ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π‘ΠΏΠΎΡΠΎΠ±Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π³ΡΠ°ΡΠ° Π² ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΊΠ΅ ΠΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΡ ΡΠΈΠΊΠ»ΠΎΠ² Π³ΡΠ°ΡΠ° Π ΡΡΠ΅Π΄Π΅ wxDev-C++
Π Π°Π·ΡΠ°Π±ΠΎΡΠΊΠ° Π² wxDev-C++
Π ΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²ΠΎ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠΉ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΡ ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π
ΠΠ²Π΅Π΄Π΅Π½ΠΈΠ΅
Π Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½Π°Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ° ΠΈ ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π½Π΅ΠΉ ΡΠ°Π·Π΄Π΅Π»Ρ ΠΏΡΠΈΠ²Π»Π΅ΠΊΠ°ΡΡ Π±ΠΎΠ»ΡΡΠΎΠ΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ ΡΠΏΠ΅ΡΠΈΠ°Π»ΠΈΡΡΠΎΠ² ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ ΠΎΠ±Π»Π°ΡΡΠ΅ΠΉ Π½Π°ΡΠΊΠΈ ΠΈ ΡΠ΅Ρ Π½ΠΈΠΊΠΈ, ΡΠ²Π»ΡΡΡΡ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΡΠΌ Π°ΠΏΠΏΠ°ΡΠ°ΡΠΎΠΌ ΡΠΎΡΠΌΠ°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΠΈΠ½ΠΆΠ΅Π½Π΅ΡΠ½ΡΡ Π·Π°Π΄Π°Ρ, ΡΠ²ΡΠ·Π°Π½Π½ΡΡ Ρ Π΄ΠΈΡΠΊΡΠ΅ΡΠ½ΡΠΌΠΈ ΠΎΠ±ΡΠ΅ΠΊΡΠ°ΠΌΠΈ. ΠΡΠΎΠ±ΠΎΠ΅ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Ρ ΠΏΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΎΡΠΊΠΈ Π·ΡΠ΅Π½ΠΈΡ ΠΈΠΌΠ΅Π΅Ρ ΡΠ΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ², ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΠ°ΡΡΡ ΠΏΡΠΈ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΈΠ½ΡΠ΅Π³ΡΠ°Π»ΡΠ½ΡΡ ΡΡ Π΅ΠΌ ΠΈ ΡΡ Π΅ΠΌ ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ, ΠΈΡΡΠ»Π΅Π΄ΠΎΠ²Π°Π½ΠΈΠΈ Π°Π²ΡΠΎΠΌΠ°ΡΠΎΠ² ΠΈ Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΈΡ ΡΠ΅ΠΏΠ΅ΠΉ, ΠΏΡΠΈ ΡΠΈΡΡΠ΅ΠΌΠ½ΠΎΠΌ Π°Π½Π°Π»ΠΈΠ·Π΅, Π°Π²ΡΠΎΠΌΠ°ΡΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΌ ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΠΈ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΡΡΠ²ΠΎΠΌ, ΠΏΡΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠ΅ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΡ ΠΈ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΎΠ½Π½ΡΡ ΡΠ΅ΡΠ΅ΠΉ, Π² ΡΡ Π΅ΠΌΠΎΡΠ΅Ρ Π½ΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΈ ΠΊΠΎΠ½ΡΡΡΡΠΊΡΠΎΡΡΠΊΠΎ-ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ, ΠΈ Ρ. Π΄. ΠΠ±ΡΠΈΡΠ½ΠΎΠ΅ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΠ΅ ΡΠ΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ² Π½Π°Ρ ΠΎΠ΄ΠΈΡ Π² ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ΅Ρ Π½ΠΈΠΊΠ΅ ΠΈ ΠΊΠΈΠ±Π΅ΡΠ½Π΅ΡΠΈΠΊΠ΅: Π² ΡΠ΅ΠΎΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠΎΠΌ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ, ΠΏΡΠΈ ΠΏΡΠΎΠ΅ΠΊΡΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ ΠΠΠ, Π±Π°Π· Π΄Π°Π½Π½ΡΡ , ΡΠΈΡΡΠ΅ΠΌ Π»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΡΠ°Π²Π»Π΅Π½ΠΈΡ. ΠΠΎΡΡΠΎΠΌΡ ΠΎΡΠ½ΠΎΠ²Π½ΠΎΠ΅ Π²Π½ΠΈΠΌΠ°Π½ΠΈΠ΅ Π² ΠΊΡΡΡΠΎΠ²ΠΎΠΉ ΡΠ°Π±ΠΎΡΠ΅ ΡΠ΄Π΅Π»ΡΠ΅ΡΡΡ ΠΈΠ·Π»ΠΎΠΆΠ΅Π½ΠΈΡ ΠΎΡΠ½ΠΎΠ² ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² ΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² ΠΏΠΎΠΈΡΠΊΠ° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΡ ΡΠΈΠΊΠ»ΠΎΠ² Π² Π³Π»ΡΠ±ΠΈΠ½Ρ Π² Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π³ΡΠ°ΡΠ°Ρ .
ΠΠ΅ΠΊΠΎΡΠΎΡΡΠ΅ ΡΠ²Π΅Π΄Π΅Π½ΠΈΡ ΠΈΠ· ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² Π ΡΠ΅ΠΎΡΠΈΠΈ Π³ΡΠ°ΡΠΎΠ² ΠΎΠ±ΡΠ΅ΠΊΡΡ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΡΡΡΡ ΠΊΠ°ΠΊ Π²Π΅ΡΡΠΈΠ½ΡΠ³ΡΠ°ΡΠ°, Π° ΡΠ²ΡΠ·ΠΈ — ΠΊΠ°ΠΊ Π΄ΡΠ³ΠΈ, ΠΈΠ»ΠΈ ΡΡΠ±ΡΠ°. ΠΡΠ°Ρ ΠΈΠ»ΠΈ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°ΡG (ΡΠΈΡ.1) — ΡΡΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½Π°Ρ ΠΏΠ°ΡΠ°G: = (V, E), Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠΉ Π²ΡΠΏΠΎΠ»Π½Π΅Π½Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΡ: V ΡΡΠΎ Π½Π΅ΠΏΡΡΡΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, E ΡΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΠΏΠ°Ρ (Π² ΡΠ»ΡΡΠ°Π΅ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° — Π½Π΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ ) Π²Π΅ΡΡΠΈΠ½, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΡ ΡΡΠ±ΡΠ°ΠΌΠΈ.
Π ΠΈΡΡΠ½ΠΎΠΊ 1 ΠΠ΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ ΠΠ΅ΡΡΠΈΠ½Ρ ΠΈ ΡΡΠ±ΡΠ° Π³ΡΠ°ΡΠ° Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠ°ΠΊΠΆΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌΠΈ Π³ΡΠ°ΡΠ°, ΡΠΈΡΠ»ΠΎ Π²Π΅ΡΡΠΈΠ½ Π² Π³ΡΠ°ΡΠ΅ | V | — ΠΏΠΎΡΡΠ΄ΠΊΠΎΠΌ, ΡΠΈΡΠ»ΠΎ ΡΡΠ±Π΅Ρ | E | — ΡΠ°Π·ΠΌΠ΅ΡΠΎΠΌ Π³ΡΠ°ΡΠ°.
ΠΠ΅ΡΡΠΈΠ½Ρ u ΠΈ v Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΠΊΠΎΠ½ΡΠ΅Π²ΡΠΌΠΈ Π²Π΅ΡΡΠΈΠ½Π°ΠΌΠΈ (ΠΈΠ»ΠΈ ΠΏΡΠΎΡΡΠΎ ΠΊΠΎΠ½ΡΠ°ΠΌΠΈ) ΡΠ΅Π±ΡΠ° e = {u, v}. Π Π΅Π±ΡΠΎ, Π² ΡΠ²ΠΎΡ ΠΎΡΠ΅ΡΠ΅Π΄Ρ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΠ΅Ρ ΡΡΠΈ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΠ²Π΅ ΠΊΠΎΠ½ΡΠ΅Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈ ΡΠΎΠ³ΠΎ ΠΆΠ΅ ΡΠ΅Π±ΡΠ° Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠΎΡΠ΅Π΄Π½ΠΈΠΌΠΈ.
ΠΠ²Π° ΡΠ΅Π±ΡΠ° Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠΌΠ΅ΠΆΠ½ΡΠΌΠΈ, Π΅ΡΠ»ΠΈ ΠΎΠ½ΠΈ ΠΈΠΌΠ΅ΡΡ ΠΎΠ±ΡΡΡ ΠΊΠΎΠ½ΡΠ΅Π²ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ.
ΠΠ²Π° ΡΠ΅Π±ΡΠ° Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΠΊΡΠ°ΡΠ½ΡΠΌΠΈ, Π΅ΡΠ»ΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΠΈΡ ΠΊΠΎΠ½ΡΠ΅Π²ΡΡ Π²Π΅ΡΡΠΈΠ½ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡΡ.
Π Π΅Π±ΡΠΎ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠ΅ΡΠ»ΡΠΉ, Π΅ΡΠ»ΠΈ Π΅Π³ΠΎ ΠΊΠΎΠ½ΡΡ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡΡ, ΡΠΎ Π΅ΡΡΡ e = {v, v}.
ΠΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ (ΡΠΎΠΊΡΠ°ΡΡΠ½Π½ΠΎ ΠΎΡΠ³ΡΠ°Ρ) G (ΡΠΈΡ.2) — ΡΡΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½Π°Ρ ΠΏΠ°ΡΠ°G: = (V, A), Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠΉ Π²ΡΠΏΠΎΠ»Π½Π΅Π½Ρ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΡΡΠ»ΠΎΠ²ΠΈΡ: V ΡΡΠΎ Π½Π΅ΠΏΡΡΡΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ ΠΈΠ»ΠΈ ΡΠ·Π»ΠΎΠ², A ΡΡΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ (ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ ) ΠΏΠ°Ρ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½, Π½Π°Π·ΡΠ²Π°Π΅ΠΌΡΡ Π΄ΡΠ³Π°ΠΌΠΈ ΠΈΠ»ΠΈ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ ΡΡΠ±ΡΠ°ΠΌΠΈ.
Π ΠΈΡΡΠ½ΠΎΠΊ 2 ΠΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ ΠΡΠ³Π° — ΡΡΠΎ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½Π°Ρ ΠΏΠ°ΡΠ° Π²Π΅ΡΡΠΈΠ½ (v, w), Π³Π΄Π΅ Π²Π΅ΡΡΠΈΠ½Ρ v Π½Π°Π·ΡΠ²Π°ΡΡ Π½Π°ΡΠ°Π»ΠΎΠΌ, Π° w — ΠΊΠΎΠ½ΡΠΎΠΌ Π΄ΡΠ³ΠΈ. ΠΠΎΠΆΠ½ΠΎ ΡΠΊΠ°Π·Π°ΡΡ, ΡΡΠΎ Π΄ΡΠ³Π° Π²Π΅Π΄ΡΡ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ v ΠΊ Π²Π΅ΡΡΠΈΠ½Π΅ w.
ΠΡΡΡΠΌ (ΠΈΠ»ΠΈ ΡΠ΅ΠΏΡΡ) Π² Π³ΡΠ°ΡΠ΅ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΊΠΎΠ½Π΅ΡΠ½ΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½, Π² ΠΊΠΎΡΠΎΡΠΎΠΉ ΠΊΠ°ΠΆΠ΄Π°Ρ Π²Π΅ΡΡΠΈΠ½Π° (ΠΊΡΠΎΠΌΠ΅ ΠΏΠΎΡΠ»Π΅Π΄Π½Π΅ΠΉ) ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π° ΡΠΎ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΉ Π² ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ Π²Π΅ΡΡΠΈΠ½ ΡΠ΅Π±ΡΠΎΠΌ.
ΠΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌ ΠΏΡΡΡΠΌ Π² ΠΎΡΠ³ΡΠ°ΡΠ΅ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΊΠΎΠ½Π΅ΡΠ½ΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½ vi, Π΄Π»Ρ ΠΊΠΎΡΠΎΡΠΎΠΉ Π²ΡΠ΅ ΠΏΠ°ΡΡ (vi, vi + 1) ΡΠ²Π»ΡΡΡΡΡ (ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ) ΡΡΠ±ΡΠ°ΠΌΠΈ.
Π¦ΠΈΠΊΠ»ΠΎΠΌ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΏΡΡΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ ΠΏΠ΅ΡΠ²Π°Ρ ΠΈ ΠΏΠΎΡΠ»Π΅Π΄Π½ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ ΡΠΎΠ²ΠΏΠ°Π΄Π°ΡΡ. ΠΡΠΈ ΡΡΠΎΠΌ Π΄Π»ΠΈΠ½ΠΎΠΉ ΠΏΡΡΠΈ (ΠΈΠ»ΠΈ ΡΠΈΠΊΠ»Π°) Π½Π°Π·ΡΠ²Π°ΡΡ ΡΠΈΡΠ»ΠΎ ΡΠΎΡΡΠ°Π²Π»ΡΡΡΠΈΡ Π΅Π³ΠΎ ΡΡΠ±Π΅Ρ. ΠΠ°ΠΌΠ΅ΡΠΈΠΌ, ΡΡΠΎ Π΅ΡΠ»ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ u ΠΈ v ΡΠ²Π»ΡΡΡΡΡ ΠΊΠΎΠ½ΡΠ°ΠΌΠΈ Π½Π΅ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ°, ΡΠΎ ΡΠΎΠ³Π»Π°ΡΠ½ΠΎ Π΄Π°Π½Π½ΠΎΠΌΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ, ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ (u, v, u) ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠΈΠΊΠ»ΠΎΠΌ. Π§ΡΠΎΠ±Ρ ΠΈΠ·Π±Π΅ΠΆΠ°ΡΡ ΡΠ°ΠΊΠΈΡ «Π²ΡΡΠΎΠΆΠ΄Π΅Π½Π½ΡΡ » ΡΠ»ΡΡΠ°Π΅Π², Π²Π²ΠΎΠ΄ΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΠΏΠΎΠ½ΡΡΠΈΡ.
ΠΡΡΡ (ΠΈΠ»ΠΈ ΡΠΈΠΊΠ») Π½Π°Π·ΡΠ²Π°ΡΡ ΠΏΡΠΎΡΡΡΠΌ, Π΅ΡΠ»ΠΈ ΡΠ΅Π±ΡΠ° Π² Π½ΡΠΌ Π½Π΅ ΠΏΠΎΠ²ΡΠΎΡΡΡΡΡΡ; ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΠΌ, Π΅ΡΠ»ΠΈ ΠΎΠ½ ΠΏΡΠΎΡΡΠΎΠΉ ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ Π² Π½ΡΠΌ Π½Π΅ ΠΏΠΎΠ²ΡΠΎΡΡΡΡΡΡ. ΠΠ΅ΡΠ»ΠΎΠΆΠ½ΠΎ Π²ΠΈΠ΄Π΅ΡΡ, ΡΡΠΎ, Π²ΡΡΠΊΠΈΠΉ ΠΏΡΡΡ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠΈΠΉ Π΄Π²Π΅ Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΠΉ ΠΏΡΡΡ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠΈΠΉ ΡΠ΅ ΠΆΠ΅ Π΄Π²Π΅ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΡΡΠΊΠΈΠΉ ΠΏΡΠΎΡΡΠΎΠΉ Π½Π΅ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΠΉ ΠΏΡΡΡ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΠΉ ΡΠΈΠΊΠ». ΠΡΡΠΊΠΈΠΉ ΠΏΡΠΎΡΡΠΎΠΉ ΡΠΈΠΊΠ», ΠΏΡΠΎΡ ΠΎΠ΄ΡΡΠΈΠΉ ΡΠ΅ΡΠ΅Π· Π½Π΅ΠΊΠΎΡΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ (ΠΈΠ»ΠΈ ΡΠ΅Π±ΡΠΎ), ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΠΉ (ΠΏΠΎΠ΄-)ΡΠΈΠΊΠ», ΠΏΡΠΎΡ ΠΎΠ΄ΡΡΠΈΠΉ ΡΠ΅ΡΠ΅Π· ΡΡ ΠΆΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ (ΠΈΠ»ΠΈ ΡΠ΅Π±ΡΠΎ). ΠΠ΅ΡΠ»Ρ — ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΠΉ ΡΠΈΠΊΠ».
ΠΡΠ°Ρ Ρ ΠΏΠ΅ΡΠ»ΡΠΌΠΈ ΠΈ ΠΊΡΠ°ΡΠ½ΡΠΌΠΈ ΡΠ΅Π±ΡΠ°ΠΌΠΈ (Π΄ΡΠ³Π°ΠΌΠΈ) Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΠ΅Π²Π΄ΠΎΠ³ΡΠ°ΡΠΎΠΌ. ΠΡΠ°Ρ Ρ ΠΊΡΠ°ΡΠ½ΡΠΌΠΈ ΡΠ΅Π±ΡΠ°ΠΌΠΈ (Π΄ΡΠ³Π°ΠΌΠΈ) ΠΈ Π±Π΅Π· ΠΏΠ΅ΡΠ΅Π»Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΌΡΠ»ΡΡΠΈΠ³ΡΠ°ΡΠΎΠΌ.
ΠΡΠ°Ρ, Π½Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ ΠΏΠ΅ΡΠ΅Π»Ρ ΠΈ ΠΊΡΠ°ΡΠ½ΡΡ ΡΠ΅Π±Π΅Ρ, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΠΎΡΡΡΠΌ Π³ΡΠ°ΡΠΎΠΌ.
ΠΠ²Π΅ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° xi ΠΈ Ρ j Π½Π°Π·ΡΠ²Π°ΡΡΡΡ ΡΠΌΠ΅ΠΆΠ½ΡΠΌΠΈ, Π΅ΡΠ»ΠΈ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠ΅Π΅ ΠΈΡ ΡΠ΅Π±ΡΠΎ (Π΄ΡΠ³Π°). ΠΠ²Π° ΡΠ΅Π±ΡΠ° (Π΄ΡΠ³ΠΈ) ΡΠΌΠ΅ΠΆΠ½Ρ, Π΅ΡΠ»ΠΈ ΠΎΠ½ΠΈ ΠΈΠΌΠ΅ΡΡ ΠΎΠ±ΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΡΠΌ, Π΅ΡΠ»ΠΈ Π½ΠΈΠΊΠ°ΠΊΠΈΠ΅ Π΄Π²Π΅ Π²Π΅ΡΡΠΈΠ½Ρ ΡΡΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π½Π΅ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Ρ ΡΠ΅Π±ΡΠΎΠΌ. ΠΡΡΠ³ΠΈΠΌΠΈ ΡΠ»ΠΎΠ²Π°ΠΌΠΈ, ΠΈΠ½Π΄ΡΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΉ ΡΡΠΈΠΌ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎΠΌ ΠΏΠΎΠ΄Π³ΡΠ°Ρ ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· ΠΈΠ·ΠΎΠ»ΠΈΡΠΎΠ²Π°Π½Π½ΡΡ Π²Π΅ΡΡΠΈΠ½. ΠΠ½ΠΎΠ³Π΄Π° ΡΠ°ΠΊΠΆΠ΅ Π³ΠΎΠ²ΠΎΡΡΡ, ΡΡΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ Π³ΡΠ°ΡΠ° ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΠΎ Π½Π΅ Π±ΠΎΠ»Π΅Π΅ ΡΠ΅ΠΌ ΠΎΠ΄Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Π΅ ΠΈΠ· Π½Π΅Π·Π°Π²ΠΈΡΠΈΠΌΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π°.
Π‘ΠΏΠΎΡΠΎΠ±Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π³ΡΠ°ΡΠ° Π² ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΊΠ΅ ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ. Π’Π°Π±Π»ΠΈΡΠ°, Π³Π΄Π΅ ΠΊΠ°ΠΊ ΡΡΠΎΠ»Π±ΡΡ, ΡΠ°ΠΊ ΠΈ ΡΡΡΠΎΠΊΠΈ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ Π²Π΅ΡΡΠΈΠ½Π°ΠΌ Π³ΡΠ°ΡΠ°. Π ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΠ΅ΠΉΠΊΠ΅ ΡΡΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ Π·Π°ΠΏΠΈΡΡΠ²Π°Π΅ΡΡΡ ΡΠΈΡΠ»ΠΎ, ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΡΡΠ΅Π΅ Π½Π°Π»ΠΈΡΠΈΠ΅ ΡΠ²ΡΠ·ΠΈ ΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ-ΡΡΡΠΎΠΊΠΈ ΠΊ Π²Π΅ΡΡΠΈΠ½Π΅-ΡΡΠΎΠ»Π±ΡΡ (Π»ΠΈΠ±ΠΎ Π½Π°ΠΎΠ±ΠΎΡΠΎΡ).
ΠΠ΅Π΄ΠΎΡΡΠ°ΡΠΊΠΎΠΌ ΡΠ²Π»ΡΡΡΡΡ ΡΡΠ΅Π±ΠΎΠ²Π°Π½ΠΈΡ ΠΊ ΠΏΠ°ΠΌΡΡΠΈ, ΠΏΡΡΠΌΠΎ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»ΡΠ½ΡΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° Π²Π΅ΡΡΠΈΠ½, Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ²; ΠΌΠ°ΡΡΠΈΡΠ° Ρ ΠΏΡΠΎΠΏΡΡΠΊΠ°ΠΌΠΈ; Π½Π΅ΡΠ²Π½ΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅ (ΠΏΡΠΈ ΠΏΠΎΠΌΠΎΡΠΈ ΡΡΠ½ΠΊΡΠΈΠΈ).
ΠΠ°ΡΡΠΈΡΠ° ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΠΎΡΡΠΈ. ΠΠ°ΠΆΠ΄Π°Ρ ΡΡΡΠΎΠΊΠ° ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΠ΅Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Π΅ Π³ΡΠ°ΡΠ°, Π° ΡΡΠΎΠ»Π±ΡΡ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡ ΡΠ²ΡΠ·ΡΠΌ Π³ΡΠ°ΡΠ°. Π ΡΡΠ΅ΠΉΠΊΡ Π½Π° ΠΏΠ΅ΡΠ΅ΡΠ΅ΡΠ΅Π½ΠΈΠΈ i-ΠΎΠΉ ΡΡΡΠΎΠΊΠΈ Ρ j-ΠΌ ΡΡΠΎΠ»Π±ΡΠΎΠΌ ΠΌΠ°ΡΡΠΈΡΡ Π·Π°ΠΏΠΈΡΡΠ²Π°Π΅ΡΡΡ: 1 Π ΡΠ»ΡΡΠ°Π΅, Π΅ΡΠ»ΠΈ ΡΠ²ΡΠ·Ρ j «Π²ΡΡ ΠΎΠ΄ΠΈΡ» ΠΈΠ· Π²Π΅ΡΡΠΈΠ½Ρ i,?1,Π΅ΡΠ»ΠΈ ΡΠ²ΡΠ·Ρ «Π²Ρ ΠΎΠ΄ΠΈΡ» Π² Π²Π΅ΡΡΠΈΠ½Ρ, 0 Π²ΠΎ Π²ΡΠ΅Ρ ΠΎΡΡΠ°Π»ΡΠ½ΡΡ ΡΠ»ΡΡΠ°ΡΡ (ΡΠΎ Π΅ΡΡΡ Π΅ΡΠ»ΠΈ ΡΠ²ΡΠ·Ρ ΡΠ²Π»ΡΠ΅ΡΡΡ ΠΏΠ΅ΡΠ»ΡΠΉ ΠΈΠ»ΠΈ ΡΠ²ΡΠ·Ρ Π½Π΅ ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½Π° Π²Π΅ΡΡΠΈΠ½Π΅) ΠΠ°Π½Π½ΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°ΠΌΡΠΌ ΡΠΌΠΊΠΈΠΌ (ΡΠ°Π·ΠΌΠ΅Ρ ΠΏΡΠΎΠΏΠΎΡΡΠΈΠΎΠ½Π°Π»Π΅Π½ | E | | V |) Π΄Π»Ρ Ρ ΡΠ°Π½Π΅Π½ΠΈΡ, Π½ΠΎ ΠΎΠ±Π»Π΅Π³ΡΠ°Π΅Ρ Π½Π°Ρ ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ ΡΠΈΠΊΠ»ΠΎΠ² Π² Π³ΡΠ°ΡΠ΅.
Π‘ΠΏΠΈΡΠΎΠΊ ΡΡΠ±Π΅Ρ — ΡΡΠΎ ΡΠΈΠΏ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½ΠΈΡ Π³ΡΠ°ΡΠ° Π² ΠΏΠ°ΠΌΡΡΠΈ ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ½ΠΎΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ, ΠΏΠΎΠ΄ΡΠ°Π·ΡΠΌΠ΅Π²Π°ΡΡΠΈΠΉ, ΡΡΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠ΅ ΡΠ΅Π±ΡΠΎ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»ΡΠ΅ΡΡΡ Π΄Π²ΡΠΌΡ ΡΠΈΡΠ»Π°ΠΌΠΈ — Π½ΠΎΠΌΠ΅ΡΠ°ΠΌΠΈ Π²Π΅ΡΡΠΈΠ½ ΡΡΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ°. Π‘ΠΏΠΈΡΠΎΠΊ ΡΡΠ±Π΅Ρ Π±ΠΎΠ»Π΅Π΅ ΡΠ΄ΠΎΠ±Π΅Π½ Π΄Π»Ρ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΠΈ ΡΠ°Π·Π»ΠΈΡΠ½ΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ² Π½Π° Π³ΡΠ°ΡΠ°Ρ ΠΏΠΎ ΡΡΠ°Π²Π½Π΅Π½ΠΈΡ Ρ ΠΌΠ°ΡΡΠΈΡΠ΅ΠΉ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ.
ΠΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΡ ΡΠΈΠΊΠ»ΠΎΠ² Π³ΡΠ°ΡΠ° ΠΠΎΠΈΡΠΊ Π² Π³Π»ΡΠ±ΠΈΠ½Ρ (Π°Π½Π³Π». Depth-firstsearch, DFS) — ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΌΠ΅ΡΠΎΠ΄ΠΎΠ² ΠΎΠ±Ρ ΠΎΠ΄Π° Π³ΡΠ°ΡΠ°. ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° ΠΎΠΏΠΈΡΡΠ²Π°Π΅ΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ: Π΄Π»Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π½Π΅ΠΏΡΠΎΠΉΠ΄Π΅Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π½Π°ΠΉΡΠΈ Π²ΡΠ΅ Π½Π΅ ΠΏΡΠΎΠΉΠ΄Π΅Π½Π½ΡΠ΅ ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ ΠΈ ΠΏΠΎΠ²ΡΠΎΡΠΈΡΡ ΠΏΠΎΠΈΡΠΊ Π΄Π»Ρ Π½ΠΈΡ . ΠΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΠΎΠ΄ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π² Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°Ρ ΠΏΠΎΠΈΡΠΊΠ° ΠΎΠ΄Π½ΠΎΠΈ Π΄Π²ΡΡΠ²ΡΠ·Π½ΡΡ ΠΊΠΎΠΌΠΏΠΎΠ½Π΅Π½Ρ, ΡΠΎΠΏΠΎΠ»ΠΎΠ³ΠΈΡΠ΅ΡΠΊΠΎΠΉ ΡΠΎΡΡΠΈΡΠΎΠ²ΠΊΠΈ.
ΠΡΡΡΡ Π·Π°Π΄Π°Π½ Π³ΡΠ°ΡG = (V, E), Π³Π΄Π΅ V — ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°, E — ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ°. ΠΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, ΡΡΠΎ Π² Π½Π°ΡΠ°Π»ΡΠ½ΡΠΉ ΠΌΠΎΠΌΠ΅Π½Ρ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π²ΡΠ΅ Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ° ΠΎΠΊΡΠ°ΡΠ΅Π½Ρ Π² Π±Π΅Π»ΡΠΉ ΡΠ²Π΅Ρ. ΠΡΠΏΠΎΠ»Π½ΠΈΠΌ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π΄Π΅ΠΉΡΡΠ²ΠΈΡ:
ΠΠ· ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²Π° Π²ΡΠ΅Ρ Π±Π΅Π»ΡΡ Π²Π΅ΡΡΠΈΠ½ Π²ΡΠ±Π΅ΡΠ΅ΠΌ Π»ΡΠ±ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ, ΠΎΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ Π΅Ρ v1.
ΠΡΠΏΠΎΠ»Π½ΡΠ΅ΠΌ Π΄Π»Ρ Π½Π΅Ρ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ DFS (v1).
ΠΠ΅ΡΠ΅ΠΊΡΠ°ΡΠΈΠ²Π°Π΅ΠΌ Π΅Ρ Π² ΡΡΡΠ½ΡΠΉ ΡΠ²Π΅Ρ.
ΠΠΎΠ²ΡΠΎΡΡΠ΅ΠΌ ΡΠ°Π³ΠΈ 1−3 Π΄ΠΎ ΡΠ΅Ρ ΠΏΠΎΡ, ΠΏΠΎΠΊΠ° ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π±Π΅Π»ΡΡ Π²Π΅ΡΡΠΈΠ½ Π½Π΅ ΠΏΡΡΡΠΎ.
ΠΡΠΎΡΠ΅Π΄ΡΡΠ° DFS (ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ — Π²Π΅ΡΡΠΈΠ½Π°)
ΠΠ΅ΡΠ΅ΠΊΡΠ°ΡΠΈΠ²Π°Π΅ΠΌ Π²Π΅ΡΡΠΈΠ½Ρ u Π² ΡΠ΅ΡΡΠΉ ΡΠ²Π΅Ρ.
ΠΠ»Ρ Π²ΡΡΠΊΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ w, ΡΠΌΠ΅ΠΆΠ½ΠΎΠΉ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ u, Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΠΌ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ Π΄Π²Π° ΡΠ°Π³Π°:
ΠΡΠ»ΠΈ Π²Π΅ΡΡΠΈΠ½Π° w ΠΎΠΊΡΠ°ΡΠ΅Π½Π° Π² Π±Π΅Π»ΡΠΉ ΡΠ²Π΅Ρ, Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΠΌ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ DFS (w).
ΠΠΊΡΠ°ΡΠΈΠ²Π°Π΅ΠΌ w Π² ΡΡΡΠ½ΡΠΉ ΡΠ²Π΅Ρ.
ΠΠ°Π½Π½ΡΠΉ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ ΠΈ Π² ΠΌΠΎΠ΅ΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅, Π° Π² ΡΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²Π΅ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ Ρ ΠΎΠΏΠΈΡΠ°Π», ΠΊΠ°ΠΊ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡΡΡ ΠΌΠΎΠ΅ΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΎΠΉ ΠΈ Π΄Π°Π»Π΅Π΅ ΠΏΡΠΈΠ²Π΅Π» ΠΏΡΠΈΠΌΠ΅Ρ.
Π ΡΡΠ΅Π΄Π΅ wxDev-C++
Π― ΡΠ°Π·ΡΠ°Π±Π°ΡΡΠ²Π°Π» Π΄Π°Π½Π½ΡΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½ΡΠΉ ΠΏΡΠΎΠ΄ΡΠΊΡ Π² ΡΡΠ΅Π΄Π΅ wxDev-Π‘++.
wxDev-C++ ΡΠ²Π»ΡΠ΅ΡΡΡ ΡΠ°Π·Π²ΠΈΡΠΈΠ΅ΠΌ ΠΏΡΠΎΠ΅ΠΊΡΠ° Dev-C++, Π½ΠΎ ΡΠ°ΠΊΠΆΠ΅ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ Π΄ΠΈΠ·Π°ΠΉΠ½Π΅Ρ ΡΠΎΡΠΌ Π΄Π»Ρ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊΠΈ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ wxWidgets. WxDev-C++ Π²ΠΊΠ»ΡΡΠ°Π΅Ρ Π²ΡΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²Π° Dev-C++, Π° ΡΠ°ΠΊΠΆΠ΅ Π½ΠΎΠ²Π΅ΠΉΡΡΡ Π²Π΅ΡΡΠΈΡ wxWidgets Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΡΡ Π΄ΠΈΠ·Π°ΠΉΠ½Π΅ΡΡ ΡΠΎΡΠΌ Π΄Π»Ρ ΡΡΠ΅Π΄Ρ Π±ΡΡΡΡΠΎΠΉ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠΉ .
Π ΠΎΠ΄ΠΈΡΠ΅Π»Ρ wxDev-C++ - ΡΡΠΎ Dev-C++. Dev-C++ — ΡΠ²ΠΎΠ±ΠΎΠ΄Π½Π°Ρ ΠΈΠ½ΡΠ΅Π³ΡΠΈΡΠΎΠ²Π°Π½Π½Π°Ρ ΡΡΠ΅Π΄Π° ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠΉ Π΄Π»Ρ ΡΠ·ΡΠΊΠΎΠ² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ C/C++. Π Π΄ΠΈΡΡΡΠΈΠ±ΡΡΠΈΠ² Π²Ρ ΠΎΠ΄ΠΈΡ ΠΊΠΎΠΌΠΏΠΈΠ»ΡΡΠΎΡ MinGW. Π‘Π°ΠΌ Dev-C++ Π½Π°ΠΏΠΈΡΠ°Π½ Π½Π° Delphi. Π Π°ΡΠΏΡΠΎΡΡΡΠ°Π½ΡΠ΅ΡΡΡ ΡΠΎΠ³Π»Π°ΡΠ½ΠΎ GPL.
ΠΡΠΎΠ΅ΠΊΡ ΠΏΠΎΠ΄Π΄Π΅ΡΠΆΠΈΠ²Π°Π΅ΡΡΡ SourceForge. ΠΡΠ½ΠΎΠ²Π°ΡΠ΅Π»Ρ ΠΏΡΠΎΠ΅ΠΊΡΠ° ΠΠΎΠ»ΠΈΠ½ ΠΠ°ΠΏΠ»Π°Ρ, ΠΊΠΎΠΌΠΏΠ°Π½ΠΈΡ Bloodshed Software.
ΠΠ΄Π½ΠΎ Π²ΡΠ΅ΠΌΡ Π±ΡΠ» Π΄ΠΎΡΡΡΠΏΠ΅Π½ Linux-ΠΏΠΎΡΡ, ΠΎΠ΄Π½Π°ΠΊΠΎ Π½Π° Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ Π°ΠΊΡΡΠ°Π»ΠΈΠ·ΠΈΡΠΎΠ²Π°Π½Π° ΡΠΎΠ»ΡΠΊΠΎ Windows-Π²Π΅ΡΡΠΈΡ.
Π Π°Π·ΡΠ°Π±ΠΎΡΠΊΠ° Π² wxDev-C++
Π§ΡΠΎ Π±Ρ ΠΏΡΠΈΡΡΡΠΏΠΈΡΡ ΠΊ ΡΠ°Π±ΠΎΡΠ΅ Π² wxDev-C++ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π·Π°ΠΏΡΡΡΠΈΡΡ ΡΡΠ΅Π΄Ρ.
ΠΠ°Π»Π΅Π΅ Π² Π»Π΅Π²ΠΎΠΌ Π²Π΅ΡΡ Π½Π΅ΠΌ ΡΠ³Π»Ρ Π²ΡΠ±ΡΠ°ΡΡ ΡΠ°ΠΉΠ» (ΡΠΈΡ 6).
Π ΠΈΡΡΠ½ΠΎΠΊ 6 ΠΌΠ΅Π½Ρ wxDev-C++
Π€Π°ΠΉΠ»>Π‘ΠΎΠ·Π΄Π°ΡΡ>ΠΡΠΎΠ΅ΠΊΡ (ΡΠΈΡ7)
Π ΠΈΡΡΠ½ΠΎΠΊ 7 ΠΠ°ΠΊ ΡΠΎΠ·Π΄Π°ΡΡ ΠΏΡΠΎΠ΅ΠΊΡ Π² wxDev-C++
ΠΠ°Π»Π΅Π΅ Π² ΠΎΡΠΊΡΡΠ²ΡΠ΅ΠΌΡΡ ΠΎΠΊΠ½Π΅ Π²ΡΠ±ΡΠ°ΡΡ ΡΠΈΠΏ ΠΏΡΠΎΠ΅ΠΊΡΠ° ΠΈ Π·Π°Π΄Π°ΡΡ Π½Π°Π·Π²Π°Π½ΠΈΠ΅ (ΡΠΈΡ8).
Π ΠΈΡΡΠ½ΠΎΠΊ 8 ΡΠΎΠ·Π΄Π°Π½ΠΈΠ΅ ΠΏΡΠΎΠ΅ΠΊΡΠ° Π ΠΌΠΎΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ ΡΠΈΠΏ ΠΏΡΠΎΠ΅ΠΊΡΠ° — Console Application Π½Π°Π·Π²Π°Π½ΠΈΠ΅ h1.
ΠΠ°Π»Π΅Π΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π·Π°Π΄Π°ΡΡ ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΏΡΠΎΠ΅ΠΊΡΠ° Π½Π° ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ΅.
Π ΠΌΠΎΠ΅ΠΌ ΡΠ»ΡΡΠ°Π΅ (ΡΠΈΡ9) ΡΡΠΎ G: ΠΡΡΡΠΎΠ²Π°Ρ ΡΠ°Π±ΠΎΡΠ° ΠΏΠΎ Π΄ΠΈΡ. ΠΌΠ°Ρ
Π ΠΈΡΡΠ½ΠΎΠΊ 9 ΡΠ°ΡΠΏΠΎΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΏΡΠΎΠ΅ΠΊΡΠ° Π Π½Π°ΠΆΠ°ΡΡ ΠΊΠ½ΠΎΠΏΠΊΡ ΡΠΎΡ ΡΠ°Π½ΠΈΡΡ. ΠΠ°Π»Π΅Π΅ Π² ΠΎΡΠΊΡΡΠ²ΡΠ΅ΠΌΡΡ ΠΏΠΎΠ»Π΅ ΡΠ΅Π΄Π°ΠΊΡΠΎΡΠ° ΠΊΠΎΠ΄Π° Π²ΠΈΠ΄ΠΈΠΌ ΠΏΡΠ΅Π΄Π²Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΠΊΠΎΠΌΠΏΠΎΠ½ΠΎΠ²Π°Π½Π½ΡΠΉ Π·Π°Π³ΠΎΠ»ΠΎΠ²ΠΎΠΊ (ΡΠΈΡ10) ΠΈΠ· Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΈΡ ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΡΡ Π±ΠΈΠ±Π»ΠΈΠΎΡΠ΅ΠΊ ΠΈ Π³Π»Π°Π²Π½ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠΈ main, Ρ ΠΊΠΎΡΠΎΡΠΎΠΉ Π½Π°ΡΠΈΠ½Π°Π΅ΡΡΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ.
Π ΠΈΡΡΠ½ΠΎΠΊ 10 Π Π΅Π΄Π°ΠΊΡΠΎΡ ΠΊΠΎΠ΄Π° wxDev-C++
Π‘Π°ΠΌ ΠΊΠΎΠ΄ ΠΌΠΎΠ΅ΠΉ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π² ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠΈ Π.
Π ΡΠΊΠΎΠ²ΠΎΠ΄ΡΡΠ²ΠΎ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ ΠΠΎΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΈΡΠ΅Ρ ΠΈ Π²ΡΠ²ΠΎΠ΄ΠΈΡ Π½Π° ΡΠΊΡΠ°Π½ ΠΏΡΠΎΡΡΡΠ΅ ΡΠΈΠΊΠ»Ρ. ΠΠ½Π° ΠΎΡΠ΅Π½Ρ ΠΏΡΠΎΡΡΠ° Π² ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π½ΠΈΠΈ. ΠΠ°ΠΏΡΡΡΠΈΠ², Π΅Π΅ Π²Ρ ΠΏΠΎΠΉΠΌΠ΅ΡΠ΅ ΡΡΠΎ ΡΠ°ΠΌΠΈ.
ΠΡΠ°ΠΊ, Π·Π°ΠΏΡΡΡΠΈΠ»ΠΈ, ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΏΡΠΎΡΠΈΡ Π½Π°Ρ Π²Π²Π΅ΡΡΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ Π² Π³ΡΠ°ΡΠ΅ (ΡΠΈΡ3). ΠΠ²ΠΎΠ΄ΠΈΠΌ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ 4.
ΠΠ°Π»Π΅Π΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π²Π²Π΅ΡΡΠΈ ΡΠ΅Π±ΡΠ°, ΠΏΠΎΠΎΡΠ΅ΡΠ΅Π΄Π½ΠΎ ΠΎΠ΄Π½Ρ ΠΈ Π²ΡΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΡΠ΅Π±ΡΠ° (ΡΠΈΡ4).
Π ΠΈΡΡΠ½ΠΎΠΊ 3 ΠΏΠ΅ΡΠ²ΠΎΠ΅, ΡΡΠΎ Π²ΠΈΠ΄ΠΈΠΌ ΠΏΠΎΡΠ»Π΅ Π·Π°ΠΏΡΡΠΊΠ° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π³ΡΠ°Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΡΠΈΠΊΠ» ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π ΠΈΡΡΠ½ΠΎΠΊ 4 Π²Π²ΠΎΠ΄ΠΈΠΌ ΡΠ΅Π±ΡΠ° Π³ΡΠ°ΡΠ° ΠΠ°Π»Π΅Π΅ ΡΠ²ΠΈΠ΄ΠΈΠΌ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ — ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΠΉ ΡΠΈΠΊΠ», ΠΊΠΎΡΠΎΡΡΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π²ΡΠ²Π΅Π΄Π΅Ρ Π½Π° ΡΠΊΡΠ°Π½ Π² ΡΡΠΎΠΌ ΠΆΠ΅ ΠΎΠΊΠ½Π΅ (ΡΠΈΡ5).
Π ΠΈΡΡΠ½ΠΎΠΊ 5 ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ.
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
Π‘ΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠ΅ ΡΠΎΡΡΠΎΡΠ½ΠΈΠ΅ ΠΈ ΡΠ΅Π½Π΄Π΅Π½ΡΠΈΠΈ ΡΠ°Π·Π²ΠΈΡΠΈΡ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ ΡΠ΅Ρ Π½ΠΈΠΊΠΈ ΠΊΠ°ΠΊ ΠΎΡΠ½ΠΎΠ²Π½ΠΎΠ³ΠΎ ΠΈΠ½ΡΡΡΡΠΌΠ΅Π½ΡΠ° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΊΠΈ ΡΠ°ΠΊΠΎΠ²Ρ, ΡΡΠΎ Π½Π°ΡΡΠ΄Ρ Ρ ΡΠ²Π΅Π»ΠΈΡΠ΅Π½ΠΈΠ΅ΠΌ ΡΡΠ½ΠΊΡΠΈΠΎΠ½Π°Π»ΡΠ½ΠΎΡΡΠΈ Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½Π°Ρ ΡΠ΅Ρ Π½ΠΈΠΊΠ° ΠΏΡΠΈΠΎΠ±ΡΠ΅ΡΠ°Π΅Ρ ΡΠ²ΠΎΠΉΡΡΠ²Π°, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠΈΠ΅ ΡΠ°Π±ΠΎΡΠ°ΡΡ Π½Π° Π½Π΅ΠΉ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΠ΅Π»Ρ, Π½Π΅ ΡΠ°Π·Π±ΠΈΡΠ°ΡΡΠ΅ΠΌΡΡΡ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ. Π ΡΡΠΎΡ ΠΏΠ΅ΡΠΈΠΎΠ΄ ΠΏΠΎΡΠ²ΠΈΠ»ΡΡ Π±ΠΎΠ»Π΅Π΅ ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΠΉ ΠΈΠ½ΡΠ΅ΡΡΠ΅ΠΉΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌ. ΠΠΎΡΠ²ΠΈΠ»ΠΈΡΡ ΡΡΡΡΠΊΡΡΡΡ Π³ΡΠ°ΡΠΈΡΠ΅ΡΠΊΠΈΡ Π΄Π°Π½Π½ΡΡ ΠΈ Π±ΠΎΠ»Π΅Π΅ ΠΊΡΡΠΏΠ½ΡΠ΅, ΠΈΠ½ΡΠ΅Π³ΡΠ°Π»ΡΠ½ΡΠ΅ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΎΠ½Π½ΡΠ΅ Π΅Π΄ΠΈΠ½ΠΈΡΡ — ΠΎΠ±ΡΠ΅ΠΊΡΡ. Π‘Π»Π΅Π΄ΡΡΠ²ΠΈΠ΅ΠΌ ΡΡΠ°Π»ΠΎ Π±ΡΡΠ½ΠΎΠ΅ ΡΠ°Π·Π²ΠΈΡΠΈΠ΅ ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΠΎ-ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΡ ΡΠΈΡΡΠ΅ΠΌ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ, ΡΠ°ΠΊΠΈΡ ΠΊΠ°ΠΊ Visual C++, Visual BASIC ΠΈ Π΄ΡΡΠ³ΠΈΡ , Π² ΠΎΡΠ½ΠΎΠ²Π΅ ΠΊΠΎΡΠΎΡΡΡ Π»Π΅ΠΆΠΈΡ ΠΎΠ±ΡΠ°Π±ΠΎΡΠΊΠ° ΠΎΠ±ΡΠ΅ΠΊΡΠ½ΡΡ ΡΡΡΡΠΊΡΡΡ Π΄Π°Π½Π½ΡΡ . Π’Π°ΠΊΠΆΠ΅ ΠΏΠΎΡΠ²ΠΈΠ»ΠΈΡΡ Π½ΠΎΠ²ΡΠ΅ ΡΠ·ΡΠΊΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ADA, OCCAM.([3]) Π Π΅ΡΠ»ΠΈ ΡΠ°Π½ΡΡΠ΅ Π±ΠΎΠ»ΡΡΠΎΠΉ ΠΏΠΎΠΏΡΠ»ΡΡΠ½ΠΎΡΡΡΡ ΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π»ΠΈΡΡ ΠΏΡΠΎΡΡΡΠ΅ Π»ΠΈΠ½Π΅ΠΉΠ½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΠΎ Π² Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΡΠ°ΠΊΠΈΡ ΡΠΈΠΏΠΎΠ² ΠΊΠ°ΠΊ Π΄Π΅ΡΠ΅Π²ΡΡ, Π³ΡΠ°ΡΡ, ΡΠΏΠΈΡΠΊΠΈ, ΠΎΡΠ΅ΡΠ΅Π΄ΠΈ — ΠΏΠΎΠ»ΡΡΠ°ΡΡ Π²ΡΠ΅ Π±ΠΎΠ»ΡΡΠ΅Π΅ ΡΠ°ΡΠΏΡΠΎΡΡΡΠ°Π½Π΅Π½ΠΈΠ΅.
ΠΠ°Π·Π²Π°Π½Π½ΡΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ ΠΌΠΎΠ³ΡΡ Π½Π°ΠΉΡΠΈ ΡΠ²ΠΎΠΈ ΠΏΡΠΈΠΌΠ΅Π½Π΅Π½ΠΈΡ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°Ρ Π΄Π»Ρ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΡΡ ΠΈ ΠΊΠΎΠΌΠΌΡΠ½ΠΈΠΊΠ°ΡΠΈΠΎΠ½Π½ΡΡ ΡΠ΅ΡΠ΅ΠΉ, ΡΠ°ΠΊΠΈΡ ΠΊΠ°ΠΊ: ΠΆΠ΅Π»Π΅Π·Π½ΠΎΠ΄ΠΎΡΠΎΠΆΠ½ΠΎΠΉ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ½ΠΎΠΉ ΡΠ΅ΡΠΈ, Π³Π΄Π΅ Π²Π΅ΡΡΠΈΠ½Ρ — ΡΡΠ°Π½ΡΠΈΠΈ, ΡΠ²ΡΠ·ΠΈ — Π΄ΠΎΡΠΎΠ³ΠΈ, ΡΠ°ΠΊΡΠΎΠΌΠΎΡΠΎΡΠ½Π°Ρ ΡΠ΅ΡΡ: Π²Π΅ΡΡΠΈΠ½Ρ — ΠΌΠ΅ΡΡΠ° ΡΡΠΎΡΠ½ΠΊΠΈ Π°Π²ΡΠΎΠΌΠΎΠ±ΠΈΠ»Π΅ΠΉ, ΡΠ²ΡΠ·ΠΈ — ΠΏΡΡΠΈ ΠΏΠΎΠ΄ΡΠ΅Π·Π΄Π°; ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ΅Π½ΠΈΠ΅ ΠΏΠΎΡΠΎΠΊΠ° Π²Π΅ΡΠ΅ΡΡΠ²Π° ΠΏΠΎ ΡΠΈΡΡΠ΅ΠΌΠ΅ ΡΡΡΠ± Π² ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΡΠΉ ΠΏΡΠ½ΠΊΡ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ ΠΈ Ρ. Π΄. ΠΠ° ΠΎΡΠ½ΠΎΠ²Π΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΠΏΠΎΠΈΡΠΊΠ° Π² ΡΠΈΡΠΈΠ½Ρ Π² Π³ΡΠ°ΡΠ΅ ΠΌΠΎΠΆΠ½ΠΎ ΠΏΠΎΡΡΡΠΎΠΈΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π²ΡΠ²ΠΎΠ΄Π° Π΄Π΅ΡΠ΅Π²Π° Π½Π°ΠΈΠΌΠ΅Π½ΡΡΠ΅ΠΉ ΡΡΠΎΠΈΠΌΠΎΡΡΠΈ, ΡΡΠΎ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΡ ΡΠ°ΡΡΡΠΈΡΡΠ²Π°ΡΡ ΠΊΡΠ°ΡΡΠ°ΠΉΡΠΈΠ΅ ΠΏΡΡΠΈ ΠΊ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΌΡ ΠΌΠ΅ΡΡΡ Π½Π°Π·Π½Π°ΡΠ΅Π½ΠΈΡ (Π²Π΅ΡΡΠΈΠ½Π΅).
Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΡΠ°Π·Π²ΠΈΡΠΈΠ΅ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΎΠ½Π½ΡΡ ΡΠ΅Ρ Π½ΠΎΠ»ΠΎΠ³ΠΈΠΉ, ΠΈΡ ΠΏΡΠΎΠ½ΠΈΠΊΠ½ΠΎΠ²Π΅Π½ΠΈΠ΅ Π²ΠΎ Π²ΡΠ΅ ΠΎΠ±Π»Π°ΡΡΠΈ ΠΆΠΈΠ·Π½Π΅Π΄Π΅ΡΡΠ΅Π»ΡΠ½ΠΎΡΡΠΈ ΡΠ΅Π»ΠΎΠ²Π΅ΠΊΠ° ΡΡΠ΅Π±ΡΡΡ ΠΊΠΎΠΌΠΏΡΡΡΠ΅ΡΠ½ΠΎΠ³ΠΎ ΠΎΡΠΎΠ±ΡΠ°ΠΆΠ΅Π½ΠΈΡ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ Π² Π²ΠΈΠ΄Π΅ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΡ ΡΡΡΡΠΊΡΡΡ Π΄Π°Π½Π½ΡΡ . Π Π³ΡΠ°ΡΡ, ΡΠ²Π»ΡΡΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· ΡΠ°ΡΡΠ΅ΠΉ ΡΡΠΈΡ ΡΡΡΡΠΊΡΡΡ Π΄Π°Π½Π½ΡΡ , ΠΈΠ³ΡΠ°ΡΡ Π²Π°ΠΆΠ½ΡΡ ΡΠΎΠ»Ρ Π² ΡΠΎΠ²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΌ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ, Π³ΡΠ°ΡΡ Π²ΡΡΡΠ΅ΡΠ°ΡΡΡΡ Π² ΡΠΎΡΠ½ΡΡ ΡΠ°Π·Π½ΡΡ Π·Π°Π΄Π°Ρ.
Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠΉ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΡ
1.Π‘ΡΠ΄ΠΎΠΏΠ»Π°ΡΠΎΠ² Π‘. Π. ΠΠ°ΡΠ΅ΠΌΠ°ΡΠΈΡΠ΅ΡΠΊΠ°Ρ Π»ΠΎΠ³ΠΈΠΊΠ° ΠΈ ΡΠ΅ΠΎΡΠΈΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΠΎΠ²: ΡΡΠ΅Π±Π½ΠΈΠΊ / Π‘. Π. Π‘ΡΠ΄ΠΎΠΏΠ»Π°ΡΠΎΠ², Π. Π. ΠΠ²ΡΠΈΠ½Π½ΠΈΠΊΠΎΠ²Π°. Π.: ΠΠΠ€Π Π-Π, 2004. — 224 Ρ.
2. ΠΠ²Π°Π½ΠΎΠ² Π. Π. ΠΠΈΡΠΊΡΠ΅ΡΠ½Π°Ρ ΠΌΠ°ΡΠ΅ΠΌΠ°ΡΠΈΠΊΠ°. ΠΠ»Π³ΠΎΡΠΈΡΠΌΡ ΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ / Π. Π. ΠΠ²Π°Π½ΠΎΠ². Π.: ΠΠ°Π±ΠΎΡΠ°ΡΠΎΡΠΈΡ Π±Π°Π·ΠΎΠ²ΡΡ Π·Π½Π°Π½ΠΈΠΉ, 2003. — 288 Ρ.
3. ΠΡΠΈΡΡΠΎΡΠΈΠ΅Ρ Π. Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ². Π.: ΠΠΠ€Π Π-Π, 2004. — 328 Ρ.
ΠΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ Π
//ΠΠ°Π½Π° ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°. ΠΠ°ΠΉΡΠΈ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΡΠ½ΡΡ ΡΠΈΠΊΠ»ΠΎΠ²
//Π³ΡΠ°ΡΠ° (ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΡΡΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΏΠΎΠΈΡΠΊΠ° Π² Π³Π»ΡΠ±ΠΈΠ½Ρ)
#include
#include
#include
#include