చెట్టు మరియు గ్రాఫ్ మధ్య వ్యత్యాసం
విషయము
- పోలిక చార్ట్
- చెట్టు యొక్క నిర్వచనం
- చెట్టు యొక్క లక్షణాలు:
- గ్రాఫ్ యొక్క నిర్వచనం
- గ్రాఫ్ యొక్క లక్షణాలు:
- ముగింపు
చెట్టు మరియు గ్రాఫ్ నాన్-లీనియర్ డేటా స్ట్రక్చర్ యొక్క వర్గంలోకి వస్తాయి, ఇక్కడ చెట్టు క్రమానుగత నిర్మాణంలో నోడ్‌ల మధ్య సంబంధాన్ని సూచించడానికి చాలా ఉపయోగకరమైన మార్గాన్ని అందిస్తుంది మరియు గ్రాఫ్ నెట్వర్క్ మోడల్‌ను అనుసరిస్తుంది. చెట్టు నిర్మాణం తప్పనిసరిగా అనుసంధానించబడి ఉండాలి మరియు గ్రాఫ్‌లో అలాంటి పరిమితులు లేనప్పుడు ఎప్పటికీ ఉచ్చులు ఉండకూడదు అనే వాస్తవం ద్వారా చెట్టు మరియు గ్రాఫ్ వేరు చేయబడతాయి.
నాన్-లీనియర్ డేటా స్ట్రక్చర్ ఒక విమానంలో పంపిణీ చేయబడిన మూలకాల సమాహారాన్ని కలిగి ఉంటుంది, అంటే సరళ డేటా నిర్మాణంలో మూలకాల మధ్య అలాంటి క్రమం లేదు.
-
- పోలిక చార్ట్
- నిర్వచనం
- కీ తేడాలు
- ముగింపు
పోలిక చార్ట్
| పోలిక కోసం ఆధారం | ట్రీ | గ్రాఫ్ |
|---|---|---|
| మార్గం | రెండు శీర్షాల మధ్య ఒకటి మాత్రమే. | ఒకటి కంటే ఎక్కువ మార్గాలు అనుమతించబడతాయి. |
| రూట్ నోడ్ | ఇది ఖచ్చితంగా ఒక రూట్ నోడ్ కలిగి ఉంది. | గ్రాఫ్‌కు రూట్ నోడ్ లేదు. |
| లూప్స్ | ఉచ్చులు అనుమతించబడవు. | గ్రాఫ్‌లో ఉచ్చులు ఉండవచ్చు. |
| సంక్లిష్టత | తక్కువ సంక్లిష్టమైనది | తులనాత్మకంగా మరింత క్లిష్టంగా ఉంటుంది |
| ట్రావెర్సల్ టెక్నిక్స్ | ప్రీ-ఆర్డర్, ఇన్-ఆర్డర్ మరియు పోస్ట్-ఆర్డర్. | వెడల్పు-మొదటి శోధన మరియు లోతు-మొదటి శోధన. |
| అంచుల సంఖ్య | n-1 (ఇక్కడ n అనేది నోడ్‌ల సంఖ్య) | వివరించబడలేదు |
| మోడల్ రకం | క్రమానుగత | నెట్వర్క్ |
చెట్టు యొక్క నిర్వచనం
ఒక చెట్టు సాధారణంగా నోడ్స్ అని పిలువబడే డేటా అంశాల పరిమిత సేకరణ. చెట్టు అనేది నాన్-లీనియర్ డేటా స్ట్రక్చర్ అని పైన పేర్కొన్నట్లుగా, ఇది డేటా ఐటెమ్‌లను క్రమబద్ధీకరించిన క్రమంలో అమర్చుతుంది. ఇది వివిధ డేటా మూలకాల మధ్య క్రమానుగత నిర్మాణాన్ని చూపించడానికి ఉపయోగించబడుతుంది మరియు డేటాను సమాచారానికి సంబంధించిన శాఖలుగా నిర్వహిస్తుంది. చెట్టులో కొత్త అంచుని చేర్చడం వల్ల లూప్ లేదా సర్క్యూట్ ఏర్పడుతుంది.
బైనరీ ట్రీ, బైనరీ సెర్చ్ ట్రీ, ఎవిఎల్ ట్రీ, థ్రెడ్ బైనరీ ట్రీ, బి-ట్రీ వంటి అనేక రకాల చెట్లు ఉన్నాయి. డేటా కంప్రెషన్, ఫైల్ స్టోరేజ్, అంకగణిత వ్యక్తీకరణ యొక్క తారుమారు మరియు గేమ్ ట్రీలు చెట్టు యొక్క కొన్ని అనువర్తనాలు డేటా నిర్మాణం.
చెట్టు యొక్క లక్షణాలు:
- చెట్టు యొక్క మూలంగా పిలువబడే చెట్టు పైభాగంలో నియమించబడిన నోడ్ ఉంది.
- మిగిలిన డేటా ఐటెమ్‌లను సబ్‌ట్రీగా సూచించే డిజాయింట్ ఉపసమితులుగా విభజించారు.
- చెట్టు దిగువ భాగంలో ఎత్తులో విస్తరించింది.
- ఒక చెట్టు కనెక్ట్ అయి ఉండాలి అంటే ఒక రూట్ నుండి మిగతా నోడ్ లకు ఒక మార్గం ఉండాలి.
- దీనిలో ఉచ్చులు లేవు.
- ఒక చెట్టుకు n-1 అంచులు ఉన్నాయి.
టెర్మినల్ నోడ్, ఎడ్జ్, లెవల్, డిగ్రీ, డెప్త్, ఫారెస్ట్ వంటి చెట్లతో సంబంధం ఉన్న వివిధ పదాలు ఉన్నాయి. ఆ నిబంధనలలో, వాటిలో కొన్ని క్రింద వివరించబడ్డాయి.
- ఎడ్జ్ - రెండు నోడ్లను కలిపే పంక్తి.
- స్థాయి - ఒక చెట్టు రూట్ నోడ్ 0 స్థాయిలో ఉండే విధంగా స్థాయిలుగా విభజించబడింది. అప్పుడు, దాని తక్షణ పిల్లలు స్థాయి 1 వద్ద ఉంటారు, మరియు దాని తక్షణ పిల్లలు 2 వ స్థాయిలో ఉంటారు మరియు టెర్మినల్ లేదా లీఫ్ నోడ్ వరకు ఉంటారు.
- డిగ్రీ - ఇది ఇచ్చిన చెట్టులోని నోడ్ యొక్క సబ్‌ట్రీల సంఖ్య.
- లోతు - ఇది ఇచ్చిన చెట్టులోని ఏదైనా నోడ్ యొక్క గరిష్ట స్థాయి మరియు దీనిని కూడా పిలుస్తారు ఎత్తు.
- టెర్మినల్ నోడ్ - అత్యధిక స్థాయి నోడ్ టెర్మినల్ నోడ్ అయితే టెర్మినల్ మరియు రూట్ నోడ్ మినహా ఇతర నోడ్లను నాన్-టెర్మినల్ నోడ్స్ అంటారు.
గ్రాఫ్ యొక్క నిర్వచనం
ఒక గ్రాఫ్ వివిధ రకాల భౌతిక నిర్మాణాన్ని సూచించగల గణిత నాన్-లీనియర్ డేటా నిర్మాణం కూడా. ఇది రెండు శీర్షాలను అనుసంధానించే శీర్షాల సమూహం (లేదా నోడ్లు) మరియు అంచుల సమితిని కలిగి ఉంటుంది. గ్రాఫ్‌లోని శీర్షాలు పాయింట్ లేదా సర్కిల్‌లుగా సూచించబడతాయి మరియు అంచులు ఆర్క్ లేదా లైన్ సెగ్మెంట్లుగా చూపబడతాయి. ఒక అంచు E (v, w) చేత సూచించబడుతుంది, ఇక్కడ v మరియు w లు శీర్షాల జతలు. సర్క్యూట్ లేదా కనెక్ట్ చేయబడిన గ్రాఫ్ నుండి అంచుని తీసివేయడం ఒక చెట్టు అయిన సబ్‌గ్రాఫ్‌ను సృష్టిస్తుంది.
గ్రాఫ్‌లు డైరెక్ట్, నాన్-డైరెక్ట్, కనెక్ట్, కనెక్ట్ కాని, సింపుల్ మరియు మల్టీ గ్రాఫ్ వంటి వివిధ వర్గాలుగా వర్గీకరించబడ్డాయి. కంప్యూటర్ నెట్వర్క్, ట్రాన్స్‌పోర్ట్ సిస్టమ్, సోషల్ నెట్వర్క్ గ్రాఫ్, ఎలక్ట్రికల్ సర్క్యూట్లు మరియు ప్రాజెక్ట్ ప్లానింగ్ గ్రాఫ్ డేటా స్ట్రక్చర్ యొక్క కొన్ని అనువర్తనాలు. ఇది పేరు పెట్టబడిన నిర్వహణ పద్ధతిలో కూడా ఉపయోగించబడుతుంది సజీవ (ప్రోగ్రామ్ మూల్యాంకనం మరియు సమీక్ష సాంకేతికత) మరియు సిపిఎం (క్లిష్టమైన మార్గం పద్ధతి) దీనిలో గ్రాఫ్ నిర్మాణం విశ్లేషించబడుతుంది.
గ్రాఫ్ యొక్క లక్షణాలు:
- గ్రాఫ్‌లోని శీర్షాన్ని అంచులను ఉపయోగించి ఎన్ని ఇతర శీర్షాలతో అయినా కనెక్ట్ చేయవచ్చు.
- ఒక అంచుని ద్వి మళ్ళించవచ్చు లేదా దర్శకత్వం చేయవచ్చు.
- ఒక అంచు బరువు ఉంటుంది.
గ్రాఫ్‌లో కూడా మేము ప్రక్కనే ఉన్న శీర్షాలు, మార్గం, చక్రం, డిగ్రీ, కనెక్ట్ చేయబడిన గ్రాఫ్, పూర్తి గ్రాఫ్, వెయిటెడ్ గ్రాఫ్ వంటి వివిధ పదాలను ఉపయోగిస్తాము. ఈ పదాలలో కొన్నింటిని అర్థం చేసుకుందాం.
- ప్రక్కనే ఉన్న శీర్షాలు - అంచు (ఎ, బి) లేదా (బి, ఎ) ఉంటే శీర్షం బి ప్రక్కనే ఉంటుంది.
- మార్గం - యాదృచ్ఛిక శీర్షం w నుండి ఒక మార్గం శీర్షాల ప్రక్కనే ఉన్న క్రమం.
- చక్రం - ఇది మొదటి మరియు చివరి శీర్షాలు ఒకే విధంగా ఉండే మార్గం.
- డిగ్రీ - ఇది శీర్షంలో అనేక అంచుల సంఘటన.
- కనెక్ట్ చేయబడిన గ్రాఫ్ - యాదృచ్ఛిక శీర్షం నుండి మరే ఇతర శీర్షానికి ఒక మార్గం ఉంటే, ఆ గ్రాఫ్‌ను కనెక్ట్ చేసిన గ్రాఫ్ అంటారు.
- ఒక చెట్టులో ఏదైనా రెండు శీర్షాల మధ్య ఒకే ఒక మార్గం ఉంటుంది, అయితే గ్రాఫ్ నోడ్‌ల మధ్య ఏకదిశాత్మక మరియు ద్వి దిశాత్మక మార్గాలను కలిగి ఉంటుంది.
- చెట్టులో, సరిగ్గా ఒక రూట్ నోడ్ ఉంది, మరియు ప్రతి బిడ్డకు ఒకే తల్లిదండ్రులు మాత్రమే ఉంటారు. దీనికి విరుద్ధంగా, గ్రాఫ్‌లో, రూట్ నోడ్ యొక్క భావన లేదు.
- ఒక చెట్టుకు ఉచ్చులు మరియు స్వీయ-ఉచ్చులు ఉండవు, గ్రాఫ్ ఉచ్చులు మరియు స్వీయ-ఉచ్చులను కలిగి ఉంటుంది.
- గ్రాఫ్‌లు మరింత క్లిష్టంగా ఉంటాయి ఎందుకంటే దీనికి ఉచ్చులు మరియు స్వీయ-ఉచ్చులు ఉంటాయి. దీనికి విరుద్ధంగా, గ్రాఫ్‌తో పోలిస్తే చెట్లు సరళమైనవి.
- ప్రీ-ఆర్డర్, ఇన్-ఆర్డర్ మరియు పోస్ట్-ఆర్డర్ పద్ధతులను ఉపయోగించి చెట్టు ప్రయాణిస్తుంది. మరోవైపు, గ్రాఫ్ ట్రావెర్సల్ కోసం, మేము BFS (వెడల్పు మొదటి శోధన) మరియు DFS (లోతు మొదటి శోధన) ఉపయోగిస్తాము.
- ఒక చెట్టు n-1 అంచులను కలిగి ఉంటుంది. దీనికి విరుద్ధంగా, గ్రాఫ్‌లో, ముందే నిర్వచించిన అంచుల సంఖ్య లేదు మరియు ఇది గ్రాఫ్‌పై ఆధారపడి ఉంటుంది.
- ఒక చెట్టుకు క్రమానుగత నిర్మాణం ఉంటుంది, అయితే గ్రాఫ్‌కు నెట్వర్క్ మోడల్ ఉంటుంది.
ముగింపు
గ్రాఫ్ మరియు ట్రీ అనేది నాన్-లీనియర్ డేటా స్ట్రక్చర్, ఇది వివిధ సంక్లిష్ట సమస్యలను పరిష్కరించడానికి ఉపయోగిస్తారు. గ్రాఫ్ అనేది శీర్షాలు మరియు అంచుల సమూహం, ఇక్కడ ఒక అంచు ఒక జత శీర్షాలను కలుపుతుంది, అయితే చెట్టును కనిష్టంగా అనుసంధానించబడిన గ్రాఫ్‌గా పరిగణిస్తారు, ఇది కనెక్ట్ అయి ఉచ్చులు లేకుండా ఉండాలి.
