ഗ്രാഫുകൾ സംഭരിക്കുന്നതിനുള്ള ഡാറ്റാ ഘടനകൾ: നിലവിലുള്ളവയുടെയും രണ്ട് "ഏതാണ്ട് പുതിയവ"യുടെയും ഒരു അവലോകനം

എല്ലാവർക്കും ഹലോ.

ഈ കുറിപ്പിൽ, കമ്പ്യൂട്ടർ സയൻസിൽ ഗ്രാഫുകൾ സംഭരിക്കുന്നതിന് ഉപയോഗിക്കുന്ന പ്രധാന ഡാറ്റാ ഘടനകൾ പട്ടികപ്പെടുത്താൻ ഞാൻ തീരുമാനിച്ചു, കൂടാതെ എനിക്കായി എങ്ങനെയെങ്കിലും “ക്രിസ്റ്റലൈസ്” ചെയ്ത അത്തരം രണ്ട് ഘടനകളെക്കുറിച്ചും ഞാൻ സംസാരിക്കും.

അതിനാൽ, നമുക്ക് ആരംഭിക്കാം. എന്നാൽ തുടക്കം മുതലേ അല്ല - ഒരു ഗ്രാഫ് എന്താണെന്നും അവ എന്താണെന്നും നമുക്കെല്ലാവർക്കും ഇതിനകം അറിയാമെന്ന് ഞാൻ കരുതുന്നു (ഡയറക്ടഡ്, അൺഡയറക്‌ട്, വെയ്‌റ്റഡ്, വെയിറ്റഡ്, ഒന്നിലധികം അരികുകളും ലൂപ്പുകളും ഉള്ളതോ അല്ലാതെയോ).

അതിനാൽ, നമുക്ക് പോകാം. "ഗ്രാഫ് സ്റ്റോറേജ്" എന്നതിനായുള്ള ഡാറ്റാ ഘടനകൾക്കായി നമുക്ക് എന്തെല്ലാം ഓപ്ഷനുകൾ ഉണ്ട്?

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 വാരിയെല്ലുകളുടെ പട്ടിക. വളരെ ജനപ്രിയമായ ഒരു ഡാറ്റാ ഘടന. ക്യാപ്റ്റൻ ഒബ്വിയസ്‌നെസ് നമ്മോട് പറയുന്നതുപോലെ, അരികുകളുടെ ലിസ്റ്റ് യഥാർത്ഥത്തിൽ ഗ്രാഫിൻ്റെ അരികുകളുടെ ഒരു പട്ടികയാണ്, അവ ഓരോന്നും ആരംഭ ശീർഷം, അവസാനിക്കുന്ന ശീർഷകം എന്നിവയാൽ വ്യക്തമാക്കുന്നു (ദിശയില്ലാതെയുള്ള ഗ്രാഫുകൾക്ക് ഓർഡർ ഇവിടെ പ്രധാനമല്ല, എന്നിരുന്നാലും ഏകീകരണത്തിനായി നിങ്ങൾക്ക് കഴിയും വിവിധ നിയമങ്ങൾ ഉപയോഗിക്കുക, ഉദാഹരണത്തിന്, വർദ്ധിക്കുന്ന ക്രമത്തിൽ ലംബങ്ങൾ വ്യക്തമാക്കുക), ഭാരം (ഭാരമുള്ള ഗ്രാഫുകൾക്ക് മാത്രം).

മുകളിൽ ലിസ്റ്റുചെയ്തിരിക്കുന്ന മാട്രിക്സ് ലിസ്റ്റുകൾ നിങ്ങൾക്ക് കൂടുതൽ വിശദമായി (ചിത്രീകരണങ്ങളോടെ) നോക്കാം, ഉദാഹരണത്തിന്, ഇവിടെ.

2.3 തൊട്ടടുത്തുള്ള അറേ. ഏറ്റവും സാധാരണമായ ഘടനയല്ല. അതിൻ്റെ കാമ്പിൽ, ഇത് ഒരു എൻയുമറേഷൻ ഘടനയിലേക്ക് (അറേ, വെക്റ്റർ) "പാക്കിംഗ്" അഡ്‌ജസെൻസി ലിസ്റ്റുകളുടെ ഒരു രൂപമാണ്. അത്തരമൊരു അറേയുടെ ആദ്യ n (ഗ്രാഫിൻ്റെ ലംബങ്ങളുടെ എണ്ണം അനുസരിച്ച്) ഘടകങ്ങളിൽ ഒരേ ശ്രേണിയുടെ ആരംഭ സൂചികകൾ അടങ്ങിയിരിക്കുന്നു, അതിൽ നിന്ന് ആരംഭിക്കുന്ന ഒന്നിനോട് ചേർന്നുള്ള എല്ലാ ശീർഷകങ്ങളും ഒരു വരിയിൽ എഴുതിയിരിക്കുന്നു.

