வரைபடங்களை சேமிப்பதற்கான தரவு கட்டமைப்புகள்: ஏற்கனவே உள்ளவை மற்றும் இரண்டு "கிட்டத்தட்ட புதியவை" பற்றிய மதிப்பாய்வு

அனைவருக்கும் வணக்கம்.

இந்த குறிப்பில், கணினி அறிவியலில் வரைபடங்களைச் சேமிக்கப் பயன்படுத்தப்படும் முக்கிய தரவு கட்டமைப்புகளை பட்டியலிட முடிவு செய்தேன், மேலும் எனக்கு எப்படியாவது "படிகமாக்கப்பட்ட" இதுபோன்ற இரண்டு கட்டமைப்புகளைப் பற்றியும் பேசுவேன்.

எனவே, ஆரம்பிக்கலாம். ஆனால் ஆரம்பத்தில் இருந்தே இல்லை - வரைபடம் என்றால் என்ன, அவை என்ன என்பதை நாம் அனைவரும் ஏற்கனவே அறிந்திருக்கிறோம் என்று நினைக்கிறேன் (இயக்கப்பட்டது, திசைதிருப்பப்படாதது, எடை, எடையில்லாதது, பல விளிம்புகள் மற்றும் சுழல்கள் அல்லது இல்லாமல்).

எனவே, போகலாம். "வரைபட சேமிப்பகத்திற்கான" தரவு கட்டமைப்புகளுக்கான என்ன விருப்பங்கள் எங்களிடம் உள்ளன?

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] என்பது இந்த விளிம்பின் எடை. அத்தகைய வரைபடம் இயக்கப்படலாம் அல்லது இயக்கப்படாமல் இருக்கலாம்.

வழக்கு (b): எடையில்லாத வரைபடம், முழு எண் அல்லாத விளிம்பு எடைகள்

ஒரு வரிசையில் (வெக்டார்) பன்முகத்தன்மை கொண்ட கூறுகளை சேமிப்பது சாத்தியமற்றது என்பதால், எடுத்துக்காட்டாக, பின்வரும் செயல்படுத்தல் சாத்தியமாகும். வரைபடம் ஒரு ஜோடி திசையன்களில் சேமிக்கப்படுகிறது, இதில் முதல் திசையன் எடைகளைக் குறிப்பிடாமல் வரைபடத்தின் அருகில் இருக்கும் திசையன் ஆகும், மேலும் இரண்டாவது திசையன் தொடர்புடைய எடைகளைக் கொண்டுள்ளது (C++: std:: pair க்கு சாத்தியமான செயல்படுத்தல் ) எனவே, முதல் திசையனின் 2i, 2i+1 குறியீடுகளின் கீழ் ஒரு ஜோடி செங்குத்துகளால் வரையறுக்கப்பட்ட ஒரு விளிம்பிற்கு, எடையானது இரண்டாவது திசையன் குறியீட்டின் கீழ் உள்ள உறுப்புக்கு சமமாக இருக்கும்.

சரி, இது ஏன் அவசியம்?

சரி, இந்த வரிகளின் ஆசிரியர் பல சிக்கல்களைத் தீர்க்க இது மிகவும் பயனுள்ளதாக இருந்தது. சரி, ஒரு முறையான பார்வையில், பின்வரும் நன்மைகள் இருக்கும்:

• அருகிலுள்ள திசையன், மற்ற எந்த "எண்ணியல்" அமைப்பைப் போலவே, மிகவும் கச்சிதமானது, அட்ஜெசென்சி மேட்ரிக்ஸை விட (சில வரைபடங்களுக்கு) குறைவான நினைவகத்தை எடுத்துக்கொள்கிறது, மேலும் செயல்படுத்துவது ஒப்பீட்டளவில் எளிதானது.
• வரைபடத்தின் செங்குத்துகள், கொள்கையளவில், எதிர்மறை எண்களால் குறிக்கப்படலாம். அத்தகைய "வக்கிரம்" தேவைப்பட்டால் என்ன செய்வது?
• வரைபடங்கள் பல விளிம்புகள் மற்றும் பல சுழல்களைக் கொண்டிருக்கலாம், வெவ்வேறு எடைகள் (நேர்மறை, எதிர்மறை, பூஜ்ஜியம் கூட). இங்கு எந்த கட்டுப்பாடுகளும் இல்லை.
• நீங்கள் விளிம்புகளுக்கு வெவ்வேறு பண்புகளை ஒதுக்கலாம் - ஆனால் அதைப் பற்றி மேலும் அறிய, பிரிவு 4 ஐப் பார்க்கவும்.

