ግራፎችን ለማከማቸት የውሂብ አወቃቀሮች-የነባር ግምገማ እና ሁለት "ከሞላ ጎደል አዲስ"

ሰላም.

በዚህ ማስታወሻ ውስጥ ፣ በኮምፒተር ሳይንስ ውስጥ ግራፎችን ለማከማቸት የሚያገለግሉ ዋና ዋና የመረጃ አወቃቀሮችን ለመዘርዘር ወሰንኩ ፣ እና እንዲሁም በሆነ መንገድ ለእኔ “ክሪስታል” ስላደረጉት ስለ ሁለት ተጨማሪ እንደዚህ ያሉ መዋቅሮችን እናገራለሁ ።

ስለዚህ, እንጀምር. ግን ከመጀመሪያው አይደለም - ሁላችንም ግራፍ ምን እንደሆነ እና ምን እንደሆኑ (የተመራ ፣ ያልተመራ ፣ ክብደት ፣ ክብደት የሌለው ፣ ባለ ብዙ ጠርዞች እና ቀለበቶች) ሁላችንም የምናውቀው ይመስለኛል።

ስለዚህ እንሂድ። ለ "ግራፍ ማከማቻ" የመረጃ አወቃቀሮች ምን አማራጮች አሉን?

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. Adjacency ቬክተር እና አሶሺዬቲቭ አድጃሰንት ድርድር

የእነዚህ መስመሮች ደራሲ ፕሮፌሽናል ፕሮግራመር ሳይሆን አልፎ አልፎ ግራፎችን የሚናገር፣ አብዛኛውን ጊዜ የዳርቻ ዝርዝሮችን ይሰራ እንደነበር ታወቀ። በእርግጥ, ግራፉ ብዙ ቀለበቶች እና ጠርዞች ካሉት ምቹ ነው. እና ስለዚህ፣ የጥንታዊውን የዳርቻ ዝርዝሮችን በማዳበር፣ ለ “ልማት/ቅርንጫፋቸው/ማሻሻያ/ሚውቴሽን” ማለትም ለአጎራባች ቬክተር እና ለተባባሪነት ድርድር ትኩረት እንድንሰጥ ሀሳብ አቀርባለሁ።

3.1 Adjacency ቬክተር

ጉዳይ (a1): ክብደት የሌለው ግራፍ

ላልተመዘነ ግራፍ የአጎራባች ቬክተር እንጠራዋለን ፣የተመጣጣኝ ቁጥር ያላቸው ኢንቲጀሮች (a[2i] ፣ a[2i+1] ፣... ፣ እኔ የተቆጠርኩበት ሐ 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]፣ ...፣ እኔ ሲ 0 የተቆጠርኩበት)፣ እያንዳንዱ “ሶስትዮሽ” የቁጥሮች a[3i]፣ a[3i+1]፣ a[3i+2] የግራፉን ጠርዝ በ a[3i] በተቆጠሩት ጫፎች መካከል ይገልፃል። እና a[3i+1]፣ በቅደም ተከተል፣ እና እሴቱ a [3i+2] የዚህ ጠርዝ ክብደት ነው። እንዲህ ዓይነቱ ግራፍም ሊመራ ወይም ሊመራ ይችላል.

መያዣ (ለ)፡- ክብደት የሌለው ግራፍ፣ ኢንቲጀር ያልሆኑ የጠርዝ ክብደቶች

በአንድ ድርድር (ቬክተር) ውስጥ የተለያዩ ንጥረ ነገሮችን ማከማቸት የማይቻል ስለሆነ, ለምሳሌ የሚከተለውን ተግባራዊ ማድረግ ይቻላል. ግራፉ በቬክተር ጥንድ ውስጥ ይከማቻል, በዚህ ውስጥ የመጀመሪያው ቬክተር የግራፍ አጎራባች ቬክተር ክብደቱን ሳይገልጽ እና ሁለተኛው ቬክተር ተጓዳኝ ክብደትን ይይዛል (ለ C ++: std :: ጥንድ ሊተገበር ይችላል). ). ስለዚህ፣ በመጀመሪያው ቬክተር ኢንዴክሶች 2i፣ 2i+1 ስር ባሉ ጥንድ ጫፎች ለተገለፀው ጠርዝ ክብደቱ በሁለተኛው ቬክተር ኢንዴክስ i ስር ካለው ኤለመንት ጋር እኩል ይሆናል።

ደህና, ይህ ለምን አስፈለገ?

ደህና ፣ የእነዚህ መስመሮች ደራሲ ብዙ ችግሮችን ለመፍታት በጣም ጠቃሚ ሆኖ አግኝቶታል። ደህና ፣ ከመደበኛ እይታ ፣ የሚከተሉት ጥቅሞች ይኖራሉ ።

