ืืขืื ืึทืืขืืขื.
ืืื ืืขื ืืึธื, ืืื ืืึทืฉืืึธืกื ืฆื ืจืฉืืื ืื ืืืืคึผื ืืึทืื ืกืืจืึทืงืืฉืขืจื ืืขื ืืฆื ืฆื ืงืจืึธื ืืจืึทืคืก ืืื ืงืึธืืคึผืืืืขืจ ืืืืกื ืฉืึทืคึฟื, ืืื ืืื ืืืขื ืืืื ืจืขืื ืืืขืื ืึท ืคึผืึธืจ ืืขืจ ืึทืืึท ืกืืจืึทืงืืฉืขืจื ืืืึธืก ืขืคืขืก "ืงืจืืกืืึทืืืืืขื" ืคึฟืึทืจ ืืืจ.
ืึทืืื, ืืึธืื ืก ืึธื ืืืืื. ืืืขืจ ื ืืฉื ืคืื ืื ืึธื ืืืื - ืืื ืืจืึทืืื ืืืจ ืึทืืข ืืืืกื ืฉืืื ืืืึธืก ืึท ืืจืึทืคืืง ืืื ืืื ืืืึธืก ืืื ืืขื ืขื (ืืืจืขืงืืขื, ืึทื ืจืขืงืืื, ืืืืืืื, ืึทื ืืืึธืืืขื, ืืื ืึธืืขืจ ืึธื ืงืืืคื ืขืืืฉืึทื ืืื ืืืคึผืก).
ืึทืืื, ืืึธืื ืก ืืืื. ืืืึธืก ืึธืคึผืฆืืขืก ืคึฟืึทืจ ืืึทืื ืกืืจืึทืงืืฉืขืจื ืคึฟืึทืจ "ืืจืึทืฃ ืกืืึธืจืืืืฉ" ืืืจ ืืึธืื?
1. ืืึทืืจืืฅ ืืึทืื ืกืืจืึทืงืืฉืขืจื
1.1 ืฉืืืื ืืฉ ืืึทืืจืืฅ. ืื ืฉืืืื ืืฉ ืืึทืืจืืฅ ืืื ืึท ืืึทืืจืืฅ ืืื ืื ืจืืืขืจื ืืื ืืืึทื ืืขืืื ืื ืฉืืืืขื ืฆื ืื ื ืืืขืจื ืคืื ืื ืืืขืจืืืงืึทืื ืคืื ืื ืืจืึทืคืืง, ืืื ืื ืืืขืจื ืคืื ืืขืืขืจ ืคืื ืืืึทื ืขืืขืืขื ืื ืึท (ื, ืืืฉ) ืืื ืืืฉืืืกื ืืืจื ืืขื ืืืึทืืืึทื ืึธืืขืจ ืึทืืืขืง ืคืื ืขืืืฉืึทื ืฆืืืืฉื ืืืขืจืืืกืขืก i ืืื j (ืขืก ืืื ืงืืึธืจ ืึทื ืคึฟืึทืจ ืึท ืึทื ืจืขืงืืื ืืจืึทืคืืง ืึทืืึท ืึท ืืึทืืจืืฅ ืืืขื ืืืื ืกืึทืืขืืจืืงืึทื, ืึธืืขืจ ืืืจ ืงืขื ืขื ืฉืืืืขื ืึทื ืืืจ ืงืจืึธื ืึทืืข ืืืึทืืืขืก ืืืืื ืืืืื ืื ืืืืคึผื ืืืึทืืึธื ืึทื). ืคึฟืึทืจ ืึทื ืืืึธืืืข ืืจืึทืคืก, ืึท (ื, ืืืฉ) ืงืขื ืขื ืืืื ืืึทืฉืืืื ืืืจื ืื ื ืืืขืจ ืคืื ืขืืืฉืึทื ืคืื i ืฆื ืืืฉ (ืืืื ืขืก ืืื ื ืื ืึทืืึท ืืจืขื, ืืขืืึธืื ืึท (ื, ืืืฉ) = 0), ืืื ืคึฟืึทืจ ืืืืืืื ืืจืึทืคืก, ืืืื ืืืจื ืื ืืืึธื (ืืึทื ืฅ ืืืึธื) ืคืื ืื ืืขืจืืื ื ืขืืืฉืึทื.
1.2 ืื ืกืืืึทื ืก ืืึทืืจืืฅ. ืืื ืืขื ืคืึทื, ืืื ืืืขืจ ืืจืึทืคืืง ืืื ืืืื ืกืืึธืจื ืืื ืึท ืืืฉ ืืื ืืืึธืก, ืืื ืึท ืืขืจืฉื, ืื ืจืืืขืจื ื ืืืขืจื ืฉืืืืขื ืฆื ืื ื ืืืขืจื ืคืื ืืืึทื ืืืขืจืืืกืขืก, ืืื ืื ืืืึทื ื ืืืขืจื ืฉืืืืขื ืฆื ืคืึทืจ-ื ืืืขืจื ืขืืืฉืึทื. ืืืื ืึท ืืืขืจืืขืงืก ืืื ืึท ืืจืขื ืืขื ืขื ืืื ืฆืืืขื ื ืฆื ืืขืืขืจ ืื ืืขืจืขืจ, โโืึท ื ืื-ื ืื ืืืขืจื ืืื ืืขืฉืจืืื ืืื ืื ืงืึธืจืึทืกืคึผืึทื ืืื ื ืฆืขื (ืคึฟืึทืจ ืึทื ืจืขืงืืื ืืจืึทืคืก, 1 ืืื ืืขืฉืจืืื ืืืื ืื ืืืขืจืืขืงืก ืืื ืืจืขื ืืขื ืขื ืืื ืฆืืืขื ื, ืคึฟืึทืจ ืึธืจืืขื ืืื ืืจืึทืคืก - "1" ืืืื ืื ืืจืขื "ืขืืืืฅ" ืคืื ืื ืืืขืจืืขืงืก ืืื "-1" ืืืื ืขืก "ืึทืจืืึทื ืืขืจืขืื ื" ืืื ืขืก (ืขืก ืืื ืืจืื ื ืืขื ืื ืฆื ืืขืืขื ืงืขื, ืืืืึทื ืื "ืืื ืืก" ืฆืืืื ืืืื ืืืื ื ืฆื ืืืื "ืึทืจืืึทื ืืขืจืขืื ื" ืืื ืื ื ืืืขืจ "-1")). ืคึฟืึทืจ ืืืืืืื ืืจืึทืคืก, ืึทื ืฉืืึธื ืคืื 1 ืืื -1, ืืืจ ืงืขื ืขื ืกืคึผืขืฆืืคืืฆืืจื ืื ืืึทื ืฅ ืืืึธื ืคืื ืื ืืจืขื.
2. ืขื ืืืขืจืึทืืืึธื ืืึทืื ืกืืจืึทืงืืฉืขืจื
2.1 ืจืฉืืื ืคืื ืึทืืืืฉืึทืืืฉืึทื ืก. ื ื, ืึทืืฅ ืืืื ื ืฆื ืืืื ืคึผืฉืื ืืึธ. ืืขืืขืจ ืืืขืจืืขืงืก ืคืื ืื ืืจืึทืคืืง ืงืขื ืขื, ืืื ืึทืืืขืืืื, ืืืื ืคืืจืืื ืื ืืื ืงืืื ืื ืืืขืจืืืฉืึทื ืกืืจืืงืืืจ (ืจืฉืืื, ืืืขืงืืึธืจ, ืืขื ืืข, ...), ืืืึธืก ืืืขื ืงืจืึธื ืื ื ืืืขืจื ืคืื ืึทืืข ืืืขืจืืืกืขืก ืฉืืืื ืืฉ ืฆื ืื ืืขืืขืื ืืืื ืขืจ. ืคึฟืึทืจ ืืืจืขืงืืขื ืืจืึทืคืก, ืืืจ ืืืขืื ืืืืื ืฆื ืึทืืึท ืึท ืจืฉืืื ืืืืื ืื ืืืขืจืืืงืึทืื ืฆื ืืืึธืก ืขืก ืืื ืึท "ืืืจืขืงืืขื" ืืจืขื ืคืื ืึท ืฉืืจืื ืืืขืจืืขืงืก. ืคึฟืึทืจ ืืืืืืื ืืจืึทืคืก ืื ืืืคึผืืึทืืขื ืืืืฉืึทื ืืืขื ืืืื ืืขืจ ืงืึธืืคึผืืืฆืืจื.
2.2 ืจืฉืืื ืคืื ืจืืืก. ืืึทื ืฅ ืึท ืคืึธืืงืก ืืึทืื ืกืืจืืงืืืจ. ืื ืจืฉืืื ืคืื ืขืืืฉืึทื, ืืื ืงืึทืคึผืืืึทื ืึธืืืืืึธืืกื ืขืกืก ืืขืจืฆืืืื ืืื ืื, ืืื ืคืืงืืืฉ ืึท ืจืฉืืื ืคืื ืขืืืฉืึทื ืคืื ืื ืืจืึทืคืืง, ืืขืืขืจ ืคืื ืืืึธืก ืืื ืกืคึผืขืกืืคืืขื ืืืจื ืื ืึธื ืืืื ืืืขืจืืขืงืก, ืื ืกืึธืฃ ืืืขืจืืขืงืก (ืคึฟืึทืจ ืึทื ืจืขืงืืื ืืจืึทืคืก ืื ืกืืจ ืืื ื ืืฉื ืืืืืืืง ืืึธ, ืืึธืืฉ ืคึฟืึทืจ ืืื ืึทืคืึทืงืืืฉืึทื ืืืจ ืงืขื ืขื ื ืืฆื ืคืึทืจืฉืืื ืึผืืืื, ืืืฉื, ืกืคึผืขืฆืืคืืฆืืจื ืื ืืืขืจืืืกืขืก ืืื ืกืืจ ืื ืงืจืืกืื ื) ืืื ืืืึธื (ืืืืื ืคึฟืึทืจ ืืืืืืื ืืจืึทืคืก).
ืืืจ ืงืขื ื ืืขื ืื ืืึทืืจืืฅ ืจืฉืืืืช ืืืกืืขื ืืืืื ืืื ืืขืจ ืืขืืึทื (ืืื ืืื ืืืืืกืืจืืฆืืขืก), ืืืฉื, .
2.3 ืึทืืืืฉืึทืืืฉืึทื ืกื ืืขื ืืข. ื ืื ืื ืืขืจืกื ืคึผืจืึธืกื ืกืืจืืงืืืจ. ืืื ืืืื ืืึทืจืฅ, ืขืก ืืื ืึท ืคืึธืจืขื ืคืื "ืคึผืึทืงืื ื" ืฉืืืื ืืฉ ืจืฉืืืืช ืืื ืืืื ืื ืืืขืจืืืฉืึทื ืกืืจืืงืืืจ (ืืขื ืืข, ืืืขืงืืึธืจ). ืื ืขืจืฉืืข n (ืืืื ืื ื ืืืขืจ ืคืื ืืืขืจืืืงืก ืคืื ืื ืืจืึทืคืืง) ืขืืขืืขื ืื ืคืื ืึทืืึท ืึท ืืขื ืืข ืึทื ืืืึทืืื ืื ืึธื ืืืื ืื ืืืกืื ืคืื ืื ืืขืืืข ืืขื ืืข, ืกืืึทืจืืื ื ืคืื ืืืึธืก ืึทืืข ืืืขืจืืืงืก ืฉืืืื ืืฉ ืฆื ืืขืจ ืืขืืขืื ืืืื ืขืจ ืืขื ืขื ืืขืฉืจืืื ืืื ืึท ืจืืืขืจื.
ืืึธ ืืื ืืขืคึฟืื ืขื ืื ืืขืจืกื ืคืึทืจืฉืืืืืง (ืคึฟืึทืจ ืืื) ืืขืจืงืืขืจืื ื:
3. Adjacency Vector ืืื Associative Adjacency Array
ืขืก ืคืืจืงืขืจื ืืืืก ืึทื ืืขืจ ืืืืจ ืคืื ืื ืฉืืจืืช, ื ืืฉื ืึท ืคืึทืืืึทื ืคึผืจืึธืืจืึทืืืกื, ืึธืืขืจ ืคึผืืจืืึทืืืงืื ืืขืื ืืื ืืจืึทืคืก, ืจืืึฟ ืึธืคื ืืขืื ืืื ืจืฉืืืืช ืคืื ืขืืืฉืึทื. ืืึทืงืข, ืขืก ืืื ืืึทืงืืืขื ืืืื ืื ืืจืึทืคืืง ืืื ืงืืืคื ืืืคึผืก ืืื ืขืืืฉืึทื. ืืื ืึทืืื, ืืื ืึทื ืืืืืงืืื ื ืคืื ืื ืงืืึทืกืืฉ ืจืฉืืืืช ืคืื ืขืืืฉืึทื, ืืื ืคืึธืจืฉืืึธืื ืฆื ืืึทืฆืึธืื ืืคืืขืจืงืืึทืืงืืื ืฆื ืืืืขืจ "ืึทื ืืืืืงืืื ื / ืฆืืืืึทื / ืืึธืืืคืืงืึทืืืึธื / ืืืืืืืฉืึทื", ื ืืืืื: ืื ืึทืืืฉืึทืกืึทื ืก ืืืขืงืืึธืจ ืืื ืื ืึทืกืกืึธืกืืึทืืืืืข ืึทืืืฉืึทืกืึทื ืกื ืืขื ืืข.
3.1 ืึทืืืืฉืึทื ืกื ืืืขืงืืึธืจ
ืคืึทื (ืึท1): ืึทื ืืืึธืืืขื ืืจืึทืคืืง
ืืืจ ืืืขืื ืจืืคื ืึทื ืึทืืืฉืึทืกืขื ืกื ืืืขืงืืึธืจ ืคึฟืึทืจ ืึท ืึทื ืืืึธืืืขื ืืจืึทืคืืง ืึท ืึธืจืืขืจื ืืึทื ื ืคืื ืึทื ืึทืคึฟืืื ื ืืืขืจ ืคืื ืื ืืึทืืืฉืขืจื (ืึท[2i], a[2i+1],..., ืืื i ืืื ืืขืฆืืืื c 0), ืืื ืืืึธืก ืืขืืขืจ ืคึผืึธืจ ืคืื ื ืืืขืจื ืืื a[2i], ืึท[2i+1] ืกืคึผืขืฆืืคืืฆืืจื ืึท ืืจืืฃ ืืจืขื ืฆืืืืฉื ืื ืืืขืจืืืงืก ืึท[2i] ืืื ืึท[2i+1], ืจืืกืคึผืขืงืืืืืื.
ืื ืจืขืงืึธืจืืื ื ืคึฟืึธืจืืึทื ืึผืืื ืงืืื ืืื ืคึฟืึธืจืืึทืฆืืข ืืืขืื ืฆื ืื ืืจืึทืคืืง ืืื ืืืจืขืงืืขื (ืืืืืข ืึธืคึผืฆืืขืก ืืขื ืขื ืืขืืืขื). ืืืขื ืืืจ ื ืืฆื ืื ืืืืจืึทืฃ ืคึฟืึธืจืืึทื, ืื ืืจืขื ืืื ืืขืจืขืื ื ืืื ืืืจืขืงืืขื ืคึฟืื ืึท [2i] ืฆื ืึท [2i + 1]. ืืึธ ืืื ืืื ืื: ืคึฟืึทืจ ืึทื ืจืขืงืืื ืืจืึทืคืก, ืืืื ื ืืืืืง, ืจืขืงืืืืจืขืืขื ืฅ ืคึฟืึทืจ ืื ืกืืจ ืคืื ืจืขืงืึธืจืืื ื ืืืขืจืืืกืขืก ืงืขื ืขื ืืืื ืืขืืืขื ืื (ืืืฉื ืึทื ืืขืจ ืืืขืจืืขืงืก ืืื ืืขืจ ื ืืืขืจืืงืขืจ ืืืขืจื ืคืื ืื ื ืืืขืจ ืึทืกืืื ื ืฆื ืขืก ืงืืื ืขืจืฉืืขืจ).
ืืื C ++, ืขืก ืืื ืงืขืืืึทืืง ืฆื ืกืคึผืขืฆืืคืืฆืืจื ืึท ืึทืืืฉืึทืกืึทื ืก ืืืขืงืืึธืจ ื ืืฆื ืกืื:: ืืืขืงืืึธืจ, ืืขืจืคืืจ ืื ื ืึธืืขื ืคืื ืืขื ืืึทืื ืกืืจืืงืืืจ.
ืคืึทื (ืึท2): ืึทื ืืืึธืืขื ืืจืึทืคืืง, ืืจืขื ืืืืืฅ ืืขื ืขื ืืึทื ืฅ ื ืืืขืจ
ืืืื ืึทื ืึทืืึทืืืฉื ืืื ืคืึทื (ืึท1), ืืืจ ืจืืคื ืื ืึทืืืฉืึทืกืึทื ืก ืืืขืงืืึธืจ ืคึฟืึทืจ ืึท ืืืืืืื ืืจืึทืคืืง ืืื ืื ืืึทืืืฉืขืจ ืืจืขื ืืืืืฅ ืึท ืึธืจืืขืจื ืืึทื ื (ืืื ืึทืืืฉ ืืขื ืืข) ืคืื ื ืืืขืจื (ืึท[3i], a[3i+1], a[3i+2], ..., ืืื i ืืื ืืขืฆืืืื c 0), ืืื ืืขืืขืจ "ืืจืืคึผืืขื" ืคืื ื ืืืขืจื a[3i], a[3i+1], a[3i+2] ืกืคึผืขืฆืืคืืฆืืจื ืึท ืืจืขื ืคืื ืื ืืจืึทืคืืง ืฆืืืืฉื ืืืขืจืืืกืขืก ืืขืฆืืืื ืึท[3i] ืืื ืึท[3i+1], ืจืืกืคึผืขืงืืืืืื, ืืื ืื ืืืขืจื ืึท [3i+2] ืืื ืื ืืืึธื ืคืื ืืขื ืืจืขื. ืึทืืึท ืึท ืืจืึทืคืืง ืงืขื ืขื ืืืื ืืืื ืืืจืขืงืืขื ืึธืืขืจ ื ืืฉื.
ืคืึทื (ื): ืื ืืืขืืืืืขื ืืจืึทืคืืง, ื ืื-ืื ืืึทืืืฉืขืจ ืืจืขื ืืืืืฅ
ืืื ื ืขืก ืืื ืืืืืขืืืขื ืฆื ืงืจืึธื ืืขืืขืจืึทืืืฉืื ืืึทืก ืขืืขืืขื ืื ืืื ืืืื ืืขื ืืข (ืืืขืงืืึธืจ), ืคึฟืึทืจ ืืืึทืฉืคึผืื, ืื ืคืืืืขื ืืข ืืืคึผืืึทืืขื ืืืืฉืึทื ืืื ืืขืืืขื. ืื ืืจืึทืคืืง ืืื ืกืืึธืจื ืืื ืึท ืคึผืึธืจ ืคืื ืืืขืงืืึธืจืก, ืืื ืืืึธืก ืืขืจ ืขืจืฉืืขืจ ืืืขืงืืึธืจ ืืื ืื ืึทืืืฉืึทืกืึทื ืก ืืืขืงืืึธืจ ืคืื ืื ืืจืึทืคืืง ืึธื ืกืคึผืขืฆืืคืืฆืืจื ืื ืืืืืฅ, ืืื ืื ืจืืข ืืืขืงืืึธืจ ืึผืืื ืื ืงืึธืจืึทืกืคึผืึทื ืืื ื ืืืืืฅ (ืืขืืืขื ืืืคึผืืึทืืขื ืืืืฉืึทื ืคึฟืึทืจ C ++: std::pair ). ืืืื, ืคึฟืึทืจ ืึท ืืจืขื ืืืคืืื ื ืืืจื ืึท ืคึผืึธืจ ืคืื ืืืขืจืืืกืขืก ืืื ืืขืจ ืื ืืขืงืกืื 2i, 2i+1 ืคืื ืืขืจ ืขืจืฉืืขืจ ืืืขืงืืึธืจ, ืื ืืืึธื ืืืขื ืืืื ืืืืึทื ืฆื ืื ืขืืขืืขื ื ืืื ืืขืจ ืืื ืืขืงืก i ืคืื ืื ืจืืข ืืืขืงืืึธืจ.
ื ื, ืคืืจืืืืก ืืื ืืึธืก ื ืืืืืง?
ื ื, ืืขืจ ืืืืจ ืคืื ืื ืฉืืจืืช ืืขืคึฟืื ืขื ืขืก ืืึทื ืฅ ื ืืฆืืง ืคึฟืึทืจ ืกืึทืืืืื ื ืึท ื ืืืขืจ ืคืื ืคึผืจืึธืืืขืืก. ื ื, ืคึฟืื ืึท ืคืึธืจืืึทื ืคืื ื ืคืื ืืืื ืื ื, ืขืก ืืืขื ืืืื ืื ืคืืืืขื ืืข ืึทืืืืึทื ืืืืืฉืื:
- ืื ืฉืืืื ืืฉ ืืืขืงืืึธืจ, ืืื ืงืืื ืื ืืขืจืข "ืื ืืืขืจืึทืืืื" ืกืืจืืงืืืจ, ืืื ืืึทื ืฅ ืกืึธืืื, ื ืขืื ืืืืื ืืงืขืจ ืืึผืจืื ืืื ืื ืฉืืืื ืืฉ ืืึทืืจืืฅ (ืคึฟืึทืจ ืฉืืืขืจ ืืจืึทืคืก), ืืื ืืื ืืขืคืืขืจืขื ืืจืื ื ืฆื ืื ืกืืจืืืขื ื.
- ืื ืืืขืจืืืกืขืก ืคืื ืื ืืจืึทืคืืง, ืืื ืคึผืจืื ืฆืืคึผ, ืงืขื ืขื ืืืื ืืืื ืื ืืขืฆืืืื ื ืืื ื ืขืืึทืืืื ื ืืืขืจื. ืืืึธืก ืืืื ืึทืืึท ืึท "ืคึผืขืจืืืขืจืกืืึธื" ืืื ืืืจืฃ?
- ืืจืึทืคืก ืงืขื ืขื ืึทื ืืืึทืืื ืงืืืคื ืขืืืฉืึทื ืืื ืงืืืคื ืืืคึผืก, ืืื ืคืึทืจืฉืืืขื ืข ืืืืืฅ (positive, ื ืขืืึทืืืื, ืืคืืื ื ืื). ืขืก ืืขื ืขื ืงืืื ืจืืกืืจืืงืฉืึทื ื ืืึธ.
- ืืืจ ืงืขื ื ืืืื ืืึทืฉืืืืขื ืคืึทืจืฉืืืขื ืข ืคึผืจืึธืคึผืขืจืืืขืก ืฆื ืขืืืฉืึทื - ืึธืืขืจ ืคึฟืึทืจ ืืขืจ ืืืขืื ืืขื, ืืขื ืึธืคึผืืืืืื ื 4.
ืึธืืขืจ, ืขืก ืืืื ืืืื ืึทืืืืืึทื ืึทื ืื "ืจืฉืืื" ืืื ื ืืฉื ืืืื ืขื ืฉื ืขื ืึทืงืกืขืก ืฆื ืื ืืจืขื. ืืื ืืึธ ืงืืื ืฆื ืจืึทืืขืืืขื ืื ืึทืกืกืึธืกืืึทืืืืืข ืึทืืืฉืึทืกืขื ืกื ืืขื ืืข, ืืืึธืก ืืื ืืืกืงืึทืกื ืืื ืื.
3.2 ืึทืกืกืึธืกืืึทืืืืืข ืึทืืืฉืึทืกืึทื ืกื ืืขื ืืข
ืึทืืื, ืืืื ืึทืงืกืขืก ืฆื ืึท ืกืคึผืขืฆืืคืืฉ ืืจืขื, ืืืึทื ืืืึธื ืืื ืื ืืขืจืข ืคึผืจืึธืคึผืขืจืืืขืก ืืขื ืขื ืงืจืืืืฉ ืคึฟืึทืจ ืืื ืื, ืืื ืืึผืจืื ืจืขืงืืืืจืขืืขื ืฅ ืืึธื ื ืื ืืึธืื ืืื ืื ืฆื ื ืืฆื ืื ืึทืืืฉืึทืกืึทื ืกื ืืึทืืจืืฅ, ืืึธืื ืืื ืื ืืจืึทืืื ืืืขืื ืืื ืืืจ ืงืขื ืขื ืืืืฉื ืื ืึทืืืฉืึทืกืึทื ืก ืืืขืงืืึธืจ ืฆื ืกืึธืืืืข ืืขื ืคึผืจืึธืืืขื. ืึทืืื, ืืขืจ ืฉืืืกื ืืื ืึท ืืจืขื ืคืื ืื ืืจืึทืคืืง, ืืืึธืก ืงืขื ืขื ืืืื ืกืคึผืขืกืืคืืขื ืืื ืึท ืึธืจืืขืจื ืคึผืึธืจ ืคืื ืื ืืึทืืืฉืขืจื. ืืื ืืืื ืงืืงื ืืืก ืืืืก? ืืื ืขืก ื ืืฉื ืึท ืฉืืืกื ืืื ืึท ืึทืกืกืึธืกืืึทืืืืืข ืืขื ืืข? ืืื, ืืืื ืึทืืื, ืคืืจืืืืก ืืึธื ืืืจ ื ืืฉื ืื ืกืืจืืืขื ื ืขืก? ืืื ืืื ืื ืืึธืื ืึท ืึทืกืกืึธืกืืึทืืืืืข ืืขื ืืข ืืื ืืขืืขืจ ืฉืืืกื - ืึท ืึธืจืืขืจื ืคึผืึธืจ ืคืื ืื ืืึทืืืฉืขืจื - ืืืขื ืืืื ืคืืจืืื ืื ืืื ืึท ืืืขืจื - ืึทื ืื ืืึทืืืฉืขืจ ืึธืืขืจ ืึท ืคืึทืงืืืฉ ื ืืืขืจ ืืืึธืก ืกืคึผืขืฆืืคืืฆืืจื ืื ืืืึธื ืคืื ืื ืืจืขื. ืืื C ++, ืขืก ืืื ืงืขืืืึทืืง ืฆื ืื ืกืืจืืืขื ื ืืขื ืกืืจืืงืืืจ ืืืืืจื ืืืืฃ ืื std :: ืืึทืคึผ ืงืึทื ืืืื ืขืจ (ืกืื :: ืืึทืคึผ , int> ืึธืืขืจ std::map , ืืึธืคึผื>), ืึธืืขืจ std :: ืืืืืืืึทืคึผ ืืืื ืงืืืคื ืขืืืฉืึทื ืืขื ืขื ืืขืจืืืึทืจื. ื ื, ืืืจ ืืึธืื ืึท ืกืืจืืงืืืจ ืคึฟืึทืจ ืกืืึธืจืื ื ืืจืึทืคืก ืืืึธืก ื ืขืื ืืืืื ืืงืขืจ ืืึผืจืื ืืื "ืืึทืืจืืฅ" ืกืืจืึทืงืืฉืขืจื, ืงืขื ืขื ืืขืคืื ืืจื ืืจืึทืคืก ืืื ืงืืืคื ืืืคึผืก ืืื ืขืืืฉืึทื, ืืื ืืื ื ืืฉื ืืคืืื ืืึธืื ืฉืืจืขื ื ืจืขืงืืืืจืขืืขื ืฅ ืคึฟืึทืจ ืื ื ืื-ื ืขืืึทืืืืืืื ืคืื ืืืขืจืืขืงืก ื ืืืขืจื (ืืื ืืึธื ื ืื ืืืืกื ืืืขืจ ืืึทืจืฃ ืืึธืก, ืึธืืขืจ ื ืึธื).
4. ืืึทืืึท ืกืืจืึทืงืืฉืขืจื ืืขื ืขื ืคืื, ืึธืืขืจ ืขืคึผืขืก ืืื ืคืขืื ืืืง
ืืื ืืึธืก ืืื ืืืช: ืืืขื ืกืึธืืืืข ืึท ื ืืืขืจ ืคืื ืคึผืจืึธืืืขืืก, ืืืจ ืงืขื ืืึทืจืคึฟื ืฆื ืืึทืฉืืืืขื ืขืืืขืืข ืงืขืจืึทืงืืขืจืืกืืืงืก ืฆื ืื ืขืืืฉืึทื ืคืื ืื ืืจืึทืคืืง ืืื, ืึทืงืึธืจืืื ืืื, ืงืจืึธื ืืื. ืืืื ืขืก ืืื ืืขืืืขื ืฆื ืึทื ืึทืืืืืืืึทืกืื ืจืขืืืฆืืจื ืื ืคึฟืขืึดืงืืืื ืฆื ืื ืืึทืืืฉืขืจื, ืขืก ืืื ืืขืืืขื ืฆื ืงืจืึธื ืึทืืึท "ืืจืึทืคืก ืืื ื ืึธื ืคึฟืขืึดืงืืืื" ื ืืฆื ืขืงืกืืขื ืืขื ืืืขืจืกืืขืก ืคืื ืื ืึทืืืืฉืึทื ืกื ืืืขืงืืึธืจ ืืื ืึทืกืกืึธืกืืึทืืืืืข ืึทืืืฉืึทืกืึทื ืกื ืืขื ืืข.
ืึทืืื, ืืึธืื ืืื ืื ืืึธืื ืึทื ืึทื ืืืึธืืขื ืืจืึทืคืืง, ืคึฟืึทืจ ืืขืืขืจ ืืจืขื ืคืื ืืืึธืก ืขืก ืืื ื ืืืืืง ืฆื ืงืจืึธื, ืืืฉื, 2 ื ืึธื ืคึฟืขืึดืงืืืื ืกืคึผืขืกืืคืืขื ืืืจื ืื ืืึทืืืฉืขืจื. ืืื ืืขื ืคืึทื, ืขืก ืืื ืืขืืืขื ืฆื ืืขืคืื ืืจื ืืืึทื ืึทืืืฉืึทืกืึทื ืก ืืืขืงืืึธืจ ืืื ืึท ืึธืจืืขืจื ืืึทื ื ื ืื ืคืื "ืคึผืขืจื", ืึธืืขืจ ืคืื "ืงืืืึทืจืืขืฅ" ืคืื ืื ืืึทืืืฉืขืจื (ืึท[2i], a[2i+1], a[2i+2], ืึท [2i+3]โฆ) , ืืื ืึท[2i+2] ืืื ืึท[2i+3] ืืืขื ืืึทืฉืืืกื ืื ืงืขืจืึทืงืืขืจืืกืืืงืก ืคืื ืื ืงืึธืจืึทืกืคึผืึทื ืืื ื ืืจืขื. ืคึฟืึทืจ ืึท ืืจืึทืคืืง ืืื ืื ืืึทืืืฉืขืจ ืืืืืฅ ืคืื ืขืืืฉืึทื, ืื ืกืืจ ืืื ืืืื ืขื ืืขื (ืืขืจ ืืืืื ืืืืืง ืืืขื ืืืื ืึทื ืื ืึทืืจืืืืืฅ ืืืขื ื ืึธืืคืึธืืื ืื ืืืึธื ืคืื ืื ืืจืขื ืืื ืืืขื ืืืื ืกืคึผืขืกืืคืืขื ืืืจื ืื ืขืืขืืขื ืื ืึท[2i+3] ืืื ืึท[2i+4] , ืืื ืืขืจ ืืจืขื ืืื ืืืขื ืืืื ืกืคึผืขืกืืคืืขื ื ืื 4, ืึธืืขืจ 5 ืึธืจืืขืจื ื ืืืขืจื). ืืื ืคึฟืึทืจ ืึท ืืจืึทืคืืง ืืื ื ืื-ืื ืืึทืืืฉืขืจ ืืจืขื ืืืืืฅ, ืื ืคึฟืขืึดืงืืืื ืงืขื ืขื ืืืื ืืขืฉืจืืื ืืื ืืืื ืึทื ืืืึธืืขื ืงืึธืืคึผืึธื ืขื ื.
ืืืขื ื ืืฆื ืึท ืึทืกืกืึธืกืืึทืืืืืข ืึทืืืฉืึทืกืึทื ืก ืืขื ืืข ืคึฟืึทืจ ืืจืึทืคืก ืืื ืื ืืึทืืืฉืขืจ ืืจืขื ืืืืืฅ, ืขืก ืืื ืืขืืืขื ืฆื ืกืคึผืขืฆืืคืืฆืืจื ืืื ืึท ืืืขืจื ื ืืฉื ืึท ืืืื ื ืืืขืจ, ืึธืืขืจ ืึท ืืขื ืืข (ืืืขืงืืึธืจ) ืคืื ื ืืืขืจื ืืืึธืก ืกืคึผืขืฆืืคืืฆืืจื, ืืื ืึทืืืฉืึทื ืฆื ืื ืืืึธื ืคืื ืึท ืืจืขื, ืึทืืข ืืืึทื ืื ืืขืจืข ื ืืืืืง ืืืื ืจืืืืื ืืขื. ืืื ืืขืจ ืืขืืืืงืขืจ ืฆืืื, ืึท ืื ืงืึทื ืืืื ืืึทื ืก ืคึฟืึทืจ ืื ืคืึทื ืคืื ื ืื-ืื ืืขืจืืขืจ ืืืืืฅ ืืืขื ืืืื ืื ื ืืื ืฆื ืกืคึผืขืฆืืคืืฆืืจื ืึท ืฆืืืื ืืื ืึท ืคืืึธืืืื ื ืคืื ื ื ืืืขืจ (ืืึธ, ืืึธืก ืืื ืึทื ืื ืงืึทื ืืืื ืืึทื ืก, ืึธืืขืจ ืืืื ืขืก ืืขื ืขื ื ืืฉื ืึทืืื ืคืืืข ืึทืืึท ืืืืื ืืขืจ, ืืื ืืืื ืืืจ ืืึธื ื ืื ื ืืฉื ืฉืืขืื ืืื ืฆื "ืืจืืงื" ืืึธืคึผื, ืขืก ืงืขื ืืืื ืืึธืจื ืืฉื). ืืขื ืืืื ืึทื ืืื C ++ ืขืงืกืืขื ืืขื ืึทืกืกืึธืกืืึทืืืืืข ืึทืืืฉืึทืกืึทื ืกื ืขืจืืื ืงืขื ืขื ืืืื ืืืคืืื ื ืืื ืืืื: std::map , std::vector> ืึธืืขืจ std::map , std::vector, ืืื ืืืึธืก ืืขืจ ืขืจืฉืืขืจ ืืืขืจื ืืื ืื "ืฉืืืกื-ืืืขืจื-ืืืขืงืืึธืจ" ืืืขื ืืืื ืื ืืืึธื ืคืื ืื ืืจืขื, ืืื ืืขืืึธืื ืื ื ืืืขืจืืงืึทื ืืึทืฆืืืืขื ืื ื ืคืื ืืืึทื ืงืขืจืึทืงืืขืจืืกืืืงืก ืืขื ืขื ืืืื.
ืืืืขืจืึทืืืจ:
ืืืขืื ืืจืึทืคืก ืืื ืึทืืืขืจืืืึทืื ืืื ืึทืืืขืืืื:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. ืึทืืืขืจืืืึทืื: ืงืึทื ืกืืจืึทืงืฉืึทื ืืื ืึทื ืึทืืืกืืก, 2 ืึทืืืฉืึทื: ืืจืึทื ืก. ืคืื ืขื ืืืืฉ - ื.: ืืืืืืืึทืืก ืคึผืืืืืฉืื ื ืืืื, 2011.
2. ืืจืจื ืคืจืึทื ืง. ืืจืืฃ ืืขืืจืืข. ื.: ืืืจ, 1973.
ืืขืจ ืืืืจ 'ืก ืืึทืจืืื ืืืขืื ืื ืืขืืืข ืืืขืงืืึธืจ ืืื ืึทืกืกืึธืกืืึทืืืืืข ืืขื ืืข ืคืื โโโโืึทืืืฉืึทืกืึทื ืกืื:
3. ืืฉืขืจื ืึธืืืึธืื ืก.ืึท. ืึทืืืฉืึทืกืขื ืกื ืืืขืงืืึธืจ ืืื ืึทืกืกืึธืกืืึทืืืืืข ืึทืืืฉืึทืกืึทื ืกื ืืขื ืืข ืืื ืืืขืื ืฆื ืคืึธืจืฉืืขืื ืืื ืงืจืึธื ืืจืึทืคืก / ืกืึท ืืฉืขืจื ืึธืืึธืื. ืึทืืืฉืึทืกืึทื ืก ืืืขืงืืึธืจ ืืื ืึทืืืืฉืึทืกืกืึทื ืกื ืืึทืคึผืข ืืื ืืึทืื ืกืืจืึทืงืืฉืขืจื ืฆื ืคืึธืจืฉืืขืื ืึท ืืจืึทืคืืง // ืืึทืืืื ื ืคืื ืึทืจืืืงืืขื ืคืื ืื ืื ืืขืจื ืึทืืืึธื ืึทื ืืืืกื ืฉืืคืืืขืืข ืืื ืคึผืจืึทืงืืืฉ ืงืึธื ืคึฟืขืจืขื ืฅ "ืคึผืจืึธืืืขืืขื ืคืื ืืืคึผืืึทืืขื ืื ื ืื ืจืขืืืืืึทืื ืคืื ืื ืึทืืืืืืืื ืืืืืขืืึทืคึผืืึทื ืฅ ืืื ืืืขืื ืฆื ืกืึธืืืืข ืืื" (Saratov, 14.09.2019 ืกืขืคืืขืืืขืจ 2019). โ Sterlitamak: AMI, 65, ื. 69-XNUMX
ื ืืฆืืง ืึธื ืืืื ืงืืืืื ืืืืฃ ืืขืจ ืืขืืข:
4.
5.
ืืงืืจ: www.habr.com