ഇവിടെ ഞാൻ ഏറ്റവും മനസ്സിലാക്കാവുന്ന (എനിക്ക്) വിശദീകരണം കണ്ടെത്തി: ejuo.livejournal.com/4518.html

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], ..., ഇവിടെ c 0 എന്ന് അക്കമിട്ടിരിക്കുന്നു), ഇവിടെ a[3i], a[3i+1], a[3i+2] എന്ന സംഖ്യകളുടെ ഓരോ “ട്രിപ്പിൾ” യും a[3i] എന്ന അക്കങ്ങൾക്കിടയിലുള്ള ഗ്രാഫിൻ്റെ ഒരു അഗ്രം വ്യക്തമാക്കുന്നു. യഥാക്രമം a[3i+1], മൂല്യം a [3i+2] ഈ അരികിൻ്റെ ഭാരമാണ്. അത്തരത്തിലുള്ള ഒരു ഗ്രാഫ് ഡയറക്‌ടുചെയ്യുകയോ ചെയ്യാതിരിക്കുകയോ ചെയ്യാം.

കേസ് (ബി): വെയിറ്റഡ് ഗ്രാഫ്, നോൺ-ഇൻ്റേജർ എഡ്ജ് വെയ്റ്റുകൾ

ഒരു അറേയിൽ (വെക്റ്റർ) വൈവിധ്യമാർന്ന മൂലകങ്ങൾ സംഭരിക്കുന്നത് അസാധ്യമായതിനാൽ, ഉദാഹരണത്തിന്, ഇനിപ്പറയുന്ന നടപ്പാക്കൽ സാധ്യമാണ്. ഗ്രാഫ് ഒരു ജോടി വെക്‌റ്ററുകളിൽ സംഭരിച്ചിരിക്കുന്നു, അതിൽ ആദ്യത്തെ വെക്‌ടർ ഭാരങ്ങൾ വ്യക്തമാക്കാതെ ഗ്രാഫിൻ്റെ അഡ്‌ജസെൻസി വെക്‌ടറാണ്, രണ്ടാമത്തെ വെക്‌ടറിൽ അനുബന്ധ ഭാരങ്ങൾ അടങ്ങിയിരിക്കുന്നു (സി++: സ്‌ടിഡി:: ജോടിക്ക് സാധ്യമായ നടപ്പിലാക്കൽ ). അങ്ങനെ, ആദ്യ വെക്‌ടറിൻ്റെ 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], 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:: വെക്റ്റർ, അതിൽ "കീ-മൂല്യം-വെക്റ്റർ" എന്നതിലെ ആദ്യ മൂല്യം അരികിൻ്റെ ഭാരം ആയിരിക്കും, തുടർന്ന് അതിൻ്റെ സ്വഭാവസവിശേഷതകളുടെ സംഖ്യാ പദവികൾ സ്ഥിതിചെയ്യുന്നു.

സാഹിത്യം:

ഗ്രാഫുകളെക്കുറിച്ചും അൽഗോരിതങ്ങളെക്കുറിച്ചും പൊതുവായി:

1. കോർമെൻ, തോമസ് എച്ച്., ലെയ്സർസൺ, ചാൾസ് I., റിവെസ്റ്റ്, റൊണാൾഡ് എൽ., സ്റ്റെയ്ൻ, ക്ലിഫോർഡ്. അൽഗോരിതങ്ങൾ: നിർമ്മാണവും വിശകലനവും, രണ്ടാം പതിപ്പ്: ട്രാൻസ്. ഇംഗ്ലീഷിൽ നിന്ന് – എം.: വില്യംസ് പബ്ലിഷിംഗ് ഹൗസ്, 2.
2. ഹരാരി ഫ്രാങ്ക്. ഗ്രാഫ് സിദ്ധാന്തം. എം.: മിർ, 1973.
സമാന വെക്‌ടറിനെയും അനുബന്ധ ശ്രേണിയെയും കുറിച്ചുള്ള രചയിതാവിൻ്റെ റിപ്പോർട്ട്:
3. Chernoukhov S.A. ഗ്രാഫുകളെ പ്രതിനിധീകരിക്കുന്നതിനും സംഭരിക്കുന്നതിനുമുള്ള വഴികളായി അഡ്‌ജസെൻസി വെക്‌ടറും അസോസിയേറ്റീവ് അഡ്‌ജസെൻസി അറേയും / SA Chernouhov. ഒരു ഗ്രാഫിനെ പ്രതിനിധീകരിക്കുന്നതിനുള്ള ഡാറ്റാ ഘടനകളായി അഡ്‌ജസെൻസി വെക്‌ടറും അഡ്‌ജസെൻസി മാപ്പും // ഇൻ്റർനാഷണൽ സയൻ്റിഫിക് ആൻ്റ് പ്രാക്ടിക്കൽ കോൺഫറൻസിൻ്റെ ലേഖനങ്ങളുടെ ശേഖരം “നൂതന സംഭവവികാസങ്ങളുടെയും അവ പരിഹരിക്കാനുള്ള വഴികളുടെയും ഫലങ്ങൾ നടപ്പിലാക്കുന്നതിലെ പ്രശ്‌നങ്ങൾ” (സരടോവ്, സെപ്റ്റംബർ 14.09.2019, 2019). – സ്റ്റെർലിറ്റമാക്: എഎംഐ, 65, പേ. 69-XNUMX
വിഷയത്തെക്കുറിച്ചുള്ള ഉപയോഗപ്രദമായ ഓൺലൈൻ ഉറവിടങ്ങൾ:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

അവലംബം: www.habr.com