Баарына салам.
Бул жазууда мен информатикада графиктерди сактоо үчүн колдонулган негизги маалымат структураларын санап чыгууну чечтим, ошондой эле мен үчүн кандайдыр бир жол менен "кристаллдашкан" дагы бир нече структуралар жөнүндө сүйлөшөм.
Ошентип, баштайлы. Бирок башынан эле эмес - менимче, биз баарыбыз график деген эмне экенин жана алар эмне экенин билебиз (багытталган, багытталбаган, салмактуу, салмаксыз, бир нече четтери жана илмектери бар же жок).
Ошентип, кетели. Бизде "график сактоо" үчүн маалымат структураларынын кандай варианттары бар?
1. Матрицалык маалымат структуралары
1.1 Кошуналык матрицасы. Кошумча матрица – бул матрица, мында саптын жана мамычанын аталыштары графтын чокуларынын сандарына туура келет, ал эми анын ар бир элементинин мааниси a(i,j) чокулардын ортосундагы четтердин бар же жоктугу менен аныкталат. i жана j (багытталбаган график үчүн мындай матрица симметриялуу болоору анык, же биз бардык маанилерди негизги диагоналдан гана жогору сактайбыз деп макул боло алабыз). Салмаксыз графиктер үчүн a(i,j) iден jге чейинки четтердин саны боюнча (эгерде андай чет жок болсо, анда a(i,j)= 0) жана салмактуу графиктер үчүн салмагы боюнча да коюлушу мүмкүн. (жалпы салмагы) көрсөтүлгөн четтеринин.
1.2 Инцидент матрицасы. Бул учурда, биздин график да таблицада сакталат, анда эреже катары, катар номерлери анын чокуларынын сандарына, ал эми мамычанын номерлери алдын ала номерленген четтерине туура келет. Эгерде чоку менен чети бири-бирине туш келсе, анда нөл эмес маани тиешелүү уячага жазылат (багытталбаган графиктер үчүн, чокусу жана чети туш келсе, 1 жазылат, багытталган графиктер үчүн - "1", эгерде чети болсо чокусунан "чыгат" жана "-1" ага "камтыса" (эсте калуу оңой, анткени "минус" белгиси да "-1" санына "киргизилген" окшойт)). Салмактуу графиктер үчүн дагы, 1 жана -1дин ордуна, четтин жалпы салмагын көрсөтсөңүз болот.
2. Санактоо маалыматтарынын структуралары
2.1 Кошумча тизме. Ооба, бул жерде баары жөнөкөй көрүнөт. Графиктин ар бир чокусу, жалпысынан, ар кандай санауу структурасы менен (тизме, вектор, массив, ...) байланыштырылышы мүмкүн, ал берилген бирине жанаша турган бардык чокулардын сандарын сактайт. Багытталган графиктер үчүн биз мындай тизмеге өзгөчөлүк чокусунан “багытталган” чети бар чокуларды гана кошобуз. Салмактуу графиктер үчүн ишке ашыруу татаалыраак болот.
2.2 Кабыргалардын тизмеси. Абдан популярдуу маалымат структурасы. Чектердин тизмеси, капитан Obviousness бизге айткандай, бул чындыгында графиктин четтеринин тизмеси, алардын ар бири башталгыч чокусу, аяккы чокусу менен аныкталат (багытталбаган графиктер үчүн бул жерде тартип маанилүү эмес, бирок бириктирүү үчүн ар кандай эрежелерди колдонуңуз, мисалы, чокуларды көбөйтүү иретинде көрсөтүү) жана салмак (салмактуу графиктер үчүн гана).
Сиз жогоруда саналган матрицалык тизмелерди кененирээк (жана иллюстрациялар менен) карай аласыз, мисалы, .
2.3 Кошумча массив. Эң таралган түзүлүш эмес. Негизинен, бул тизмектерди бир санап түзүмүнө (массив, вектор) "жыйноо" түрү. Мындай массивдин биринчи n (график чокуларынын санына жараша) элементтери ошол эле массивдин баштапкы индекстерин камтыйт, алардан баштап берилгенге жанаша турган бардык чокулар катарга жазылат.
Бул жерде мен эң түшүнүктүү (өзүм үчүн) түшүндүрмө таптым:
3. Коштук вектору жана ассоциативдик чектеш массив
Көрсө, бул саптардын автору профессионал программист эмес, бирок мезгил-мезгили менен графиктер менен алектенгендиктен, көбүнчө четтердин тизмеси менен алектенет экен. Чынында эле, графиктин бир нече илмектери жана четтери болсо ыңгайлуу. Ошентип, четтердин классикалык тизмелерин иштеп чыгууда мен алардын “өнүгүү/тармак/модификация/мутациясына” көңүл бурууну сунуштайм, тактап айтканда: чектеш вектор жана ассоциативдик чектеш массив.
3.1 Кошулуу вектору
Иш (a1): салмаксыз график
Салмаксыз график үчүн чектеш векторду бүтүн сандардын (a[2i], a[2i+1],..., мында i номери c 0) иреттелген иреттүү жыйындысы деп атайбыз, анда ар бир жуп сандар a[2i], a[2i+1 ] тиешелүүлүгүнө жараша a[2i] жана a[2i+1] чокуларынын ортосундагы графиктин четин аныктайт.
Бул жаздыруу форматында графиктин багытталганы жөнүндө маалымат камтылбайт (эки вариант тең мүмкүн). Диграф форматын колдонууда чети a[2i]ден a[2i+1] чейин багытталган деп эсептелет. Бул жерде жана төмөндө: багытталбаган графиктер үчүн, зарыл болсо, чокуларды жазуу тартибине талаптар колдонулушу мүмкүн (мисалы, ага ыйгарылган сандын төмөнкү мааниси бар чоку биринчи орунда турат).
C++ тилинде std::vektor аркылуу чектеш векторду көрсөтүү максатка ылайыктуу, демек, бул маалымат структурасынын аталышы.
Иш (a2): өлчөнгөн график, четиндеги салмактар бүтүн сан
(a1) учуруна окшоштук боюнча, биз бүтүн жээк салмактары бар салмактанып алынган график үчүн чектеш векторду сандардын иреттелген жыйындысы (динамикалык массив) деп атайбыз (a[3i], a[3i+1], a[3i+2], ..., мында i номерленген c 0), мында a[3i], a[3i+1], a[3i+2] сандарынын ар бир “үчтүкү” a[3i] номерленген чокуларынын ортосундагы графиктин четин аныктайт. жана a[3i+1], тиешелүүлүгүнө жараша, а [3i+2] мааниси бул кырдын салмагы. Мындай график да багытталышы мүмкүн же багытталбашы мүмкүн.
(b) учуру: өлчөнгөн эмес график, бүтүн эмес четтин салмагы
Гетерогендик элементтерди бир массивде (вектордо) сактоо мүмкүн болбогондуктан, мисалы, төмөнкү ишке ашыруу мүмкүн. График жуп векторлордо сакталат, мында биринчи вектор салмактарды көрсөтпөстөн графиктин чектеш вектору болуп саналат, ал эми экинчи вектор тиешелүү салмактарды камтыйт (C++ үчүн мүмкүн ишке ашыруу: std::pair) ). Ошентип, биринчи вектордун 2i, 2i+1 индекстеринин астындагы чокулардын жуптары менен аныкталган кыр үчүн салмак экинчи вектордун i индексинин астындагы элементке барабар болот.
Ооба, бул эмне үчүн керек?
Ооба, бул саптардын автору бир катар маселелерди чечүү үчүн абдан пайдалуу деп тапты. Расмий көз караштан алганда, төмөнкү артыкчылыктар болот:
- Кошуналык вектору, ар кандай башка “санак” структуралар сыяктуу эле, бир топ компакттуу, чектеш матрицага караганда азыраак эстутумду ээлейт (сейрек графиктер үчүн) жана ишке ашыруу салыштырмалуу жеңил.
- Графиктин чокулары, негизинен, терс сандар менен да белгилениши мүмкүн. Андай «бузукулук» керек болуп калсачы?
- Графиктер ар кандай салмактагы (оң, терс, жада калса нөл) бир нече кырларды жана бир нече циклдерди камтышы мүмкүн. Бул жерде эч кандай чектөөлөр жок.
- Сиз ошондой эле четтерине ар кандай касиеттерди дайындай аласыз - бирок бул тууралуу көбүрөөк билүү үчүн 4-бөлүмдү караңыз.
Бирок, бул "тизме" четине тез жетүү дегенди билдирбейт экенин моюнга алуу керек. Бул жерде Ассоциативдик чектеш массив жардамга келет, ал төмөндө талкууланат.
3.2 Ассоциативдик чектеш массив
Демек, эгерде белгилүү бир кырга, анын салмагына жана башка касиеттерине жетүү биз үчүн өтө маанилүү болсо жана эстутум талаптары чектеш матрицаны колдонууга мүмкүндүк бербесе, анда келгиле, бул маселени чечүү үчүн чектештик векторун кантип өзгөртө аларыбыз жөнүндө ойлонуп көрөлү. Ошентип, ачкыч - бүтүн сандардын иреттелген жуп катары көрсөтүлүшү мүмкүн болгон графиктин чети. Бул кандай көрүнөт? Бул ассоциативдик массивдин ачкычы эмеспи? А эгер ошондой болсо, эмне үчүн биз аны ишке ашырбайбыз? Ассоциативдик массивге ээ бололу, анда ар бир ачкыч - бүтүн сандардын иреттелген түгөйү - чектин салмагын көрсөткөн бир маани - бүтүн сан же реалдуу сан менен байланыштырылат. C++ тилинде бул структураны std::map контейнеринин (std::map) негизинде ишке ашыруу сунушталат. , int> же std::map , double>), же std::multimap, эгерде бир нече четтери күтүлсө. Ну и вот, и у нас получилась структура для хранения графов, которая занимает меньше памяти, нежели «матричные» структуры, может задавать графы со множественными петлями и ребрами и даже не имеющая жестких требований к неотрицательности номеров вершин (не знаю, кому это надо, Ошентсе да).
4. Маалымат структуралары толгон, бирок бир нерсе жетишпейт
Бул чындык: бир катар маселелерди чечип жатканда, графиктин четтерине кээ бир мүнөздөмөлөрдү ыйгарып, ошого жараша аларды сактоо керек болушу мүмкүн. Эгерде бул өзгөчөлүктөрдү бүтүн сандарга бир мааниде азайтуу мүмкүн болсо, анда чектеш вектордун жана ассоциативдик чектеш массивдин кеңейтилген версияларын колдонуу менен мындай “кошумча өзгөчөлүктөрү бар графиктерди” сактоого болот.
Ошентип, келгиле, салмаксыз графикке ээ бололу, анын ар бир четине, мисалы, бүтүн сандар менен аныкталган 2 кошумча функцияны сактоо керек. Мында анын чектеш векторун “жуптардын” эмес, бүтүн сандардын “квартеттеринин” (a[2i], a[2i+1], a[2i+2], [2i+3]…) , мында a[2i+2] жана a[2i+3] тиешелүү кырдын мүнөздөмөлөрүн аныктайт. Четтеринин бүтүн салмактары бар график үчүн тартип жалпысынан окшош (бир гана айырмачылык, атрибуттар кырдын салмагына жараша болот жана a[2i+3] жана a[2i+4] элементтери менен белгиленет. , жана четинин өзү 4 эмес, 5 иреттелген сандар көрсөтүлөт). Ал эми бүтүн эмес четинин салмагы бар график үчүн өзгөчөлүктөр анын салмаксыз компонентине жазылышы мүмкүн.
Бүтүн сандык кырлары бар графиктер үчүн ассоциативдик чектеш массивди колдонууда, маани катары бир эле санды эмес, чектин салмагынан тышкары анын бардык башка зарыл болгон массивдерин (векторлорун) көрсөтүүгө болот. Өзгөчөлүктөрү. Ошол эле учурда, бүтүн эмес салмактар үчүн ыңгайсыздык калкыма чекиттик номери бар белгини көрсөтүү зарылчылыгы болот (ооба, бул ыңгайсыздык, бирок мындай белгилер мынчалык көп болбосо, жана эгерде 'Аларды өтө эле "татаал" кош кылып койбоңуз, анда эч нерсе болбошу мүмкүн). Бул C++ кеңейтилген ассоциативдик чектеш массивдерди төмөнкүчө аныктоого болот дегенди билдирет: std::map , std::вектор> же std::карта , std::вектор, мында “ачкыч-маани-вектордогу” биринчи маани четинин салмагы болот, андан кийин анын мүнөздөмөлөрүнүн сандык белгилер жайгашкан.
Адабият:
Графиктер жана жалпысынан алгоритмдер жөнүндө:
1. Кормен, Томас Х., Лейзерсон, Чарльз I., Ривест, Рональд Л., Стейн, Клиффорд. Алгоритмдер: куруу жана анализ, 2-басылышы: Trans. англис тилинен – М.: Уильямс басмасы, 2011.
2. Харари Фрэнк. График теориясы. М.: Мир, 1973.
Ушул эле вектордук жана ассоциативдик чектеш массив жөнүндө автордун баяндамасы:
3. Черноухов С.А. Участкалык вектор жана ассоциативдик чектеш массив графиктерди көрсөтүү жана сактоо жолдору катары / Черноухов С.А. Контакттык вектор жана чектеш карта графикти көрсөтүү үчүн маалымат структуралары катары // “Инновациялык иштеп чыгуулардын натыйжаларын ишке киргизүү көйгөйлөрү жана аларды чечүүнүн жолдору” Эл аралык илимий-практикалык конференциянын макалаларынын жыйнагы (Саратов, 14.09.2019-сентябрь, 2019-ж.). – Стерлитамак: АМИ, 65, б. 69-XNUMX
Тема боюнча пайдалуу онлайн булактар:
4.
5.
Source: www.habr.com