Всем привет.
Бұл жазбада мен информатикада графиктерді сақтау үшін пайдаланылатын негізгі деректер құрылымдарын тізіп шығуды шештім, сонымен қатар мен үшін қандай да бір түрде «кристалданған» тағы бірнеше осындай құрылымдар туралы айтатын боламын.
Сонымен, бастайық. Бірақ басынан бастап емес - менің ойымша, біз бәріміз графиктің не екенін және олардың не екенін білеміз (бағытталған, бағытталмаған, өлшенген, өлшенбеген, бірнеше жиектер мен ілмектер бар немесе жоқ).
Ендеше, кеттік. Бізде «графиктерді сақтау» үшін деректер құрылымдарының қандай нұсқалары бар?
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 Қабырғалардың тізімі. Өте танымал деректер құрылымы. Шеттердің тізімі, Captain 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::vector көмегімен іргелестік векторын көрсеткен жөн, сондықтан бұл деректер құрылымының атауы.
Жағдай (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] және a [3i+2] мәні осы жиектің салмағы болып табылады. Сондай-ақ мұндай график бағытталған болуы да, болмауы да мүмкін.
(b) жағдайы: өлшенбеген график, бүтін емес жиек салмақтары
Гетерогенді элементтерді бір массивте (векторда) сақтау мүмкін болмағандықтан, мысалы, келесі іске асыру мүмкін болады. График векторлар жұбында сақталады, онда бірінші вектор салмақтарды көрсетпей графиктің іргелес векторы болып табылады, ал екінші вектор сәйкес салмақтарды қамтиды (C++: std::pair үшін мүмкін іске асыру). ). Осылайша, бірінші вектордың 2i, 2i+1 индекстерінің астындағы шыңдар жұбымен анықталған жиек үшін салмақ екінші вектордың i индексінің астындағы элементке тең болады.
Ал, бұл не үшін қажет?
Бұл жолдардың авторы оны бірқатар мәселелерді шешу үшін өте пайдалы деп тапты. Ресми тұрғыдан алғанда, келесі артықшылықтар болады:
- Көршілестік векторы, кез келген басқа «санақ» құрылымы сияқты, айтарлықтай ықшам, іргелес матрицаға қарағанда (сирек графиктер үшін) аз жадты алады және салыстырмалы түрде оңай жүзеге асырылады.
- Графиктің шыңдары, негізінен, теріс сандармен де белгіленуі мүмкін. Мұндай «бұзушылық» қажет болса ше?
- Графиктер салмағы әртүрлі (оң, теріс, тіпті нөл) бірнеше жиектер мен бірнеше циклдардан тұруы мүмкін. Мұнда ешқандай шектеулер жоқ.
- Сондай-ақ жиектерге әртүрлі сипаттарды тағайындауға болады, бірақ бұл туралы қосымша ақпарат алу үшін 4-бөлімді қараңыз.
Дегенмен, бұл «тізім» шетке жылдам қол жеткізуді білдірмейтінін мойындау керек. Міне, төменде талқыланатын Ассоциативті көршілестік массиві көмекке келеді.
3.2 Ассоциативті іргелес массив
Сонымен, егер белгілі бір жиекке, оның салмағына және басқа қасиеттеріне қол жеткізу біз үшін өте маңызды болса және жад талаптары іргелес матрицаны пайдалануға мүмкіндік бермесе, онда бұл мәселені шешу үшін іргелестік векторын қалай өзгертуге болатынын ойластырайық. Сонымен, кілт - бұл реттелген бүтін жұп ретінде көрсетуге болатын графиктің шеті. Бұл неге ұқсайды? Бұл ассоциативті массивтің кілті емес пе? Ал егер солай болса, неге біз оны жүзеге асырмаймыз? Ассоциативті массив болсын, онда әрбір кілт – реттелген бүтін сандар жұбы – мәнмен – бүтін санмен немесе жиектің салмағын көрсететін нақты санмен байланыстырылады. C++ тілінде бұл құрылымды std::map контейнері (std::map) негізінде жүзеге асырған жөн. , int> немесе std::map , double>), немесе std::multimimap, егер бірнеше жиектер күтілсе. Ну и вот, и у нас получилась структура для хранения графов, которая занимает меньше памяти, нежели «матричные» структуры, может задавать графы со множественными петлями и ребрами и даже не имеющая жестких требований к неотрицательности номеров вершин (не знаю, кому это надо, Сонда да).
4. Деректер құрылымдары толы, бірақ бірдеңе жетіспейді
Және бұл рас: бірқатар есептерді шешу кезінде графиктің шеттеріне кейбір сипаттамаларды тағайындау және тиісінше оларды сақтау қажет болуы мүмкін. Егер бұл мүмкіндіктерді бүтін сандарға бір мәнді түрде азайту мүмкін болса, онда іргелес вектордың және ассоциативті іргелес массивтің кеңейтілген нұсқаларын пайдалана отырып, мұндай «қосымша мүмкіндіктері бар графиктерді» сақтауға болады.
Сонымен, бізде өлшенбеген график болсын, оның әрбір жиегі үшін, мысалы, бүтін сандармен көрсетілген 2 қосымша мүмкіндікті сақтау қажет. Бұл жағдайда оның іргелестік векторын «жұптардың» емес, бүтін сандардың (a[2i], a[2i+1], a[2i+2], a) «квартеттерінің» реттелген жиыны ретінде анықтауға болады. [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-ші басылым: Транс. ағылшын тілінен – М.: Уильямс баспасы, 2011 ж.
2. Харари Фрэнк. Графикалық теория. М.: Мир, 1973 ж.
Дәл осы векторлық және ассоциативті қатарлар туралы автордың есебі:
3. Черноухов С.А. Көршілестік векторы және ассоциативті іргелестік массиві графиктерді көрсету және сақтау тәсілдері ретінде / С.А.Черноухов. Іргелестік векторы және іргелестік картасы графикті көрсету үшін деректер құрылымдары ретінде // «Инновациялық әзірлемелердің нәтижелерін енгізу мәселелері және оларды шешу жолдары» Халықаралық ғылыми-практикалық конференция мақалаларының жинағы (Саратов, 14.09.2019 қыркүйек 2019 ж.). – Стерлитамак: AMI, 65, б. 69-XNUMX
Тақырып бойынша пайдалы интернет көздері:
4.
5.
Ақпарат көзі: www.habr.com