• የአጎራባች ቬክተር፣ ልክ እንደሌላው “ኢንሜሬቲቭ” መዋቅር፣ በጣም የታመቀ ነው፣ ከአጎራባች ማትሪክስ ያነሰ የማስታወስ ችሎታ ይይዛል (በተለይ ግራፎች) እና ለመተግበር በአንፃራዊነት ቀላል ነው።
• የግራፉ ጫፎች, በመርህ ደረጃ, በአሉታዊ ቁጥሮችም ምልክት ሊደረግባቸው ይችላል. እንዲህ ያለ “ጠማማነት” የሚያስፈልግ ቢሆንስ?
• ግራፎች የተለያዩ ክብደቶች (አዎንታዊ፣ አሉታዊ፣ እንዲያውም ዜሮ) ያላቸው በርካታ ጠርዞችን እና በርካታ ቀለበቶችን ሊይዝ ይችላል። እዚህ ምንም ገደቦች የሉም.
• እንዲሁም የተለያዩ ንብረቶችን ወደ ጠርዞች መመደብ ይችላሉ - ግን ለበለጠ መረጃ ክፍል 4ን ይመልከቱ ።

ነገር ግን, ይህ "ዝርዝር" በፍጥነት ወደ ጫፉ መድረስን እንደማይያመለክት መቀበል አለበት. እና እዚህ የአሶሺዬቲቭ አድጃሴንሲ ድርድር ወደ ማዳን ይመጣል, እሱም ከዚህ በታች ተብራርቷል.

3.2 አሶሺዬቲቭ ተጓዳኝ ድርድር

ስለዚህ, ወደ አንድ የተወሰነ ጠርዝ መድረስ, ክብደቱ እና ሌሎች ንብረቶቹ ለእኛ ወሳኝ ከሆኑ እና የማስታወሻ መስፈርቶች የአጎራባች ማትሪክስ እንድንጠቀም አይፈቅዱልንም, ከዚያም ይህን ችግር ለመፍታት የአጃቢ ቬክተርን እንዴት መቀየር እንደምንችል እናስብ. ስለዚህ ቁልፉ የግራፉ ጠርዝ ነው, እሱም እንደ የታዘዘ ጥንድ ቁጥሮች ሊገለጽ ይችላል. ይህ ምን ይመስላል? በአሶሺዬቲቭ ድርድር ውስጥ ቁልፍ አይደለም? እና, ከሆነ, ለምን ተግባራዊ አንሆንም? እያንዳንዱ ቁልፍ - የታዘዘ ጥንድ ኢንቲጀር - ከዋጋ ጋር የሚገናኝበት አሶሺዬቲቭ ድርድር ይኑረን - ኢንቲጀር ወይም የጠርዙን ክብደት የሚገልጽ እውነተኛ ቁጥር። በ C ++ ውስጥ, በ std :: የካርታ መያዣ ( std :: ካርታ ) ላይ በመመስረት ይህንን መዋቅር መተግበር ተገቢ ነው. , int> ወይም std :: ካርታ ፣ ድርብ>) ፣ ወይም std :: ባለብዙ ጫፎቹ ከተጠበቁ። ደህና ፣ ከ “ማትሪክስ” አወቃቀሮች ያነሰ ማህደረ ትውስታን የሚወስዱ ፣ ግራፎችን በበርካታ ዑደቶች እና ጠርዞች ሊገልጹ የሚችሉ እና የ vertex ቁጥሮች አሉታዊ ላለመሆን ጥብቅ መስፈርቶች የሉትም ግራፎችን ለማከማቸት መዋቅር አለን (አላውቅም ማን ያስፈልገዋል, ግን አሁንም).

4. የውሂብ አወቃቀሮች ሙሉ ናቸው, ግን የሆነ ነገር ይጎድላል

እና እውነት ነው: በርካታ ችግሮችን በሚፈታበት ጊዜ, አንዳንድ ባህሪያትን በግራፍ ጠርዞች ላይ መመደብ እና, በዚህ መሰረት, ማከማቸት ያስፈልገናል. እነዚህን ባህሪያት በማያሻማ ሁኔታ ወደ ኢንቲጀር መቀነስ ከተቻለ እንዲህ ያሉትን “ግራፎች ከተጨማሪ ባህሪያት ጋር” የተራዘሙ የአጃቢ ቬክተር እና የአሶሺዬቲቭ አጃቢነት ድርድርን በመጠቀም ማከማቸት ይቻላል።

