Բարեւ բոլորին
Այս գրառման մեջ ես որոշեցի թվարկել հիմնական տվյալների կառուցվածքները, որոնք օգտագործվում են համակարգչային գիտության մեջ գրաֆիկները պահելու համար, և ես կխոսեմ ևս մի քանի նման կառուցվածքների մասին, որոնք ինչ-որ կերպ «բյուրեղացել» են ինձ համար:
Այսպիսով, եկեք սկսենք: Բայց ոչ ի սկզբանե - կարծում եմ, մենք բոլորս արդեն գիտենք, թե ինչ է գրաֆիկը և ինչ են դրանք (ուղղված, չուղղորդված, կշռված, չկշռված, բազմաթիվ եզրերով և օղակներով կամ առանց):
Այսպիսով, եկեք գնանք: Տվյալների կառուցվածքների ի՞նչ տարբերակներ ունենք «գրաֆիկի պահպանման» համար:
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] արժեքը այս եզրի կշիռն է: Նման գրաֆիկը կարող է նաև ուղղորդված լինել, կամ ոչ:
Դեպք (բ)՝ չկշռված գրաֆիկ, ոչ ամբողջ թվային եզրերի կշիռներ
Քանի որ անհնար է տարասեռ տարրերը պահել մեկ զանգվածում (վեկտոր), օրինակ, հնարավոր է հետևյալ իրականացումը. Գրաֆիկը պահվում է զույգ վեկտորներում, որոնցում առաջին վեկտորը գրաֆի հարևանության վեկտորն է՝ առանց կշիռները նշելու, իսկ երկրորդ վեկտորը պարունակում է համապատասխան կշիռներ (C++-ի հնարավոր իրականացում՝ std::pair ). Այսպիսով, առաջին վեկտորի 2i, 2i+1 ինդեքսների տակ գտնվող զույգ գագաթներով սահմանված եզրի համար կշիռը հավասար կլինի երկրորդ վեկտորի i ցուցիչի տակ գտնվող տարրին։
Դե, ինչու է դա անհրաժեշտ:
Դե, այս տողերի հեղինակը բավականին օգտակար է համարել մի շարք խնդիրներ լուծելու համար։ Դե, ֆորմալ տեսանկյունից, կլինեն հետևյալ առավելությունները.
- Հարևանության վեկտորը, ինչպես ցանկացած այլ «թվային» կառուցվածք, բավականին կոմպակտ է, ավելի քիչ հիշողություն է զբաղեցնում, քան հարևանության մատրիցը (նոսր գրաֆիկների համար) և համեմատաբար հեշտ է իրագործել:
- Գրաֆիկի գագաթները, սկզբունքորեն, կարելի է նշել նաև բացասական թվերով։ Իսկ եթե նման «այլասերվածություն» է պետք։
- Գրաֆիկները կարող են պարունակել բազմաթիվ եզրեր և բազմաթիվ օղակներ՝ տարբեր կշիռներով (դրական, բացասական, նույնիսկ զրո): Այստեղ սահմանափակումներ չկան։
- Դուք կարող եք նաև տարբեր հատկություններ վերագրել եզրերին, բայց դրա մասին ավելին տե՛ս բաժին 4:
Այնուամենայնիվ, պետք է խոստովանել, որ այս «ցուցակը» չի ենթադրում արագ մուտք դեպի եզր։ Եվ այստեղ օգնության է գալիս Associative Adjacency Array-ը, որը քննարկվում է ստորև:
3.2 Ասոցիատիվ հարևանության զանգված
Այսպիսով, եթե մուտքը կոնկրետ եզրին, դրա քաշը և այլ հատկություններ մեզ համար կարևոր է, և հիշողության պահանջները թույլ չեն տալիս օգտագործել հարևանության մատրիցը, ապա եկեք մտածենք, թե ինչպես կարող ենք փոխել հարևանության վեկտորը այս խնդիրը լուծելու համար: Այսպիսով, բանալին գրաֆիկի եզրն է, որը կարելի է նշել որպես ամբողջ թվերի դասավորված զույգ: Ինչպիսի՞ն է սա: Բանալին չէ՞ ասոցիատիվ զանգվածում: Եվ եթե այո, ապա ինչո՞ւ չենք իրականացնում այն։ Եկեք ունենանք ասոցիատիվ զանգված, որտեղ յուրաքանչյուր ստեղն՝ ամբողջ թվերի դասավորված զույգ, կապված կլինի արժեքի հետ՝ ամբողջ կամ իրական թիվը, որը սահմանում է եզրի կշիռը: C++-ում խորհուրդ է տրվում իրականացնել այս կառուցվածքը՝ հիմնվելով std::map կոնտեյների վրա (std::map , int> կամ std::map , double>), կամ std::multimap, եթե ակնկալվում են մի քանի եզրեր: Դե, մենք ունենք գրաֆիկներ պահելու կառուցվածք, որն ավելի քիչ հիշողություն է խլում, քան «մատրիցային» կառուցվածքները, կարող է սահմանել գրաֆիկներ մի քանի օղակներով և եզրերով, և նույնիսկ խիստ պահանջներ չունի գագաթային թվերի ոչ բացասական լինելու համար (չգիտեմ ում է դա պետք, բայց դեռ):
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::vector> կամ std::map , std::vector, որում «բանալի-արժեք-վեկտորի» առաջին արժեքը կլինի եզրի կշիռը, այնուհետև տեղակայված են նրա բնութագրերի թվային նշանակումները։
Գրականություն.
Ընդհանուր առմամբ գրաֆիկների և ալգորիթմների մասին.
1. Կորմեն, Թոմաս Հ., Լեյզերսոն, Չարլզ Ի., Ռիվեստ, Ռոնալդ Լ., Սթայն, Քլիֆորդ: Ալգորիթմներ՝ կառուցում և վերլուծություն, 2-րդ հրատարակություն՝ Տրանս. անգլերենից - M.: Williams Publishing House, 2011:
2. Հարարի Ֆրանկ. Գրաֆիկի տեսություն. Մ.: Միր, 1973:
Հեղինակի զեկույցը այս նույն վեկտորային և հարևանությունների ասոցիատիվ զանգվածի մասին.
3. Չեռնուխով Ս.Ա. Հարևանության վեկտորը և ասոցիատիվ հարևանության զանգվածը որպես գրաֆիկներ ներկայացնելու և պահելու եղանակներ / SA Chernouhov. Հարևանության վեկտորը և հարևանության քարտեզը որպես գծապատկեր ներկայացնելու տվյալների կառուցվածքներ // Միջազգային գիտական և գործնական կոնֆերանսի «Նորարարական զարգացումների արդյունքների իրականացման հիմնախնդիրները և դրանց լուծման ուղիները» հոդվածների ժողովածու (Սարատով, 14.09.2019 սեպտեմբերի, 2019 թ.): – Sterlitamak: AMI, 65, էջ. 69-XNUMX թթ
Օգտակար առցանց աղբյուրներ թեմայի վերաբերյալ.
4.
5.
Source: www.habr.com