Π Π°Π·ΡΠ°Π±ΠΎΡΠΊΠ° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ
ΠΡΠ»ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ v ΠΈ u ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Ρ ΡΠ΅Π±ΡΠΎΠΌ e, ΡΠΎ Π³ΠΎΠ²ΠΎΡΡΡ, ΡΡΠΎ ΠΎΠ½ΠΈ ΡΠΌΠ΅ΠΆΠ½Ρ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΎΠ±ΠΎΠΉ, Π° ΡΠ΅Π±ΡΠΎ e ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· Π½ΠΈΡ . ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ°, ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½Π΅ v Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ Π΄Π°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΠ»Ρ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Π²ΡΠ΄Π΅Π»ΡΡΡ Π²Ρ ΠΎΠ΄ΡΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ, ΡΠ°Π²Π½ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ Π²Ρ ΠΎΠ΄ΡΡΠΈΡ ΡΠ΅Π±Π΅Ρ ΠΈ ΠΈΡΡ ΠΎΠ΄ΡΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ, ΡΠ°Π²Π½ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ ΠΈΡΡ ΠΎΠ΄ΡΡΠΈΡ ΡΠ΅Π±Π΅Ρ, Π° ΡΡΠ΅ΠΏΠ΅Π½ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ Π² ΡΠ°ΠΊΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π½Π°Π·ΡΠ²Π°ΡΡ ΡΡΠΌΠΌΡ… Π§ΠΈΡΠ°ΡΡ Π΅ΡΡ >
Π Π°Π·ΡΠ°Π±ΠΎΡΠΊΠ° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ (ΡΠ΅ΡΠ΅ΡΠ°Ρ, ΠΊΡΡΡΠΎΠ²Π°Ρ, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½Π°Ρ)
ΠΠ½Π½ΠΎΡΠ°ΡΠΈΡ
Π Π΄Π°Π½Π½ΠΎΠΉ ΠΏΠΎΡΡΠ½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ Π·Π°ΠΏΠΈΡΠΊΠ΅ ΠΏΡΠΈΠ²Π΅Π΄Π΅Π½ΠΎ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡ ΡΠΏΠΈΡΠΊΡ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° ΠΈ ΡΠ°Π±ΠΎΡΠ° Ρ ΡΡΠΈΠΌ Π³ΡΠ°ΡΠΎΠΌ, ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ° Π΄ΡΠ³ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° ΠΏΠΎ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡ ΡΠΏΠΈΡΠΊΡ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° Π½Π°ΠΏΠΈΡΠ°Π½Π° Π½Π° ΡΠ·ΡΠΊΠ΅ C++ Π² ΠΈΠ½ΡΠ΅Π³ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ ΡΡΠ΅Π΄Π΅ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ Microsoft Visual Studio 2005. Π’Π°ΠΊ ΠΆΠ΅ Π² Π΄Π°Π½Π½ΠΎΠΉ ΠΏΠΎΡΡΠ½ΠΈΡΠ΅Π»ΡΠ½ΠΎΠΉ Π·Π°ΠΏΠΈΡΠΊΠ΅ ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Ρ ΡΠ΅Π·ΡΠ»ΡΡΠ°ΡΡ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ, ΠΏΡΠΎΠ²Π΅Π΄ΡΠ½ Π°Π½Π°Π»ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΈ ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ°.
ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΡ Π²Π΅ΡΡΠΈΠ½Π° Π³ΡΠ°Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌ
ΠΠ½Π½ΠΎΡΠ°ΡΠΈΡ Π‘ΠΎΠ΄Π΅ΡΠΆΠ°Π½ΠΈΠ΅
1. Π’Π΅ΠΎΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΡΠ°ΡΡΡ
2. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½Π°Ρ ΡΠ°ΡΡΡ
3. ΠΠ½Π°Π»ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΈ ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ
4. ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
5. Π‘ΠΏΠΈΡΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΠΎΠΉ Π»ΠΈΡΠ΅ΡΠ°ΡΡΡΡ
6. Π Π΅ΡΠ΅Π½ΠΈΠ΅ ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½ΡΡ ΠΏΡΠΈΠΌΠ΅ΡΠΎΠ²
7. ΠΡΡ ΠΎΠ΄Π½ΡΠΉ ΠΊΠΎΠ΄ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
1. Π’Π΅ΠΎΡΠ΅ΡΠΈΡΠ΅ΡΠΊΠ°Ρ ΡΠ°ΡΡΡ
ΠΡΠ°ΡΠΎΠΌ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠ°ΡΠ° (X, U), Π³Π΄Π΅ X — ΠΊΠΎΠ½Π΅ΡΠ½ΠΎΠ΅ ΠΌΠ½ΠΎΠΆΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, Π° U — Π½Π°Π±ΠΎΡ Π½Π΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ ΠΈ ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½ΡΡ ΠΏΠ°Ρ Π²Π΅ΡΡΠΈΠ½. ΠΠ±ΠΎΠ·Π½Π°ΡΠΈΠΌ Π³ΡΠ°Ρ G=(X, U). ΠΠ΅ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½Π°Ρ ΠΏΠ°ΡΠ° Π²Π΅ΡΡΠΈΠ½ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ΅Π±ΡΠΎΠΌ, ΡΠΏΠΎΡΡΠ΄ΠΎΡΠ΅Π½Π½Π°Ρ — Π΄ΡΠ³ΠΎΠΉ. ΠΡΠ°Ρ, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΠΉ ΡΠΎΠ»ΡΠΊΠΎ ΡΠ΅Π±ΡΠ°, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ Π½Π΅ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌ, ΡΠΎΠ»ΡΠΊΠΎ Π΄ΡΠ³ΠΈ — ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌ, ΠΈΠ»ΠΈ ΠΎΡΠ³ΡΠ°ΡΠΎΠΌ.
ΠΡΠ»ΠΈ Π²Π΅ΡΡΠΈΠ½Ρ v ΠΈ u ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Ρ ΡΠ΅Π±ΡΠΎΠΌ e, ΡΠΎ Π³ΠΎΠ²ΠΎΡΡΡ, ΡΡΠΎ ΠΎΠ½ΠΈ ΡΠΌΠ΅ΠΆΠ½Ρ ΠΌΠ΅ΠΆΠ΄Ρ ΡΠΎΠ±ΠΎΠΉ, Π° ΡΠ΅Π±ΡΠΎ e ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΠΎ ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΠΈΠ· Π½ΠΈΡ . ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ Π³ΡΠ°ΡΠ°, ΠΈΠ½ΡΠΈΠ΄Π΅Π½ΡΠ½ΡΡ Π²Π΅ΡΡΠΈΠ½Π΅ v Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ Π΄Π°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΠ»Ρ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Π²ΡΠ΄Π΅Π»ΡΡΡ Π²Ρ ΠΎΠ΄ΡΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ, ΡΠ°Π²Π½ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ Π²Ρ ΠΎΠ΄ΡΡΠΈΡ ΡΠ΅Π±Π΅Ρ ΠΈ ΠΈΡΡ ΠΎΠ΄ΡΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ, ΡΠ°Π²Π½ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Ρ ΠΈΡΡ ΠΎΠ΄ΡΡΠΈΡ ΡΠ΅Π±Π΅Ρ, Π° ΡΡΠ΅ΠΏΠ΅Π½ΡΡ Π²Π΅ΡΡΠΈΠ½Ρ Π² ΡΠ°ΠΊΠΎΠΌ ΡΠ»ΡΡΠ°Π΅ Π½Π°Π·ΡΠ²Π°ΡΡ ΡΡΠΌΠΌΡ Π΅Π΅ Π²Ρ ΠΎΠ΄ΡΡΠ΅ΠΉ ΠΈ ΠΈΡΡ ΠΎΠ΄ΡΡΠ΅ΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ. ΠΠ΅ΡΡΠΈΠ½Ρ, ΠΈΠΌΠ΅ΡΡΠΈΠ΅ ΡΡΠ΅ΠΏΠ΅Π½Ρ 0, Π½Π°Π·ΡΠ²Π°ΡΡ ΠΈΠ·ΠΎΠ»ΠΈΡΠΎΠ²Π°Π½Π½ΡΠΌΠΈ.
ΠΠ»Ρ ΠΎΡΠ³ΡΠ°ΡΠ° Π½Π° ΡΠΈΡ. 3 Π²Ρ ΠΎΠ΄ΡΡΠΈΠ΅ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ Π²Π΅ΡΡΠΈΠ½ 1,2,3,4,5 ΡΠ°Π²Π½Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ 0,1,1,1,0, ΠΈΡΡ ΠΎΠ΄ΡΡΠΈΠ΅ — 2,0,0,1,0. Π‘ΡΠ΅ΠΏΠ΅Π½ΠΈ Π²Π΅ΡΡΠΈΠ½, ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌΡΠ΅ ΡΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅ΠΌ Π²Ρ ΠΎΠ΄ΡΡΠΈΡ ΠΈ ΠΈΡΡ ΠΎΠ΄ΡΡΠΈΡ ΡΡΠ΅ΠΏΠ΅Π½Π΅ΠΉ ΡΠ°Π²Π½Ρ 2,1,1,2,0. Π’Π°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠ², Π²Π΅ΡΡΠΈΠ½Π° 5 — ΠΈΠ·ΠΎΠ»ΠΈΡΠΎΠ²Π°Π½Π½Π°Ρ.
Π Π΅Π±ΡΠΎ, ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡΠ΅Π΅ Π²Π΅ΡΡΠΈΠ½Ρ ΡΠ°ΠΌΡ Ρ ΡΠΎΠ±ΠΎΠΉ, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠ΅ΡΠ»Π΅ΠΉ. ΠΡΠ»ΠΈ ΠΎΠ΄Π½Ρ ΠΏΠ°ΡΡ Π²Π΅ΡΡΠΈΠ½ ΡΠΎΠ΅Π΄ΠΈΠ½ΡΡΡ Π΄Π²Π° ΠΈΠ»ΠΈ Π±ΠΎΠ»Π΅Π΅ ΡΠ΅Π±Π΅Ρ, ΡΠΎ ΡΠ°ΠΊΠΈΠ΅ ΡΠ΅Π±ΡΠ° Π½Π°Π·ΡΠ²Π°ΡΡ ΠΊΡΠ°ΡΠ½ΡΠΌΠΈ. ΠΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΡΠΎΡΡΡΠΌ, Π΅ΡΠ»ΠΈ ΠΎΠ½ Π½Π΅ ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ Π½ΠΈ ΠΏΠ΅ΡΠ΅Π»Ρ, Π½ΠΈ ΠΊΡΠ°ΡΠ½ΡΡ ΡΠ΅Π±Π΅Ρ, ΠΈΠ½Π°ΡΠ΅ Π³ΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΌΡΠ»ΡΡΠΈΠ³ΡΠ°ΡΠΎΠΌ. (Π Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΠΈΡΡΠΎΡΠ½ΠΈΠΊΠ°Ρ Π³ΡΠ°Ρ Ρ ΠΊΡΠ°ΡΠ½ΡΠΌΠΈ ΡΠ΅Π±ΡΠ°ΠΌΠΈ Π½Π°Π·ΡΠ²Π°ΡΡ ΠΌΡΠ»ΡΡΠΈΠ³ΡΠ°ΡΠΎΠΌ, Ρ ΠΏΠ΅ΡΠ»ΡΠΌΠΈ — ΠΏΡΠ΅Π²Π΄ΠΎΠ³ΡΠ°ΡΠΎΠΌ). ΠΡΠΎΡΡΠΎΠΉ Π³ΡΠ°Ρ, Π»ΡΠ±Π°Ρ ΠΏΠ°ΡΠ° Π²Π΅ΡΡΠΈΠ½ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ ΡΠΎΠ΅Π΄ΠΈΠ½Π΅Π½Π° ΡΠ΅Π±ΡΠΎΠΌ, Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠΎΠ»Π½ΡΠΌ.
ΠΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΡΠ°Π·ΡΠ΅ΠΆΠ΅Π½Π½ΡΠΌ, Π΅ΡΠ»ΠΈ ΠΎΠ±ΡΠ΅Π΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ΅Π±Π΅Ρ Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΠΌΠ΅Π½ΡΡΠ΅ ΠΈΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΠ³ΠΎ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π°. ΠΠ½Π°ΡΠ΅ Π³ΡΠ°Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠ»ΠΎΡΠ½ΡΠΌ.
2. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ½Π°Ρ ΡΠ°ΡΡΡ
ΠΠ±ΡΠΈΠ΅ ΡΠ²Π΅Π΄Π΅Π½ΠΈΡ ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΏΠΎ Π·Π°Π΄Π°Π½Π½ΠΎΠΌΡ ΡΠΏΠΈΡΠΊΡ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Π½Π°ΠΏΠΈΡΠ°Π½Π° Π½Π° ΡΠ·ΡΠΊΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΡ C++ Π² ΠΈΠ½ΡΠ΅Π³ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠΉ ΡΡΠ΅Π΄Π΅ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠΊΠΈ Microsoft Visual Studio 2005. ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΈΠΌΠ΅Π΅Ρ ΠΈΠΌΡ «ΠΡΡΡΠΎΠ²Π°Ρ ΡΠ°Π±ΠΎΡΠ° (ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌ. 2 ΡΠ΅ΠΌΠ΅ΡΡΡ)».
ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΡΠΎΠ΄Π΅ΡΠΆΠΈΡ ΠΎΠΊΠΎΠ»ΠΎ 560 ΡΡΡΠΎΠΊ ΠΊΠΎΠ΄Π° ΠΈ Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ ΠΎΠΊΠΎΠ»ΠΎ 116 ΠΠ Π½Π° ΠΆΡΡΡΠΊΠΎΠΌ Π΄ΠΈΡΠΊΠ΅.
Π‘ΡΡΡΠΊΡΡΡΠ½Π°Ρ ΡΡ Π΅ΠΌΠ° ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° «ΠΡΡΡΠΎΠ²Π°Ρ ΡΠ°Π±ΠΎΡΠ° «ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌ. 2 ΡΠ΅ΠΌΠ΅ΡΡΡ» ΡΠ°Π·Π±ΠΈΡΠ° Π½Π° ΡΡΠ½ΠΊΡΠΈΠΈ, ΡΡΠΎ Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎ ΡΠΏΡΠΎΡΠ°Π΅Ρ Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠ΅ ΠΈ ΠΎΡΠ»Π°Π΄ΠΊΡ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΊΠΎΠ΄Π°. Π‘ΡΡΡΠΊΡΡΡΠ½Π°Ρ ΡΡ Π΅ΠΌΠ° ΠΏΡΠ΅Π΄ΡΡΠ°Π²Π»Π΅Π½Π° Π½Π° ΡΠΈΡΡΠ½ΠΊΠ΅ 2.1.
Π‘ΠΏΠΈΡΠΎΠΊ ΡΡΠ½ΠΊΡΠΈΠΉ ΠΠ»Ρ ΡΠ΅ΡΠ΅Π½ΠΈΡ ΠΏΠΎΡΡΠ°Π²Π»Π΅Π½Π½ΠΎΠΉ Π·Π°Π΄Π°ΡΠΈ Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠΈΠ΅ ΡΡΠ½ΠΊΡΠΈΠΈ:
Β· void _input (int &var),
void _input (char &output, char mode = 'b'),
void _input (string &var)
ΠΠ΅ΡΠ΅Π³ΡΡΠΆΠ΅Π½Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ _input. Π‘Π»ΡΠΆΠΈΡ, ΡΡΠΎΠ±Ρ ΠΎΠ±Π΅Π·ΠΎΠΏΠ°ΡΠΈΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΎΡ Π²Π²ΠΎΠ΄Π° Π½Π΅Π²Π΅ΡΠ½ΡΡ Π΄Π°Π½Π½ΡΡ . Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΡΠΈΠΏΠ° int, string ΠΈΠ»ΠΈ char, ΠΏΠ΅ΡΠ΅Π΄Π°Π²Π°Π΅ΠΌΠΎΠ΅ ΠΏΠΎ ΡΡΡΠ»ΠΊΠ΅.
Β· bool fileExists (string fileName)
Π€ΡΠ½ΠΊΡΠΈΡ ΠΏΡΠΎΠ²Π΅ΡΡΠ΅Ρ ΡΠ°Π»ΠΉ Π½Π° ΡΡΡΠ΅ΡΡΠ²ΠΎΠ²Π°Π½ΠΈΠ΅. Π€ΡΠ½ΠΊΡΠΈΠΈ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ Π°ΡΠ³ΡΠΌΠ΅Π½ΡΠ° ΡΠΈΠΏΠ° string ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΡΡ ΠΈΠΌΡ ΡΠ°ΠΉΠ»Π°. ΠΠΎΠ·Π²ΡΠ°ΡΠ°Π΅ΡΡΡ true, Π΅ΡΠ»ΠΈ ΡΠ°ΠΉΠ» ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ, ΠΈΠ»ΠΈ false, Π΅ΡΠ»ΠΈ ΡΠ°ΠΉΠ» Ρ ΡΠΊΠ°Π·Π°Π½Π½ΡΠΌ ΠΈΠΌΠ΅Π½Π΅ΠΌ Π½Π΅ Π½Π°ΠΉΠ΄Π΅Π½.
Β· void main ()
Π’ΠΎΡΠΊΠ° Π²Ρ ΠΎΠ΄Π° Π² ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΠ΅.
Β· DirectedGraph *assembleGraph (int &NUM_VERTEX, ostream *stream)
Π€ΡΠ½ΠΊΡΠΈΡ, ΡΠΎΠ±ΠΈΡΠ°ΡΡΠ°Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ ΠΏΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ°ΠΌ. Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠΈΠΏΠ° int, NUM_VERTEX, ΠΏΠ΅ΡΠ΅Π΄Π°Π²Π°Π΅ΠΌΡΡ ΠΏΠΎ ΡΡΡΠ»ΠΊΠ΅, ΠΊΠΎΡΠΎΡΠ°Ρ Π²ΠΏΠΎΡΠ»Π΅Π΄ΡΡΠ²ΠΈΠΈ Π±ΡΠ΄Π΅Ρ Ρ ΡΠ°Π½ΠΈΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°. Π’Π°ΠΊ ΠΆΠ΅ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ *stream Π½Π° ΠΏΠΎΡΠΎΠΊ Π²ΡΠ²ΠΎΠ΄Π° Π΄Π°Π½Π½ΡΡ .
Β· bool getArcData (string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout)
ΠΠ°Π½Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ ΠΏΡΠΎΠΈΠ·Π²ΠΎΠ΄ΠΈΡ ΡΡΠ΅Π½ΠΈΠ΅ ΠΈΠ· ΡΠ°ΠΉΠ»Π°, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠ΅Π³ΠΎ ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½, ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π·Π½Π°ΡΠ΅Π½ΠΈΡ Π·Π° ΠΎΠ΄ΠΈΠ½ Π²ΡΠ·ΠΎΠ². ΠΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ graphName ΡΠΈΠΏΠ° string, ΠΏΡΠΈΠ½ΠΈΠΌΠ°ΡΡΠΈΠΉ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΠΈΠΌΠ΅Π½ΠΈ ΡΠ°ΠΉΠ»Π° Π±Π΅Π· ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΡ, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Ρ ΡΠ°Π½ΠΈΡΡΡ Π³ΡΠ°Ρ, ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ NUM_VERTEX ΡΠΈΠΏΠ° int, ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΠΈΠΉΡΡ ΠΏΠΎ ΡΡΡΠ»ΠΊΠ΅, ΡΡΡΠ»ΠΊΡ Π½Π° ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ lastNode ΡΠΈΠΏΠ° DirectedGraph, Π° ΡΠ°ΠΊ ΠΆΠ΅ ΡΡΡΠ»ΠΊΡ Π½Π° ΠΏΠΎΡΠΎΠΊ Π²ΡΠ²ΠΎΠ΄Π° Π΄Π°Π½Π½ΡΡ . Π€ΡΠ½ΠΊΡΠΈΡ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ ΡΠΈΠΏΠ° bool, ΠΏΠΎΠΊΠ°Π·ΡΠ²Π°ΡΡΠ΅Π΅, ΠΏΡΠ΅ΠΊΡΠ°ΡΠΈΠ»ΡΡ Π»ΠΈ Π²Π²ΠΎΠ΄ ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ ΠΈΠ»ΠΈ Π½Π΅Ρ.
Β· int findVertexAndPrintNewList (DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevelOfVertex, ostream *stream)
Π€ΡΠ½ΠΊΡΠΈΡ Π²ΡΠ²ΠΎΠ΄ΠΈΡ Π½Π° ΡΠΊΡΠ°Π½ ΠΈΠ»ΠΈ Π² ΡΠ°ΠΉΠ» ΡΡΠ΅ΠΏΠ΅Π½ΠΈ Π²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½, Π° ΡΠ°ΠΊ ΠΆΠ΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ ΠΈΠ΄Π΅Π½ΡΠΈΡΠΈΠΊΠ°ΡΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ, ΠΈΠΌΠ΅ΡΡΠ΅ΠΉ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π°, ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ Π΅Π³ΠΎ. Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ Π°ΡΠ³ΡΠΌΠ΅Π½ΡΠΎΠ² ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ°, ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°, ΠΏΡΡΡΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ maxLevelOfVertex, ΠΊΠΎΡΠΎΡΠ°Ρ ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π² ΡΠ΅Π»Π΅ Π΄Π°Π½Π½ΠΎΠΉ ΡΡΠ½ΠΊΡΠΈΠΈ, Π° ΡΠ°ΠΊ ΠΆΠ΅ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠΎΡΠΎΠΊ Π²ΡΠ²ΠΎΠ΄Π° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΈ.
Β· bool foundInArray (int value, int *arr, int NUM_ITEMS)
Π€ΡΠ½ΠΊΡΠΈΡ ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ Π°ΡΠ³ΡΠΌΠ΅Π½ΡΠΎΠ² Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅, Π½Π°Π»ΠΈΡΠΈΠ΅ ΠΊΠΎΡΠΎΡΠΎΠ³ΠΎ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ, ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΎΠ΄Π½ΠΎΠΌΠ΅ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΡΠΈΠΏΠ° int ΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΌΠ°ΡΡΠΈΠ²Π°. ΠΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΠΈΡΡΠΈΠ½Ρ, Π΅ΡΠ»ΠΈ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ Π΅ΡΡΡ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Ρ Π·Π°Π΄Π°Π½Π½ΡΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ, ΠΈΠ»ΠΈ Π»ΠΎΠΆΡ, Π΅ΡΠ»ΠΈ Π² ΠΌΠ°ΡΡΠΈΠ²Π΅ ΡΠ°ΠΊΠΎΠ³ΠΎ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠ° Π½Π΅Ρ.
Β· fstream openFile (string fileName, char mode)
Π€ΡΠ½ΠΊΡΠΈΡ ΠΎΡΠΊΡΡΠ²Π°ΡΡΠ°Ρ ΡΠ°ΠΉΠ» Π΄Π»Ρ Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠ΅ΠΆΠΈΠΌΠ°: I — ΡΡΠ΅Π½ΠΈΠ΅, o — Π·Π°ΠΏΠΈΡΡ, a — Π΄ΠΎΠ·Π°ΠΏΠΈΡΡ. Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ Π°ΡΠ³ΡΠΌΠ΅Π½ΡΠΎΠ² ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΡΡ ΠΈΠΌΡ ΡΠ°ΠΉΠ»Π° ΠΈ ΡΠ΅ΠΆΠΈΠΌ. ΠΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΠΎΠ±ΡΠ΅ΠΊΡ ΠΊΠ»Π°ΡΡΠ° fstream.
Β· void removeNode (DirectedGraph *node, DirectedGraph *&firstNode)
ΠΠ°Π½Π½Π°Ρ ΡΡΠ½ΠΊΡΠΈΡ ΡΠ΄Π°Π»ΡΠ΅Ρ ΠΈΠ· Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ° ΠΏΠ΅ΡΠ΅Π΄Π°Π½Π½ΡΠΉ Π΅ΠΉ Π² ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΠ΅ΡΠ²ΠΎΠ³ΠΎ Π°ΡΠ³ΡΠΌΠ΅Π½ΡΠ° ΡΠ»Π΅ΠΌΠ΅Π½Ρ. Π’Π°ΠΊ ΠΆΠ΅ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΡΡ ΡΡΡΠ»ΠΊΠ° Π½Π° ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ°.
Β· void removeAdjacentVertex (DirectedGraph *&firstArc, int vertexId, int vertexLevel)
Π€ΡΠ½ΠΊΡΠΈΡ ΡΠ΄Π°Π»ΡΠ΅Ρ ΠΈΠ· Π³ΡΠ°ΡΠ° Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π·Π°Π΄Π°Π½Π½ΠΎΠΉ (ΠΈΠ΄Π΅Π½ΡΠΈΡΠΈΠΊΠ°ΡΠΎΡ Π·Π°Π΄Π°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΡΡ Π² ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠ° vertexId). ΠΠ΅ΡΠ²ΡΠΉ Π°ΡΠ³ΡΠΌΠ΅Π½Ρ ΡΡΠ½ΠΊΡΠΈΠΈ — ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ°, ΡΡΠ΅ΡΠΈΠΉ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ — ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° ΠΏΠ΅ΡΠ΅Π΄Π°Π²Π°Π΅ΠΌΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ.
Β· void printNeiborhoodsList (DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, string title = «»)
Π€ΡΠ½ΠΊΡΠΈΡ Π²ΡΠ²ΠΎΠ΄ΠΈΡ ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° Π½Π° ΡΠΊΡΠ°Π½ ΠΈΠ»ΠΈ Π² ΡΠ°ΠΉΠ». ΠΠ΅ΡΠ²ΡΠΉ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ — ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ°, Π²ΡΠΎΡΠΎΠΉ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ — ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠΎΡΠΎΠΊ Π²ΡΠ²ΠΎΠ΄Π°, ΡΡΠ΅ΡΠΈΠΉ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ — ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠΎΡΠΎΠΊ Π²ΡΠ²ΠΎΠ΄Π°, ΡΠ΅ΡΠ²ΡΡΡΡΠΉ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π² Π³ΡΠ°ΡΠ΅, ΠΏΡΡΡΠΉ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡ — Π·Π°Π³ΠΎΠ»ΠΎΠ²ΠΎΠΊ ΠΏΠ΅ΡΠ΅Π΄ Π²ΡΠ²ΠΎΠ΄ΠΎΠΌ Π½Π° ΡΠΊΡΠ°Π½ ΠΈΠ»ΠΈ Π² ΡΠ°ΠΉΠ».
Β· bool **completeAdjacencyMatrix (DirectedGraph *firstNode, int NUM_VERTEX)
Π€ΡΠ½ΠΊΡΠΈΡ ΡΠΎΠ·Π΄Π°ΡΡ ΠΈ Π·Π°ΠΏΠΎΠ»Π½ΡΠ΅Ρ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Π΄Π»Ρ Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°. Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΡΡ ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ° ΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π² Π³ΡΠ°ΡΠ΅. ΠΠΎΠ·Π²ΡΠ°ΡΠ°Π΅ΡΡΡ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΌΠ°ΡΡΠΈΠ².
Β· void printMatrix (bool **matrix, int dimension, ostream *stream, string title = «»)
ΡΡΠ½ΠΊΡΠΈΡ, Π²ΡΠ²ΠΎΠ΄ΡΡΠ°Ρ ΠΌΠ°ΡΡΠΈΡΡ Π½Π° ΡΠΊΡΠ°Π½ ΠΈΠ»ΠΈ Π² ΡΠ°ΠΉΠ». Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ Π°ΡΠ³ΡΠΌΠ΅Π½ΡΠΎΠ² ΠΏΠ΅ΡΠ΅Π΄Π°ΡΡΡΡ ΠΌΠ°ΡΡΠΈΡΠ°, ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° Π²ΡΡ ΠΎΠ΄Π½ΠΎΠΉ ΠΏΠΎΡΠΎΠΊ ΠΈ Π·Π°Π³ΠΎΠ»ΠΎΠ²ΠΎΠΊ, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²Π΅Π½Π½ΠΎ.
Β· void clearMatrix (bool **matrix, int dimention)
ΡΡΠ½ΠΊΡΠΈΡ ΠΎΡΠΈΡΠ°Π΅Ρ ΠΏΠ°ΠΌΡΡΡ, ΠΎΡΠ²Π΅Π΄ΡΠ½Π½ΡΡ ΠΏΠΎΠ΄ ΠΌΠ°ΡΡΠΈΡΡ matrix Ρ ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΡΡ dimention.
Β· int getKeyByValue (int value, int *arr, int numItems)
Π€ΡΠ½ΠΊΡΠΈΡ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΡΠ΅Ρ ΠΈ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ Π½ΠΎΠΌΠ΅Ρ ΠΊΠ»ΡΡΠ° ΠΌΠ°ΡΡΠΈΠ²Π°, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΉ Π·Π½Π°ΡΠ΅Π½ΠΈΡ value. Π ΠΊΠ°ΡΠ΅ΡΡΠ²Π΅ ΠΏΠ°ΡΠ°ΠΌΠ΅ΡΡΠΎΠ² ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅Ρ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ Π΄Π»Ρ ΠΏΠΎΠΈΡΠΊΠ°, ΠΎΠ΄Π½ΠΎΠΌΠ΅ΡΠ½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ² ΠΈ Π΅Π³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΡ.
ΠΡ ΠΎΠ΄Π½ΡΠ΅ ΠΈ Π²ΡΡ ΠΎΠ΄Π½ΡΠ΅ Π΄Π°Π½Π½ΡΠ΅ ΠΡΠΎΠ³ΡΠ°ΠΌΠΌΠ° ΠΏΠΎΠ»ΡΡΠ°Π΅Ρ Π΄Π°Π½Π½ΡΠ΅ ΠΈΠ· ΡΠ°ΠΉΠ»Π°, Π² ΠΊΠΎΡΠΎΡΠΎΠΌ Ρ ΡΠ°Π½ΠΈΡΡΡ ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°. Π‘ΡΡΡΠΊΡΡΡΠ° ΡΠ°ΠΉΠ»Π° Π΄ΠΎΠ»ΠΆΠ½Π° Π±ΡΡΡ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΉ: Π½ΠΎΠΌΠ΅Ρ ΡΡΡΠΎΠΊΠΈ ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ Π½ΠΎΠΌΠ΅Ρ (ΠΈΠ΄Π΅Π½ΡΠΈΡΠΈΠΊΠ°ΡΠΎΡ) Π²Π΅ΡΡΠΈΠ½Ρ Π³ΡΠ°ΡΠ°, Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅ ΡΠ΅ΡΠ΅Π· ΠΏΡΠΎΠ±Π΅Π» Π·Π°ΠΏΠΈΡΠ°Π½Ρ ΠΈΠ΄Π΅Π½ΡΠΈΡΠΈΠΊΠ°ΡΠΎΡΡ Π²Π΅ΡΡΠΈΠ½, Π² ΠΊΠΎΡΠΎΡΡΠ΅ Π²Ρ ΠΎΠ΄ΡΡ Π΄ΡΠ³ΠΈ, ΠΈΡΡ ΠΎΠ΄ΡΡΠΈΠ΅ ΠΈΠ· ΡΠ΅ΠΊΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½Ρ. ΠΡΠ»ΠΈ Π²Π΅ΡΡΠΈΠ½Π° Π½Π΅ ΠΈΠΌΠ΅Π΅Ρ ΠΈΡΡ ΠΎΠ΄ΡΡΠΈΡ Π΄ΡΠ³, ΡΠΎ Π² ΡΡΡΠΎΠΊΠ΅, ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠ΅ΠΉ Π΄Π°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Π΅ ΡΡΠΎΠΈΡ 0. ΠΠ° ΠΎΡΠ½ΠΎΠ²Π΅ ΡΡΠΈΡΠ°Π½Π½ΡΡ ΠΈΠ· ΡΠ°ΠΉΠ»Π° Π΄Π°Π½Π½ΡΡ ΡΡΡΠΎΠΈΡΡΡ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΈΠΉ Π΄Π²ΡΠ½Π°ΠΏΡΠ°Π²Π»Π΅Π½Π½ΡΠΉ Π»ΠΈΠ½Π΅ΠΉΠ½ΡΠΉ ΡΠΏΠΈΡΠΎΠΊ, Ρ ΡΠ°Π½ΡΡΠΈΠΉ ΡΠΏΠΈΡΠΎΠΊ Π΄ΡΠ³ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°.
ΠΠ° Π²ΡΡ ΠΎΠ΄Π΅ Π²ΡΠ²ΠΎΠ΄ΡΡΡΡ:
Β· ΠΈΠΌΡ Π³ΡΠ°ΡΠ°;
Β· ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½, ΠΊΠΎΡΠΎΡΡΠΌ Π·Π°Π΄Π°Π½ Π΄Π°Π½Π½ΡΠΉ Π³ΡΠ°Ρ;
Β· ΡΡΠ΅ΠΏΠ΅Π½ΠΈ ΠΈΡΡ ΠΎΠ΄Π° Π²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½ ΠΈ ΠΈΠ΄Π΅Π½ΡΠΈΡΠΈΠΊΠ°ΡΠΎΡ Π²Π΅ΡΡΠΈΠ½Ρ Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ ΠΈΡΡ ΠΎΠ΄Π°;
Β· ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ° ΠΏΠΎΡΠ»Π΅ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½, ΡΠΌΠ΅ΠΆΠ½ΡΡ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ, ΠΈΠΌΠ΅ΡΡΠ΅ΠΉ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π°;
Β· ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Π½ΠΎΠ²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΠΎΠ΄Π½ΠΎΠΉ ΠΈΠ· ΡΡΠ½ΠΊΡΠΈΠΉ Π€ΡΠ½ΠΊΡΠΈΡ completeAjacencyMatrix.
ΠΠ°ΡΠ°ΠΌΠ΅ΡΡΡ, ΠΏΡΠΈΠ½ΠΈΠΌΠ°Π΅ΠΌΡΠ΅ ΡΡΠ½ΠΊΡΠΈΠ΅ΠΉ:
Β· *firstNode — ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΏΠ΅ΡΠ²ΡΠΉ ΡΠ·Π΅Π» Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ°;
Β· NUM_VERTEX — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°
3. ΠΠ½Π°Π»ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΠΈ ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ
ΠΠ½Π°Π»ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΠ»Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΡΠ°ΡΡΡΠΈΡΠ°ΡΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ ΡΠΈΠΊΠ»ΠΎΠ² Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅.
ΠΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ ΡΠΈΠΊΠ»ΠΎΠ² Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° Π΄ΡΠ³ Π² Π³ΡΠ°ΡΠ΅, Π° ΡΠ°ΠΊ ΠΆΠ΅ ΠΎΡ Π²Π΅Π»ΠΈΡΠΈΠ½Ρ ΠΈΠ΄Π΅Π½ΡΠΈΡΠΈΠΊΠ°ΡΠΎΡΠ° Π²Π΅ΡΡΠΈΠ½Ρ Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ ΠΈΡΡ ΠΎΠ΄Π° ΠΈ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ ΠΈΡΡ ΠΎΠ΄Π° ΡΡΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ.
ΠΡΡΡΡ M — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄ΡΠ³ Π³ΡΠ°ΡΠ°, — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄ΡΠ³ Π³ΡΠ°ΡΠ° ΠΏΠΎΡΠ»Π΅ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½, ΡΠΌΠ΅ΠΆΠ½ΡΡ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ, ΠΈΠΌΠ΅ΡΡΠ΅ΠΉ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° (Π΄Π°Π»Π΅Π΅ — ΡΠ΄Π°Π»Π΅Π½ΠΈΠ΅), N — ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ Π³ΡΠ°ΡΠ°, — ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ. Π’ΠΎΠ³Π΄Π° ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ ΠΈΡΠ΅ΡΠ°ΡΠΈΠΉ ΡΠΈΠΊΠ»ΠΎΠ² Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅ ΠΌΠΎΠΆΠ½ΠΎ Π²ΡΡΠΈΡΠ»ΠΈΡΡ ΠΏΠΎ ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΉ ΡΠΎΡΠΌΡΠ»Π΅:
Π€ΠΎΡΠΌΡΠ»Π° 1
ΠΠ½Π°Π»ΠΈΠ· ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΠ»Ρ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½ΠΈΡ ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π½Π΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠΏΡΠ΅Π΄Π΅Π»ΠΈΡΡ ΡΠ°Π·ΠΌΠ΅Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ° ΠΈ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ.
Π Π°Π·ΠΌΠ΅Ρ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ° ΠΈ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Π·Π°Π²ΠΈΡΠΈΡ ΠΎΡ Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ° ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ, Π² ΡΠ°ΡΡΠ½ΠΎΡΡΠΈ ΠΎΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΡΡΡΠΎΠΊ ΠΈ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΡΠΈΡΠ΅Π» Π² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ ΡΡΡΠΎΠΊΠ΅.
ΠΠ°ΠΆΠ΄ΡΠΉ ΡΠ·Π΅Π» Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΡΠΏΠΈΡΠΊΠ°, ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡΡΠ΅Π³ΠΎΡΡ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅, ΠΈΠΌΠ΅Π΅Ρ ΡΠ»Π΅Π΄ΡΡΡΡΡ ΡΡΡΡΠΊΡΡΡΡ:
struct DirectedGraph {
ArcGraph oneArc;
DirectedGraph *previousArc;
DirectedGraph *nextArc;
};
Π ΡΠΎΡΡΠ°Π² Π΄Π°Π½Π½ΠΎΠΉ ΡΡΡΡΠΊΡΡΡΡ Π²Ρ ΠΎΠ΄ΡΡ: ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ-ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΡΠ΅Π»Ρ ΡΡΡΡΠΊΡΡΡΠ½ΠΎΠ³ΠΎ ΡΠΈΠΏΠ° ArcGraph oneArc, Π΄Π²Π° ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ ΡΠΈΠΏΠ° int (ΠΏΠΎΠ΄ Π΄Π°Π½Π½ΡΠ΅ ΡΠΈΠΏΠ° int ΠΎΡΠ²ΠΎΠ΄ΠΈΡΡΡ ΡΠ΅ΡΡΡΠ΅ Π±Π°ΠΉΡΠ°). Π’Π°ΠΊ ΠΊΠ°ΠΊ ΡΡΡΡΠΊΡΡΡΠ° ArgGraph ΡΠΎΡΡΠΎΠΈΡ ΠΈΠ· Π΄Π²ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠΈΠΏΠ° int, ΡΠΎ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ oneArc ΠΈΠΌΠ΅Π΅Ρ ΡΠ°Π·ΠΌΠ΅Ρ 8 Π±Π°ΠΉΡ. Π ΡΡΠΎΠ³ΠΎ ΡΠ»Π΅Π΄ΡΠ΅Ρ, ΡΡΠΎ Π΄Π°Π½Π½Π°Ρ ΡΡΡΡΠΊΡΡΡΠ° ΠΈΠΌΠ΅Π΅Ρ ΡΠ°Π·ΠΌΠ΅Ρ 4+4+8 = 16 Π±Π°ΠΉΡ.
ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈΠΌΠ΅Π΅Ρ ΡΠΈΠΏ bool, ΡΠΎ Π΅ΡΡΡ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΡΡ Π±ΡΠ΄Π΅Ρ ΠΈΠΌΠ΅ΡΡ ΡΠ°Π·ΠΌΠ΅Ρ 1 Π±Π°ΠΉΡ.
Π’Π°ΠΊ ΠΆΠ΅ Π² ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ΅ ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΡΡ: ΡΠΊΠ°Π·Π°ΡΠ΅Π»Ρ Π½Π° ΠΎΠ±ΡΠ΅ΠΊΡ ΠΊΠ»Π°ΡΡΠ° ostream, Π·Π°Π½ΠΈΠΌΠ°ΡΡΠΈΠΉ 80 Π±Π°ΠΉΡ, ΠΎΠ±ΡΠ΅ΠΊΡ ΠΊΠ»Π°ΡΡΠ° fstream, Π·Π°Π½ΠΈΠΌΠ°ΡΡΠΈΠΉ 184 Π±Π°ΠΉΡΠ°, ΠΎΠ±ΡΠ΅ΠΊΡ ΠΊΠ»Π°ΡΡΠ° string, Π·Π°Π½ΠΈΠΌΠ°ΡΡΠΈΠΉ 32 Π±Π°ΠΉΡΠ°, ΠΏΡΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠΈΠΏΠ° short, ΠΊΠ°ΠΆΠ΄Π°Ρ ΠΈΠ· ΠΊΠΎΡΠΎΡΡΡ Π·Π°Π½ΠΈΠΌΠ°Π΅Ρ 2 Π±Π°ΠΉΡΠ°, ΡΡΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠΈΠΏΠ° int, Π·Π°Π½ΠΈΠΌΠ°ΡΡΠΈΡ ΠΏΠΎ 4 Π±Π°ΠΉΡΠ°, ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½Π°Ρ ΡΠΈΠΏΠ° bool, Π·Π°Π½ΠΈΠΌΠ°ΡΡΠ°Ρ 1 Π±Π°ΠΉΡ ΠΈ ΡΠ΅ΠΌΠ½Π°Π΄ΡΠ°ΡΡ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠΈΠΏΠ° char, Π·Π°Π½ΠΈΠΌΠ°ΡΡΠΈΡ ΠΏΠΎ 1 Π±Π°ΠΉΡΡ.
ΠΡΠΈΠ½ΡΠ² Π·Π° M ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄ΡΠ³ Π² Π³ΡΠ°ΡΠ΅, Π·Π° N ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½, Π° ΡΠ°ΠΊ ΠΆΠ΅ Ρ ΡΡΡΡΠΎΠΌ ΠΏΠ°ΠΌΡΡΠΈ, Π·Π°Π½ΠΈΠΌΠ°Π΅ΠΌΠΎΠΉ Π²ΡΠ΅ΠΌΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅Π½Π½ΡΠΌΠΈ, ΠΌΡ ΠΏΠΎΠ»ΡΡΠΈΠΌ ΡΠ»Π΅Π΄ΡΡΡΡΡ ΡΠΎΡΠΌΡΠ»Ρ
ΠΠ°ΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅
ΠΠΎ Π²ΡΠ΅ΠΌΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΠΊΡΡΡΠΎΠ²ΠΎΠΉ ΡΠ°Π±ΠΎΡΡ Π±ΡΠ» ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°Π½ Π°Π»Π³ΠΎΡΠΈΡΠΌ, ΡΠ΅ΡΠ°ΡΡΠΈΠΉ ΠΏΠΎΡΡΠ°Π²Π»Π΅Π½Π½ΡΡ Π·Π°Π΄Π°ΡΡ. ΠΠΎ ΡΠΎΡΡΠ°Π²Π»Π΅Π½Π½ΠΎΠΌΡ Π°Π»Π³ΠΎΡΠΈΡΠΌΡ Π±ΡΠ»Π° Π½Π°ΠΏΠΈΡΠ°Π½Π° ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠ°, ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΡΠ°Ρ:
Β· ΠΠ²ΠΎΠ΄ΠΈΡΡ ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ ΠΎΡΠΈΠ΅Π½ΡΠΈΡΠΎΠ²Π°Π½Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° ΠΈΠ· ΡΠ°ΠΉΠ»Π°;
Β· ΠΡΠ²ΠΎΠ΄ΠΈΡΡ Π½Π° ΡΠΊΡΠ°Π½ ΠΈΠ»ΠΈ Π² ΡΠ°ΠΉΠ» ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ ΠΈ ΡΡΠ΅ΠΏΠ΅Π½ΠΈ ΠΈΡΡ ΠΎΠ΄Π° Π²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½;
Β· ΠΠ°Ρ ΠΎΠ΄ΠΈΡΡ Π²Π΅ΡΡΠΈΠ½Ρ Ρ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠ΅ΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ ΠΈΡΡ ΠΎΠ΄Π°;
Β· Π£Π΄Π°Π»ΡΡΡ Π²Π΅ΡΡΠΈΠ½Ρ, ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ, ΠΈΠΌΠ΅ΡΡΠ΅ΠΉ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π°;
Β· Π‘ΠΎΡΡΠ°Π²Π»ΡΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈ Π²ΡΠ²ΠΎΠ΄ΠΈΡΡ Π΅Ρ Π½Π° ΡΠΊΡΠ°Π½ ΠΈΠ»ΠΈ Π² ΡΠ°ΠΉΠ».
«C/C++ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π° ΡΠ·ΡΠΊΠ΅ Π²ΡΡΠΎΠΊΠΎΠ³ΠΎ ΡΡΠΎΠ²Π½Ρ» Π’. Π. ΠΠ°Π²Π»ΠΎΠ²ΡΠΊΠ°Ρ.
«ΠΠΎΠ»Π½ΡΠΉ ΡΠΏΡΠ°Π²ΠΎΡΠ½ΠΈΠΊ ΠΏΠΎ Π‘++, 4-Π΅ ΠΈΠ·Π΄Π°Π½ΠΈΠ΅» ΠΠ΅ΡΠ±Π΅ΡΡ Π¨ΠΈΠ»Π΄Ρ
«Π’Π΅ΠΎΡΠΈΡ Π³ΡΠ°ΡΠΎΠ²» Π. Π. ΠΠ΅Π»ΠΎΠ², Π£. Π. ΠΠΎΡΠΎΠ±ΡΡΠ².
Π Π΅ΡΠ΅Π½ΠΈΠ΅ ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½ΡΡ ΠΏΡΠΈΠΌΠ΅ΡΠΎΠ²
ΠΡΠΈΠΌΠ΅Ρ 1
ΠΡΡ ΠΎΠ΄Π½ΡΠΉ Π³ΡΠ°Ρ:
ΠΡΠ°Ρ ΠΏΠΎΡΠ»Π΅ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ:
ΠΌΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΡΠΉ Π³ΡΠ°Ρ Π°Π»Π³ΠΎΡΠΈΡΠΌ ΠΠ½Π°Π»ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ:
ΠΡΠΏΠΎΠ»ΡΠ·ΡΡ ΡΠΎΡΠΌΡΠ»Ρ 1, Π° ΡΠ°ΠΊ ΠΆΠ΅ Ρ ΡΡΡΡΠΎΠΌ ΡΠΎΠ³ΠΎ, ΡΡΠΎ M = 38, 16, N = 17, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 1: 3, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 2: 2, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 3: 4, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 4: 1, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 5: 2, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 6: 2, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 7: 2, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 8: 1, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 9: 2, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 10: 6, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 11: 3, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 12: 2, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 13: 1, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 14: 1, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 15: 1, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 16: 1, ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ 17: 4, ΠΏΠΎΠ»ΡΡΠΈΠΌ:
626 ΠΏΡΠΎΡ ΠΎΠ΄ΠΎΠ² ΠΏΠΎ ΡΠΈΠΊΠ»Π°ΠΌ.
ΠΠ½Π°Π»ΠΈΠ· ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ:
Π Π΄Π°Π½Π½ΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄ΡΠ³ M = 38, ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ N = 17. Π’Π΅ΠΏΠ΅ΡΡ ΡΠ°ΡΡΡΠΈΡΠ°Π΅ΠΌ ΡΠΌΠΊΠΎΡΡΠ½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ Π΄Π»Ρ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ°:
961 Π±Π°ΠΉΡ ΠΏΠ°ΠΌΡΡΠΈ.
Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ:
ΠΡΠΈΠΌΠ΅Ρ 2
ΠΡΡ ΠΎΠ΄Π½ΡΠΉ Π³ΡΠ°Ρ:
ΠΡΠ°Ρ ΠΏΠΎΡΠ»Π΅ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ:
ΠΠ½Π°Π»ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ:
ΠΠ»Ρ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²Π° ΠΏΡΠΎΡ ΠΎΠ΄ΠΎΠ² ΠΏΠΎ ΡΠΈΠΊΠ»Π°ΠΌ Π²ΠΎΡΠΏΠΎΠ»ΡΠ·ΡΠ΅ΠΌΡΡ ΡΠΎΡΠΌΡΠ»ΠΎΠΉ 1:
1540 ΠΏΡΠΎΡ ΠΎΠ΄ΠΎΠ² ΠΏΠΎ ΡΠΈΠΊΠ»Π°ΠΌ.
ΠΠ½Π°Π»ΠΈΠ· ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ:
Π Π΄Π°Π½Π½ΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄ΡΠ³ M = 65, ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ N = 31. ΠΡΡ ΠΎΠ΄Ρ ΠΈΠ· ΡΡΠΎΠ³ΠΎ, ΡΠ°ΡΡΡΠΈΡΠ°Π΅ΠΌ ΡΠΌΠΊΠΎΡΡΠ½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ:
1407 Π±Π°ΠΉΡ ΠΏΠ°ΠΌΡΡΠΈ.
Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ:
ΠΡΠΈΠΌΠ΅Ρ 3
ΠΡΡ ΠΎΠ΄Π½ΡΠΉ Π³ΡΠ°Ρ:
ΠΡΠ°Ρ ΠΏΠΎΡΠ»Π΅ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ:
ΠΠ½Π°Π»ΠΈΠ· Π²ΡΠ΅ΠΌΠ΅Π½Π½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ:
ΠΠΎΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π²ΡΠΈΡΡ ΡΠΎΡΠΌΡΠ»ΠΎΠΉ 1, ΡΠ°ΡΡΡΠΈΡΠ°Π΅ΠΌ Π²ΡΠ΅ΠΌΠ΅Π½Π½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π΄Π»Ρ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ° (ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄ΡΠ³ M = 181,, N = 77):
7601 ΠΏΡΠΎΡ ΠΎΠ΄ ΠΏΠΎ ΡΠΈΠΊΠ»Π°ΠΌ.
ΠΠ½Π°Π»ΠΈΠ· ΡΠΌΠΊΠΎΡΡΠ½ΠΎΠΉ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΠΈ:
Π Π΄Π°Π½Π½ΠΎΠΌ ΠΏΡΠΈΠΌΠ΅ΡΠ΅ ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π΄ΡΠ³ M = 181, ΠΊΠΎΠ»ΠΈΡΠ΅ΡΡΠ²ΠΎ Π²Π΅ΡΡΠΈΠ½ N = 77. ΠΡΡ ΠΎΠ΄Ρ ΠΈΠ· ΡΡΠΎΠ³ΠΎ, Π²ΡΡΠΈΡΠ»ΠΈΠΌ ΡΠΌΠΊΠΎΡΡΠ½ΡΡ ΡΠ»ΠΎΠΆΠ½ΠΎΡΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π΄Π»Ρ Π΄Π°Π½Π½ΠΎΠ³ΠΎ ΠΏΡΠΈΠΌΠ΅ΡΠ° ΠΏΠΎ ΡΠΎΡΠΌΡΠ»Π΅ 2:
3309 Π±Π°ΠΉΡ ΠΏΠ°ΠΌΡΡΠΈ.
Π Π΅Π·ΡΠ»ΡΡΠ°ΡΡ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ:
4. ΠΡΡ ΠΎΠ΄Π½ΡΠΉ ΠΊΠΎΠ΄ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ:
#include «stdafx.h»
#include
#include
#include
#include
using namespace std;
struct ArcGraph {
int outVertexId;
int inVertexId;
};
struct DirectedGraph {
ArcGraph oneArc;
DirectedGraph *previousArc;
DirectedGraph *nextArc;
};
void _input (int &var) {
int BAD_STATE = 2;
do {
cin.clear ();
cin.sync ();
cin >> var;
} while (cin.rdstate () == BAD_STATE);
}
void _input (char &output, char mode = 'b') {
const char OUTPUT_MODE = 'o', ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's';
bool successfulInput;
do {
cin.sync ();
cin >> output;
if (output == 'e') exit (0);
switch (mode) output == 'd'
} while (!successfulInput);
}
void _input (string &var) {
cin.sync ();
getline (cin, var);
}
bool fileExists (string fileName) {
return (ifstream (fileName) ≠ NULL);
}
void main () {
setlocale (LC_ALL, «Russian»);
system («cls»);
static DirectedGraph *firstArc, *sideNode;
static ostream *out;
static fstream fileForOutput;
static string fileForOutputName;
static short CURRENT_STAGE = 0;
static int vertexWithMaxLevel, maxLevel, NUM_VERTEX = 0;
static bool **adjacencyMatrix, fileOutput;
static char action;
const static short START_EXECUTION = 0, INPUT_DATA = 1, THE_MAIN_PART = 2, SOME_ACTIONS_PERFORMED = 3;
const static char ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's',
YES = 'y', NO = 'n',
ON_THE_SCREEN = 's', INTO_A_FILE = 'f',
FOR_INPUT = 'i', FOR_OUTPUT = 'o', FOR_APPEND = 'a',
PRINT_NEIBORHOODS = 'p', MAKE_ADJACENCY_MATRIX = 'm', DELETE_VERTEX = 'd', RESTART_PROGRAM = 'r', SAVE_NEW_GRAPH = 's', EXIT = 'e';
DirectedGraph *assembleGraph (int &NUM_VERTEX, ostream *stream);
fstream openFile (string fileName, char mode);
int findVertexAndPrintNewList (DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevel, ostream *stream);
bool **completeAdjacencyMatrix (DirectedGraph *firstNode, int NUM_VERTEX);
bool saveGraph (string fileName, DirectedGraph *firstNode, int NUM_VERTEX);
void removeAdjacentVertex (DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel);
void removeNode (DirectedGraph *node, DirectedGraph *&firstNode);
void printNeiborhoodsList (DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = «»);
void printMatrix (bool **matrix, int dimension, ostream *stream, string title = «»);
void clearMatrix (bool **matrix, int dimention);
switch (CURRENT_STAGE) {
case START_EXECUTION:
cout << «Π Π΅ΠΆΠΈΠΌ Π²Π²ΠΎΠ΄Π° Π΄Π°Π½Π½ΡΡ (f — Π² ΡΠ°ΠΉΠ», s — Π½Π° ΡΠΊΡΠ°Π½, e — Π²ΡΡ ΠΎΠ΄): «;
_input (action, FOR_OUTPUT);
switch (action) {
case ON_THE_SCREEN:
out = &cout;
fileOutput = false;
break;
case INTO_A_FILE:
cout << «ΠΠΌΡ ΡΠ°ΠΉΠ»Π° Π΄Π»Ρ Π·Π°ΠΏΠΈΡΠΈ (ΡΠ°ΡΡΠΈΡΠ΅Π½ΠΈΠ΅ Π½Π΅ ΡΡΠ΅Π±ΡΠ΅ΡΡΡ): «;
_input (fileForOutputName);
if (fileExists («output/» +fileForOutputName+" .txt"))
fileForOutput = openFile («output/» +fileForOutputName+" .txt", FOR_APPEND);
else
fileForOutput = openFile («output/» +fileForOutputName+" .txt", FOR_OUTPUT);
out = &fileForOutput;
fileOutput = true;
break;
}
CURRENT_STAGE = INPUT_DATA;
break;
case INPUT_DATA:
firstArc = assembleGraph (NUM_VERTEX, out);
CURRENT_STAGE = THE_MAIN_PART;
break;
case THE_MAIN_PART:
cout << «Π‘ΠΏΠΈΡΠΎΠΊ Π΄ΠΎΡΡΡΠΏΠ½ΡΡ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ:» << endl;
cout << PRINT_NEIBORHOODS << «- Π²ΡΠ²Π΅ΡΡΠΈ ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ» << endl;
cout << MAKE_ADJACENCY_MATRIX << «- ΡΠΎΡΡΠ°Π²ΠΈΡΡ ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ» << endl;
cout << DELETE_VERTEX << «- ΡΠ΄Π°Π»ΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ, ΠΈΠΌΠ΅ΡΡΠ΅ΠΉ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π°, Π²Π΅ΡΡΠΈΠ½Ρ» << endl;
cout << RESTART_PROGRAM << «- Π½Π°ΡΠ°ΡΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΡΠ½Π°ΡΠ°Π»Π°» << endl;
cout << EXIT << «- Π²ΡΡ ΠΎΠ΄» << endl;
_input (action, MAIN_MODE);
switch (action) {
case PRINT_NEIBORHOODS:
printNeiborhoodsList (firstArc, out, NUM_VERTEX, false, «ΠΡΠ°Ρ Π·Π°Π΄Π°Π½ ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ ΡΠΏΠΈΡΠΊΠΎΠΌ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ:»);
*out << endl << endl;
if (fileOutput)
cout << «Π‘ΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Π·Π°ΠΏΠΈΡΠ°Π½ Π² ΡΠ°ΠΉΠ».» << endl;
break;
case MAKE_ADJACENCY_MATRIX:
adjacencyMatrix = completeAdjacencyMatrix (firstArc, NUM_VERTEX);
printMatrix (adjacencyMatrix, NUM_VERTEX, out, «ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°: «);
clearMatrix (adjacencyMatrix, NUM_VERTEX);
*out << endl << endl;
if (fileOutput)
cout << «ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ ΠΈΡΡ ΠΎΠ΄Π½ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Π·Π°ΠΏΠΈΡΠ°Π½Π° Π² ΡΠ°ΠΉΠ».» << endl;
break;
case DELETE_VERTEX:
vertexWithMaxLevel = findVertexAndPrintNewList (firstArc, NUM_VERTEX, maxLevel, out);
*out << endl;
NUM_VERTEX -= maxLevel;
removeAdjacentVertex (firstArc, NUM_VERTEX, vertexWithMaxLevel, maxLevel);
if (fileOutput)
cout << «ΠΠ΅ΡΡΠΈΠ½Ρ, ΡΠΌΠ΅ΠΆΠ½ΡΠ΅ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ, ΠΈΠΌΠ΅ΡΡΠ΅ΠΉ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π°, ΡΠ΄Π°Π»Π΅Π½Ρ,» << endl
<< «Π‘ΡΠ΅ΠΏΠ΅Π½ΠΈ ΠΈΡΡ ΠΎΠ΄Π° Π²ΡΠ΅Ρ Π²Π΅ΡΡΠΈΠ½ Π·Π°ΠΏΠΈΡΠ°Π½Ρ Π² ΡΠ°ΠΉΠ».» << endl;
CURRENT_STAGE = SOME_ACTIONS_PERFORMED;
break;
case RESTART_PROGRAM:
while (firstArc ≠ NULL) {
sideNode = firstArc;
firstArc = firstArc->nextArc;
delete sideNode;
}
if (fileOutput) {
fileForOutput.close ();
*out << endl << endl;
cout << «ΠΠ°ΠΏΠΈΡΡ Π² ΡΠ°ΠΉΠ» ΡΡΠΏΠ΅ΡΠ½ΠΎ Π·Π°Π²Π΅ΡΡΠ΅Π½Π°!» << endl;
}
CURRENT_STAGE = START_EXECUTION;
break;
}
break;
case SOME_ACTIONS_PERFORMED:
cout << «Π‘ΠΏΠΈΡΠΎΠΊ Π΄ΠΎΡΡΡΠΏΠ½ΡΡ Π΄Π΅ΠΉΡΡΠ²ΠΈΠΉ:» << endl;
cout << PRINT_NEIBORHOODS << «- Π²ΡΠ²Π΅ΡΡΠΈ ΡΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ» << endl;
cout << MAKE_ADJACENCY_MATRIX << «- ΡΠΎΡΡΠ²ΠΈΡΡ ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ ΠΌΠ°ΡΡΠΈΡΡ ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ» << endl;
cout << SAVE_NEW_GRAPH << «- ΡΠΎΡ ΡΠ°Π½ΠΈΡΡ Π½ΠΎΠ²ΡΠΉ Π³ΡΠ°Ρ» << endl;
cout << RESTART_PROGRAM << «- Π½Π°ΡΠ°ΡΡ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΡΠ½Π°ΡΠ°Π»Π°» << endl;
cout << EXIT << «- Π²ΡΡ ΠΎΠ΄» << endl;
_input (action, SOME_ACTIONS_MODE);
switch (action) {
case PRINT_NEIBORHOODS:
printNeiborhoodsList (firstArc, out, NUM_VERTEX, false, «Π‘ΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π³ΡΠ°ΡΠ° ΠΏΠΎΡΠ»Π΅ ΡΠ΄Π°Π»Π΅Π½ΠΈΡ Π²Π΅ΡΡΠΈΠ½, ΡΠΌΠ΅ΠΆΠ½ΡΡ Ρ Π²Π΅ΡΡΠΈΠ½ΠΎΠΉ, ΠΈΠΌΠ΅ΡΡΠ΅ΠΉ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΡΡ ΡΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π°:»);
*out << endl << endl;
if (fileOutput)
cout << «Π‘ΠΏΠΈΡΠΎΠΊ ΠΎΠΊΡΠ΅ΡΡΠ½ΠΎΡΡΠ΅ΠΉ Π½ΠΎΠ²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Π·Π°ΠΏΠΈΡΠ°Π½ Π² ΡΠ°ΠΉΠ».» << endl;
break;
case MAKE_ADJACENCY_MATRIX:
adjacencyMatrix = completeAdjacencyMatrix (firstArc, NUM_VERTEX);
printMatrix (adjacencyMatrix, NUM_VERTEX, out, «ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Π½ΠΎΠ²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°: «);
clearMatrix (adjacencyMatrix, NUM_VERTEX);
*out << endl << endl;
if (fileOutput)
cout << «ΠΠ°ΡΡΠΈΡΠ° ΡΠΌΠ΅ΠΆΠ½ΠΎΡΡΠΈ Π½ΠΎΠ²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ° Π·Π°ΠΏΠΈΡΠ°Π½Π° Π² ΡΠ°ΠΉΠ».» << endl;
break;
case SAVE_NEW_GRAPH:
cout << «ΠΠ²Π΅Π΄ΠΈΡΠ΅ ΠΈΠΌΡ Π½ΠΎΠ²ΠΎΠ³ΠΎ Π³ΡΠ°ΡΠ°: «;
_input (fileForOutputName);
if (!saveGraph (fileForOutputName, firstArc, NUM_VERTEX))
cout << «ΠΡΠ°Ρ Ρ ΡΠ°ΠΊΠΈΠΌ ΠΈΠΌΠ΅Π½Π΅ΠΌ «<< fileForOutputName << «ΡΠΆΠ΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ!» << endl;
else
cout << «Π‘ΠΎΡ ΡΠ°Π½Π΅Π½ΠΈΠ΅ Π³ΡΠ°ΡΠ° ΠΏΡΠΎΠΈΠ·Π²Π΅Π΄Π΅Π½ΠΎ ΡΡΠΏΠ΅ΡΠ½ΠΎ.» << endl;
break;
case RESTART_PROGRAM:
while (firstArc ≠ NULL) {
sideNode = firstArc;
firstArc = firstArc->nextArc;
delete sideNode;
}
if (fileOutput) {
fileForOutput.close ();
*out << endl << endl;
cout << «ΠΠ°ΠΏΠΈΡΡ Π² ΡΠ°ΠΉΠ» ΡΡΠΏΠ΅ΡΠ½ΠΎ Π·Π°Π²Π΅ΡΡΠ΅Π½Π°!» << endl;
}
CURRENT_STAGE = START_EXECUTION;
break;
}
}
system («pause»);
main ();
}
DirectedGraph *assembleGraph (int &NUM_VERTEX, ostream *stream) {
DirectedGraph *firstNode = NULL, *lastNode = NULL, *currentNode;
bool getArcData (string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout);
string graphName;
cout << «ΠΠΌΡ Π³ΡΠ°ΡΠ°: «;
_input (graphName);
if (getArcData (graphName, NUM_VERTEX, firstNode, stream)) {
currentNode = firstNode;
while (getArcData (graphName, NUM_VERTEX, lastNode)) {
lastNode->previousArc = currentNode;
lastNode->nextArc = NULL;
currentNode->nextArc = lastNode;
currentNode = lastNode;
}
}
return firstNode;
}
bool getArcData (string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout) {
static fstream fileForReadGraph;
string filePath = «graphs/» ;
int inVertexId;
static int counter = 0;
char sideChar;
static bool firstIn = true;
bool fileExists (string fileName);
fstream openFile (string fileName, char mode);
if (firstIn) {
if (!fileExists (filePath+graphName+" .txt")) {
cout << «ΠΡΠ°ΡΠ° Ρ ΡΠ°ΠΊΠΈΠΌ ΠΈΠΌΠ΅Π½Π΅ΠΌ Π½Π΅ ΡΡΡΠ΅ΡΡΠ²ΡΠ΅Ρ!» << endl << «ΠΡΠ΄Π΅Ρ Π·Π°Π³ΡΡΠΆΠ΅Π½ ΡΡΠ°Π½Π΄Π°ΡΡΠ½ΡΠΉ ΡΠ°ΠΉΠ».. .» << endl;
graphName = «default» ;
}
fileForReadGraph = openFile (filePath+graphName+" .txt", 'i');
*stream << «ΠΡΠ°Ρ «<< graphName << endl;
firstIn = false;
counter++;
}
if (fileForReadGraph.eof ()) {
firstIn = true;
NUM_VERTEX = counter;
counter = 0;
fileForReadGraph.close ();
return false;
}
lastNode = (DirectedGraph*) new (DirectedGraph);
lastNode->previousArc = NULL;
lastNode->nextArc = NULL;
if (lastNode == NULL) {
cout << «ΠΠ°ΠΌΡΡΡ Π½Π΅ Π²ΡΠ΄Π΅Π»ΠΈΠ»Π°ΡΡ!» << endl << «ΠΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π·Π°Π²Π΅ΡΡΠ΅Π½ΠΎ.. .» ;
Sleep (1000);
exit (1);
}
fileForReadGraph >> inVertexId;
lastNode->oneArc.inVertexId = inVertexId;
lastNode->oneArc.outVertexId = counter;
sideChar = fileForReadGraph. get ();
if (sideChar == 'n')
counter++;
return true;
}
int findVertexAndPrintNewList (DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevelOfVertex, ostream *stream) {
int counter, inVertexCounter, vertexWithMaxLevel = 0;
maxLevelOfVertex = 0;
for (counter = 1; counter <= NUM_VERTEX; counter++) {
inVertexCounter = 0;
while ((firstNode ≠ NULL) && (firstNode->oneArc.outVertexId == counter)) {
inVertexCounter++;
firstNode = firstNode->nextArc;
}
*stream << «Π‘ΡΠ΅ΠΏΠ΅Π½Ρ ΠΈΡΡ ΠΎΠ΄Π° Π²Π΅ΡΡΠΈΠ½Ρ «<< counter << «: «<< inVertexCounter << endl;
if (inVertexCounter > maxLevelOfVertex) {
maxLevelOfVertex = inVertexCounter;
vertexWithMaxLevel = counter;
}
}
*stream << «ΠΠ΅ΡΡΠΈΠ½Π° Ρ ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡΠ½ΠΎΠΉ ΡΡΠ΅ΠΏΠ΅Π½ΡΡ ΠΈΡΡ ΠΎΠ΄Π°: «<< vertexWithMaxLevel << endl;
return vertexWithMaxLevel;
}
int foundInArray (int value, int *arr, int rightBound) {
int counter, middle, leftBound = 0;
if ((value > arr[rightBound]) || (value < arr[leftBound]))
return -1;
counter = 0;
while ((rightBound-leftBound) > 1) {
middle = (rightBound+leftBound)/2;
if (arr[middle] < value)
leftBound = middle;
else
rightBound = middle;
}
for (counter = 0; counter <= rightBound; counter++) {
if (arr[counter] == value)
return counter;
}
return -1;
}
fstream openFile (string fileName, char mode) {
fstream filePointer;
switch (mode) {
case 'i': filePointer. open (fileName, ios_base:in); break;
case 'o': filePointer. open (fileName, ios_base:out); break;
case 'a': filePointer. open (fileName, ios_base:app); break;
}
return filePointer;
}
void removeNode (DirectedGraph *node, DirectedGraph *&firstNode) {
if ((node->previousArc ≠ NULL) && (node->nextArc ≠ NULL)) {
node->previousArc->nextArc = node->nextArc;
node->nextArc->previousArc = node->previousArc;
} else if ((node->previousArc == NULL) && (node->nextArc ≠ NULL)) {
node->nextArc->previousArc = NULL;
firstNode = node->nextArc;
} else if ((node->previousArc ≠ NULL) && (node->nextArc == NULL)) {
node->previousArc->nextArc = NULL;
} else if ((node->previousArc == NULL) && (node->nextArc == NULL)) {
firstNode = NULL;
}
delete node;
}
bool saveGraph (string fileName, DirectedGraph *firstNode, int NUM_VERTEX) {
bool fileExists (string fileName);
void printNeiborhoodsList (DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = «»);
fstream openFile (string fileName, char mode);
if (fileExists («graphs/» +fileName+" .txt")) return false;
fstream file;
file = openFile («graphs/» +fileName+" .txt", 'o');
printNeiborhoodsList (firstNode, &file, NUM_VERTEX, true);
return true;
}
void removeAdjacentVertex (DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel) {
DirectedGraph *currentNode, *nodePointer, *sidePointer;
int counter, currentId, *adjacentVertex, *newVertexId, NOT_FOUND = -1;
bool noOneBefore;
void removeNode (DirectedGraph *node, DirectedGraph *&firstNode);
int foundInArray (int value, int *arr, int rightBound);
currentNode = firstArc;
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId ≠ vertexId))
currentNode = currentNode->nextArc;
counter = 1;
adjacentVertex = new int [vertexLevel];
adjacentVertex[0] = currentNode->oneArc.inVertexId;
currentNode->oneArc.inVertexId = 0;
currentNode = currentNode->nextArc;
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId == vertexId)) {
adjacentVertex[counter] = currentNode->oneArc.inVertexId;
nodePointer = currentNode;
currentNode = currentNode->nextArc;
removeNode (nodePointer, firstArc);
counter++;
}
currentNode = firstArc;
while (currentNode ≠ NULL) {
currentId = currentNode->oneArc.outVertexId;
if (foundInArray (currentId, adjacentVertex, vertexLevel-1) ≠ NOT_FOUND) {
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId == currentId)) {
nodePointer = currentNode;
currentNode = currentNode->nextArc;
removeNode (nodePointer, firstArc);
}
continue;
}
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId == currentId))
currentNode = currentNode->nextArc;
}
currentNode = firstArc;
newVertexId = new int [NUM_VERTEX];
counter = 0;
while (currentNode ≠ NULL) {
newVertexId[counter] = currentNode->oneArc.outVertexId;
if (currentNode->oneArc.inVertexId ≠ 0) {
noOneBefore = true;
sidePointer = NULL;
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId == newVertexId[counter])) {
currentNode->oneArc.outVertexId = counter+1;
if (sidePointer ≠ NULL) {
removeNode (sidePointer, firstArc);
sidePointer = NULL;
}
if (foundInArray (currentNode->oneArc.inVertexId, adjacentVertex, vertexLevel-1) ≠ NOT_FOUND) {
if (noOneBefore) {
currentNode->oneArc.inVertexId = 0;
sidePointer = currentNode;
currentNode = currentNode->nextArc;
} else {
nodePointer = currentNode;
currentNode = currentNode->nextArc;
removeNode (nodePointer, firstArc);
}
continue;
}
if (noOneBefore)
noOneBefore = false;
currentNode = currentNode->nextArc;
}
} else {
currentNode->oneArc.outVertexId = counter+1;
currentNode = currentNode->nextArc;
}
counter++;
}
currentNode = firstArc;
while (currentNode ≠ NULL) {
if (currentNode->oneArc.inVertexId == 0) {
currentNode = currentNode->nextArc;
continue;
}
currentId = currentNode->oneArc.outVertexId;
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId == currentId)) {
currentNode->oneArc.inVertexId = foundInArray (currentNode->oneArc.inVertexId, newVertexId, NUM_VERTEX-1)+1;
currentNode = currentNode->nextArc;
}
}
}
void printNeiborhoodsList (DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = «») {
DirectedGraph *currentNode = firstNode;
int currentVertex;
if (!title.empty ())
*stream << title;
if (saveMode) {
while (currentNode ≠ NULL) {
currentVertex = currentNode->oneArc.outVertexId;
*stream << endl << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId == currentVertex)) {
*stream << ' ' << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
}
}
} else {
while (currentNode ≠ NULL) {
*stream << endl << (currentVertex = currentNode->oneArc.outVertexId) << «: «;
*stream << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
while ((currentNode ≠ NULL) && (currentNode->oneArc.outVertexId == currentVertex)) {
*stream << ' ' << currentNode->oneArc.inVertexId;
currentNode = currentNode->nextArc;
}
}
}
}
bool **completeAdjacencyMatrix (DirectedGraph *firstNode, int NUM_VERTEX) {
DirectedGraph *currentNode = firstNode;
int currentId, rowCounter, colCounter;
bool **adjacencyMatrix = new bool* [NUM_VERTEX];
for (rowCounter = 0; rowCounter < NUM_VERTEX; rowCounter++) {
adjacencyMatrix[rowCounter] = new bool [NUM_VERTEX];
for (colCounter = 0; colCounter < NUM_VERTEX; colCounter++)
adjacencyMatrix[rowCounter][colCounter] = false;
}
currentNode = firstNode;
while (currentNode ≠ NULL) {
if (currentNode->oneArc.inVertexId ≠ 0)
adjacencyMatrix[currentNode->oneArc.outVertexId-1][currentNode->oneArc.inVertexId-1] = true;
currentNode = currentNode->nextArc;
}
return adjacencyMatrix;
}
void printMatrix (bool **matrix, int dimension, ostream *stream, string title = «») {
int rowCounter, colCounter;
if (!title.empty ())
*stream << title;
for (rowCounter = 0; rowCounter < dimension; rowCounter++) {
*stream << endl << ' ' << matrix[rowCounter][0];
for (colCounter = 1; colCounter < dimension; colCounter++) {
*stream << ' ' << matrix[rowCounter][colCounter];
}
}
}
void clearMatrix (bool **matrix, int dimention) {
for (int counter = 0; counter < dimention; counter++)
delete [] matrix[counter];
delete [] matrix;
}