అందరికీ నమస్కారం.
ఈ నోట్‌లో, కంప్యూటర్ సైన్స్‌లో గ్రాఫ్‌లను నిల్వ చేయడానికి ఉపయోగించే ప్రధాన డేటా స్ట్రక్చర్‌లను జాబితా చేయాలని నేను నిర్ణయించుకున్నాను మరియు నా కోసం ఏదో ఒకవిధంగా “స్ఫటికీకరించిన” అలాంటి మరికొన్ని నిర్మాణాల గురించి కూడా మాట్లాడుతాను.
కాబట్టి, ప్రారంభిద్దాం. కానీ మొదటి నుండి కాదు - గ్రాఫ్ అంటే ఏమిటో మరియు అవి ఏమిటో మనందరికీ ఇప్పటికే తెలుసునని నేను అనుకుంటున్నాను (దర్శకత్వం, నిర్దేశించబడినది, వెయిటెడ్, వెయిటెడ్, బహుళ అంచులు మరియు లూప్‌లతో లేదా లేకుండా).
కనుక మనము వెళ్దాము. “గ్రాఫ్ స్టోరేజ్” కోసం డేటా స్ట్రక్చర్‌ల కోసం మనకు ఏ ఎంపికలు ఉన్నాయి?
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 (గ్రాఫ్ యొక్క శీర్షాల సంఖ్య ప్రకారం) మూలకాలు అదే శ్రేణి యొక్క ప్రారంభ సూచికలను కలిగి ఉంటాయి, దీని నుండి ఇవ్వబడిన దానికి ప్రక్కనే ఉన్న అన్ని శీర్షాలు వరుసగా వ్రాయబడతాయి.
ఇక్కడ నేను చాలా అర్థమయ్యే (నాకు) వివరణను కనుగొన్నాను:
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 చూడండి.
అయితే, ఈ "జాబితా" అంచుకు త్వరిత ప్రాప్తిని సూచించదని అంగీకరించాలి. మరియు ఇక్కడ అసోసియేటివ్ అడ్జసెన్సీ అర్రే రెస్క్యూకి వస్తుంది, ఇది క్రింద చర్చించబడింది.
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:: వెక్టర్, దీనిలో "కీ-విలువ-వెక్టార్"లో మొదటి విలువ అంచు యొక్క బరువుగా ఉంటుంది, ఆపై దాని లక్షణాల యొక్క సంఖ్యాపరమైన హోదాలు ఉంటాయి.
సాహిత్యం:
సాధారణంగా గ్రాఫ్‌లు మరియు అల్గారిథమ్‌ల గురించి:
1. కోర్మెన్, థామస్ హెచ్., లీజర్సన్, చార్లెస్ I., రివెస్ట్, రోనాల్డ్ ఎల్., స్టెయిన్, క్లిఫోర్డ్. అల్గోరిథంలు: నిర్మాణం మరియు విశ్లేషణ, 2వ ఎడిషన్: ట్రాన్స్. ఇంగ్లీష్ నుండి – M.: విలియమ్స్ పబ్లిషింగ్ హౌస్, 2011.
2. హరారి ఫ్రాంక్. గ్రాఫ్ సిద్ధాంతం. M.: మీర్, 1973.
ఇదే వెక్టార్ మరియు అనుబంధ శ్రేణి అనుబంధాల గురించి రచయిత యొక్క నివేదిక:
3. చెర్నౌఖోవ్ S.A. గ్రాఫ్‌లు / SA చెర్నౌహోవ్‌ను సూచించడానికి మరియు నిల్వ చేయడానికి అడ్జసెన్సీ వెక్టర్ మరియు అనుబంధ ప్రక్కనే ఉన్న శ్రేణి. గ్రాఫ్‌ను సూచించడానికి డేటా స్ట్రక్చర్‌లుగా ప్రక్కనే ఉన్న వెక్టర్ మరియు ప్రక్కనే ఉన్న మ్యాప్ // ఇంటర్నేషనల్ సైంటిఫిక్ అండ్ ప్రాక్టికల్ కాన్ఫరెన్స్ యొక్క కథనాల సేకరణ “వినూత్న పరిణామాల ఫలితాలు మరియు వాటిని పరిష్కరించే మార్గాలను అమలు చేయడంలో సమస్యలు” (సరతోవ్, సెప్టెంబర్ 14.09.2019, 2019). – స్టెర్లిటామాక్: AMI, 65, p. 69-XNUMX
అంశంపై ఉపయోగకరమైన ఆన్‌లైన్ మూలాలు:
4.
5.
మూలం: www.habr.com