இருப்பினும், இந்த "பட்டியல்" விளிம்பிற்கு விரைவான அணுகலைக் குறிக்கவில்லை என்பதை ஒப்புக் கொள்ள வேண்டும். இங்கே அசோசியேட்டிவ் அட்ஜாசென்சி வரிசை மீட்புக்கு வருகிறது, இது கீழே விவாதிக்கப்படுகிறது.

3.2 அசோசியேட்டிவ் அட்ஜெசென்சி வரிசை

எனவே, ஒரு குறிப்பிட்ட விளிம்பு, அதன் எடை மற்றும் பிற பண்புகளுக்கான அணுகல் நமக்கு முக்கியமானது, மேலும் நினைவகத் தேவைகள் அருகிலுள்ள அணியைப் பயன்படுத்த அனுமதிக்கவில்லை என்றால், இந்த சிக்கலைத் தீர்க்க பக்க திசையனை எவ்வாறு மாற்றுவது என்பதைப் பற்றி சிந்திப்போம். எனவே, விசை என்பது வரைபடத்தின் ஒரு விளிம்பாகும், இது வரிசைப்படுத்தப்பட்ட ஜோடி முழு எண்களாக குறிப்பிடப்படலாம். இது எப்படி இருக்கும்? அசோசியேட்டிவ் வரிசையில் இது ஒரு திறவுகோல் இல்லையா? மற்றும், அப்படியானால், நாம் ஏன் அதை செயல்படுத்தக்கூடாது? ஒவ்வொரு விசையும் - வரிசைப்படுத்தப்பட்ட ஜோடி முழு எண்கள் - ஒரு மதிப்புடன் தொடர்புடையதாக இருக்கும் - ஒரு முழு எண் அல்லது விளிம்பின் எடையைக் குறிப்பிடும் உண்மையான எண். C++ இல், std::map கொள்கலன் (std::map) அடிப்படையில் இந்தக் கட்டமைப்பைச் செயல்படுத்துவது நல்லது. , int> அல்லது std::map , இரட்டை>), அல்லது பல முனைகள் எதிர்பார்க்கப்பட்டால் 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. கோர்மென், தாமஸ் எச்., லீசர்சன், சார்லஸ் I., ரிவெஸ்ட், ரொனால்ட் எல்., ஸ்டீன், கிளிஃபோர்ட். அல்காரிதம்கள்: கட்டுமானம் மற்றும் பகுப்பாய்வு, 2வது பதிப்பு: டிரான்ஸ். ஆங்கிலத்தில் இருந்து – எம்.: வில்லியம்ஸ் பப்ளிஷிங் ஹவுஸ், 2011.
2. ஹராரி பிராங்க். வரைபடக் கோட்பாடு. எம்.: மிர், 1973.
இதே வெக்டார் மற்றும் அசோசியேட்டிவ் வரிசை பற்றிய ஆசிரியரின் அறிக்கை:
3. Chernoukhov S.A. வரைபடங்களை பிரதிநிதித்துவப்படுத்துவதற்கும் சேமிப்பதற்கும் வழிகள் / எஸ்ஏ செர்னௌஹோவ் போன்ற அட்ஜாசென்சி வெக்டார் மற்றும் அசோசியேட்டிவ் அட்ஜெசென்சி வரிசை. வரைபடத்தை பிரதிநிதித்துவப்படுத்த தரவு கட்டமைப்புகளாக அருகிலுள்ள திசையன் மற்றும் அருகிலுள்ள வரைபடம். – ஸ்டெர்லிடமாக்: ஏஎம்ஐ, 14.09.2019, ப. 2019-65
தலைப்பில் பயனுள்ள ஆன்லைன் ஆதாரங்கள்:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

ஆதாரம்: www.habr.com