እንግዲያው, ክብደት የሌለው ግራፍ ይኑረን, ለእያንዳንዱ ጠርዝ ለምሳሌ ያህል, 2 ተጨማሪ ባህሪያትን በኢንቲጀር የተገለጹትን ማከማቸት አስፈላጊ ነው. በዚህ ሁኔታ፣ የእሱን የአጎራባች ቬክተር እንደ የታዘዘ የ"ጥንድ" ሳይሆን "ኳርትት" የኢንቲጀር ስብስብ (a[2i]፣ a[2i+1]፣ a[2i+2]፣ ሀ [2i+3]…)፣ a[2i+2] እና a[2i+3] የተዛማጁን ጠርዝ ባህሪያት የሚወስኑበት። የጠርዙ ኢንቲጀር ክብደቶች ላለው ግራፍ፣ ትዕዛዙ በአጠቃላይ ተመሳሳይ ነው (ልዩነቱ ባህሪያቱ የጠርዙን ክብደት መከተላቸው ብቻ ነው እና በ a[2i+3] እና a[2i+4] አካላት ይገለጻል። , እና ጠርዝ እራሱ 4 ሳይሆን 5 የታዘዙ ቁጥሮች ይገለጻል). እና ኢንቲጀር ያልሆኑ የጠርዝ ክብደቶች ላለው ግራፍ ባህሪያቱ ባልተመዘነ ክፍል ውስጥ ሊፃፉ ይችላሉ።

የኢንቲጀር ጠርዝ ክብደቶች ላለው ግራፎች አሶሺዬቲቭ አጎራባች ድርድር ሲጠቀሙ እንደ አንድ ነጠላ ቁጥር ሳይሆን የቁጥሮች ድርድር (ቬክተር) ከጫፍ ክብደት በተጨማሪ ሌሎች አስፈላጊ የሆኑትን ሁሉ መግለጽ ይቻላል ዋና መለያ ጸባያት. በተመሳሳይ ጊዜ, ኢንቲጀር ያልሆኑ ክብደቶች ጉዳይ ላይ አንድ ችግር ተንሳፋፊ ነጥብ ቁጥር ጋር ምልክት መግለጽ አስፈላጊነት ይሆናል (አዎ, ይህ የማይመች ነው, ነገር ግን እንዲህ ያሉ ምልክቶች በጣም ብዙ ከሌሉ, እና ከሆነ አይደለም ከሆነ. በጣም “አታላይ” ድርብ አላዘጋጃቸውም፣ ከዚያ ምንም ላይሆን ይችላል) . ይህ ማለት በC++ የተራዘመ የአስተሳሰብ ትስስር ድርድር እንደሚከተለው ሊገለፅ ይችላል፡ std :: ካርታ , std :: vector> ወይም std :: ካርታ , std :: ቬክተር, በ "ቁልፍ-ዋጋ-ቬክተር" ውስጥ ያለው የመጀመሪያው እሴት የጠርዝ ክብደት ይሆናል, ከዚያም የባህሪያቱ አሃዛዊ ስያሜዎች ይገኛሉ.

ሥነ ጽሑፍ

ስለ ግራፎች እና ስልተ ቀመሮች በአጠቃላይ፡-

1. ኮርመን፣ ቶማስ ኤች.፣ ሌይሰርሰን፣ ቻርልስ I.፣ ሪቨስት፣ ሮናልድ ኤል.፣ ስታይን፣ ክሊፎርድ። አልጎሪዝም፡ ግንባታ እና ትንተና፡ 2ኛ እትም፡ ትራንስ. ከእንግሊዝኛ - ኤም.: ዊሊያምስ ማተሚያ ቤት, 2011.
2. ሀረሪ ፍራንክ. የግራፍ ቲዎሪ. ኤም: ሚር, 1973.
ስለእነዚህ ተመሳሳይ የቬክተር እና ተባባሪ ድርድር የደራሲው ዘገባ፡-
3. Chernoukhov S.A. ግራፎችን / ኤስኤ Chernouhov ለመወከል እና ለማከማቸት የአድጃሴንሲ ቬክተር እና አሶሺዬቲቭ ተጓዳኝ ድርድር። Adjacency ቬክተር እና የአጎራባች ካርታ እንደ የውሂብ አወቃቀሮች ግራፍ ለመወከል // የአለም አቀፍ ሳይንሳዊ እና ተግባራዊ ኮንፈረንስ መጣጥፎች ስብስብ "የፈጠራ እድገቶችን ውጤቶች የመተግበር ችግሮች እና እነሱን ለመፍታት መንገዶች" (ሳራቶቭ, ሴፕቴምበር 14.09.2019, 2019). – ስተርሊታማክ፡ ኤኤምአይ፣ 65፣ ገጽ. 69-XNUMX
በርዕሱ ላይ ጠቃሚ የመስመር ላይ ምንጮች፡-
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

ምንጭ: hab.com