ગ્રાફ સ્ટોર કરવા માટે ડેટા સ્ટ્રક્ચર્સ: હાલના અને બે "લગભગ નવા" ની સમીક્ષા

બધા ને નમસ્કાર.

આ નોંધમાં, મેં કોમ્પ્યુટર સાયન્સમાં આલેખને સંગ્રહિત કરવા માટે ઉપયોગમાં લેવાતા મુખ્ય ડેટા સ્ટ્રક્ચર્સની સૂચિ બનાવવાનું નક્કી કર્યું, અને હું આવા કેટલાક વધુ બંધારણો વિશે પણ વાત કરીશ જે મારા માટે કોઈક રીતે "સ્ફટિકીકૃત" છે.

તો, ચાલો શરૂ કરીએ. પરંતુ શરૂઆતથી જ નહીં - મને લાગે છે કે આપણે બધા પહેલાથી જ જાણીએ છીએ કે ગ્રાફ શું છે અને તે શું છે (નિર્દેશિત, અનિર્દેશિત, ભારિત, વજન વિનાનું, બહુવિધ ધાર અને લૂપ્સ સાથે અથવા વગર).

તો, ચાલો જઈએ. અમારી પાસે "ગ્રાફ સ્ટોરેજ" માટે ડેટા સ્ટ્રક્ચર માટે કયા વિકલ્પો છે?

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], ..., જ્યાં i ને c 0 ક્રમાંકિત કરવામાં આવે છે), જ્યાં a[3i], a[3i+1], a[3i+2] સંખ્યાઓનો દરેક "ટ્રિપલેટ" એ[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::નકશો , double>), અથવા std::મલ્ટીમેપ જો બહુવિધ ધાર અપેક્ષિત હોય. ઠીક છે, અમારી પાસે ગ્રાફ સ્ટોર કરવા માટેનું માળખું છે જે “મેટ્રિક્સ” સ્ટ્રક્ચર્સ કરતાં ઓછી મેમરી લે છે, બહુવિધ લૂપ્સ અને કિનારીઓ સાથે આલેખને વ્યાખ્યાયિત કરી શકે છે, અને શિરોબિંદુ નંબરોની બિન-નકારાત્મકતા માટે કડક આવશ્યકતાઓ પણ નથી (મને ખબર નથી. કોને આની જરૂર છે, પરંતુ હજુ પણ).

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::નકશો , std::vector, જેમાં "કી-વેલ્યુ-વેક્ટર" માં પ્રથમ મૂલ્ય ધારનું વજન હશે, અને પછી તેની લાક્ષણિકતાઓના સંખ્યાત્મક હોદ્દો સ્થિત છે.

સાહિત્ય:

સામાન્ય રીતે આલેખ અને અલ્ગોરિધમ્સ વિશે:

1. કોરમેન, થોમસ એચ., લીઝરસન, ચાર્લ્સ આઈ., રિવેસ્ટ, રોનાલ્ડ એલ., સ્ટેઈન, ક્લિફોર્ડ. અલ્ગોરિધમ્સ: બાંધકામ અને વિશ્લેષણ, 2જી આવૃત્તિ: ટ્રાન્સ. અંગ્રેજીમાંથી – એમ.: વિલિયમ્સ પબ્લિશિંગ હાઉસ, 2011.
2. હરારી ફ્રેન્ક. ગ્રાફ થિયરી. એમ.: મીર, 1973.
આ સમાન વેક્ટર અને સંલગ્નતાઓની સહયોગી શ્રેણી વિશે લેખકનો અહેવાલ:
3. ચેર્નોખોવ એસ.એ. આલેખને રજૂ કરવા અને સંગ્રહિત કરવાના માર્ગો તરીકે સંલગ્નતા વેક્ટર અને સહયોગી સંલગ્નતા એરે / SA ચેર્નોહોવ. ગ્રાફનું પ્રતિનિધિત્વ કરવા માટે ડેટા સ્ટ્રક્ચર્સ તરીકે સંલગ્નતા વેક્ટર અને સંલગ્નતા નકશો // આંતરરાષ્ટ્રીય વૈજ્ઞાનિક અને પ્રાયોગિક પરિષદના લેખોનો સંગ્રહ "નવીન વિકાસના પરિણામોના અમલીકરણની સમસ્યાઓ અને તેમને હલ કરવાની રીતો" (સેરાટોવ, સપ્ટેમ્બર 14.09.2019, 2019). – સ્ટર્લિટામક: AMI, 65, p. 69-XNUMX
વિષય પર ઉપયોગી ઓનલાઇન સ્ત્રોતો:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

સોર્સ: www.habr.com