درخت اور گراف میں فرق
مواد
درخت اور گراف غیر لکیری اعداد و شمار کے ڈھانچے کے زمرے میں آتے ہیں جہاں درخت نسلی ڈھانچے میں نوڈس کے مابین تعلقات کی نمائندگی کرنے کا ایک نہایت مفید طریقہ پیش کرتا ہے اور گراف نیٹ ورک کے ماڈل کے بعد آتا ہے۔ درخت اور گراف کو اس حقیقت سے ممتاز کیا جاتا ہے کہ درختوں کا ڈھانچہ منسلک ہونا چاہئے اور اس میں کبھی چھلنی نہیں ہوسکتی ہے جب کہ گراف میں اس طرح کی کوئی پابندی نہیں ہے۔
غیر لکیری ڈیٹا ڈھانچہ ان عناصر کا ایک مجموعہ پر مشتمل ہوتا ہے جو ہوائی جہاز پر تقسیم ہوتے ہیں جس کا مطلب ہے کہ عناصر کے مابین اس طرح کا کوئی تسلسل نہیں ہے کیونکہ یہ لکیری ڈیٹا ڈھانچے میں موجود ہے۔
-
- موازنہ چارٹ
- تعریف
- کلیدی اختلافات
- نتیجہ اخذ کرنا
موازنہ چارٹ
| موازنہ کی بنیاد | درخت | گراف |
|---|---|---|
| راہ | صرف دو چوکوں کے درمیان ایک۔ | ایک سے زیادہ راستوں کی اجازت ہے۔ |
| جڑ نوڈ | اس میں بالکل ایک جڑ نوڈ ہے۔ | گراف میں جڑ کا نوڈ نہیں ہوتا ہے۔ |
| لوپس | کسی لوپ کی اجازت نہیں ہے۔ | گراف میں لوپس ہوسکتے ہیں۔ |
| پیچیدگی | کم پیچیدہ | نسبتا More زیادہ پیچیدہ |
| ٹراورسل تکنیک | پیشگی آرڈر ، انڈر آرڈر اور پوسٹ آرڈر۔ | پہلی چوڑائی اور گہرائی کی پہلی تلاش۔ |
| کناروں کی تعداد | n-1 (جہاں n نوڈس کی تعداد ہے) | وضاحت نہیں کی |
| ماڈل کی قسم | درجہ بندی | نیٹ ورک |
درخت کی تعریف
A درخت عام طور پر نوڈس کے طور پر کہا جاتا ہے اعداد و شمار کی اشیاء کا ایک محدود مجموعہ ہے. جیسا کہ یہ اوپر بتایا گیا ہے کہ درخت ایک غیر لکیری ڈیٹا ڈھانچہ ہے جو ڈیٹا آئٹم کو ترتیب سے ترتیب دیتا ہے۔ اس کا استعمال مختلف اعداد و شمار کے عناصر کے مابین ایک درجہ بندی کی ساخت کو ظاہر کرنے کے لئے کیا جاتا ہے اور اعداد و شمار کو ان شاخوں میں ترتیب دیتا ہے جو معلومات سے متعلق ہیں۔ درخت میں نئے کنارے کے اضافے کے نتیجے میں لوپ یا سرکٹ کی تشکیل ہوتی ہے۔
درختوں کی متعدد قسمیں ہیں جیسے بائنری ٹری ، بائنری سرچ ٹری ، اے وی ایل ٹری ، تھریڈڈ بائنری ٹری ، بی ٹری وغیرہ۔ ڈیٹا کمپریشن ، فائل اسٹوریج ، ریاضی کے اظہار میں ہیرا پھیری اور کھیل کے درخت درخت کی درخواست ہیں۔ ڈیٹا ڈھانچہ.
درخت کی خصوصیات:
- درخت کی چوٹی پر نامزد نوڈ ہے جو درخت کی جڑ کے طور پر جانا جاتا ہے۔
- باقی ڈیٹا آئٹمز کو ناجائز ذیلی حصوں میں تقسیم کیا گیا ہے جس کو سب ٹری کہتے ہیں۔
- درخت اونچائی میں نیچے کی طرف بڑھا ہوا ہے۔
- ایک درخت کو جڑنا چاہئے جس کا مطلب ہے کہ ایک جڑ سے دوسرے تمام نوڈس تک کا راستہ ہونا چاہئے۔
- اس میں کوئی لوپس نہیں ہوتا ہے۔
- ایک درخت میں N-1 کنارے ہیں۔
درختوں کے ساتھ متعدد اصطلاحات وابستہ ہیں جیسے ٹرمینل نوڈ ، کنارے ، سطح ، ڈگری ، گہرائی ، جنگل وغیرہ۔ ان شرائط میں ، ان میں سے کچھ ذیل میں بیان کی گئیں ہیں۔
- کنارہ - ایک لائن جو دو نوڈس کو جوڑتی ہے۔
- سطح - ایک درخت کو سطحوں میں اس طرح تقسیم کیا جاتا ہے کہ جڑ نوڈ 0 کی سطح پر ہوتا ہے۔ پھر ، اس کے فوری بچے 1 کی سطح پر ہوتے ہیں ، اور اس کے فوری بچے 2 کی سطح پر ہوتے ہیں اور اسی طرح ٹرمینل یا پتی کے نوڈ تک۔
- ڈگری - یہ کسی دیئے ہوئے درخت میں نوڈ کے ذیلی ذرات کی تعداد ہے۔
- گہرائی - یہ کسی درخت میں کسی بھی نوڈ کی زیادہ سے زیادہ سطح ہے اور اسے بھی جانا جاتا ہے اونچائی.
- ٹرمینل نوڈ - اعلی سطح کا نوڈ ٹرمینل نوڈ ہے جبکہ ٹرمینل اور روٹ نوڈ کے علاوہ دوسرے نوڈس غیر ٹرمینل نوڈس کے نام سے جانے جاتے ہیں۔
گراف کی تعریف
A گراف ایک ریاضی کی غیر لکیری ڈیٹا ڈھانچہ بھی ہے جو طرح طرح کی جسمانی ساخت کی نمائندگی کرسکتا ہے۔ اس میں عمودی گروہوں (یا نوڈس) کا ایک گروپ اور کناروں کا سیٹ ہوتا ہے جو دو چوٹیوں کو جوڑتا ہے۔ گراف میں عمودی نقطہ یا حلقوں کے طور پر نمائندگی کی جاتی ہے اور کناروں کو آرکس یا لائن حصوں کی طرح دکھایا جاتا ہے۔ ایک کنارے کی نمائندگی E (v، w) کے ذریعہ کی جاتی ہے جہاں v اور w کونے کے جوڑے ہوتے ہیں۔ سرکٹ یا منسلک گراف سے ایک کنارے کا خاتمہ ایک پیراگراف بناتا ہے جو درخت ہے۔
گراف کو مختلف قسموں میں درجہ بندی کیا گیا ہے جیسے ہدایت ، غیر ہدایت ، متصل ، غیر منسلک ، آسان اور کثیر گراف۔ کمپیوٹر نیٹ ورک ، ٹرانسپورٹیشن سسٹم ، سوشل نیٹ ورک گراف ، الیکٹریکل سرکٹس اور پروجیکٹ پلاننگ گراف ڈیٹا ڈھانچے کی کچھ ایپلی کیشنز ہیں۔ اس کے بطور نامی انتظامی تکنیک میں بھی کام کیا جاتا ہے PERT (پروگرام کی تشخیص اور جائزہ لینے کی تکنیک) اور سی پی ایم (اہم راستہ طریقہ) جس میں گراف ڈھانچے کا تجزیہ کیا جاتا ہے۔
گراف کی خصوصیات:
- کسی گراف میں ایک لمبے حصے کو کناروں کے استعمال سے کسی بھی دوسری چوٹی سے منسلک کیا جاسکتا ہے۔
- ایک کنارے کی ہدایت یا ہدایت کی جاسکتی ہے۔
- ایک کنارے وزن کیا جا سکتا ہے.
گراف میں بھی ہم متعدد اصطلاحات استعمال کرتے ہیں جیسے ملحقہ افقی ، راستہ ، سائیکل ، ڈگری ، منسلک گراف ، مکمل گراف ، وزنی گراف وغیرہ۔ آئیے ان میں سے کچھ شرائط کو سمجھیں۔
- متصل چوڑیاں اگر ایک کنارے (a، b) یا (b، a) ہو تو ایک عمو A سے عمودی b سے متصل ہے۔
- راہ - ایک بے ترتیب ورٹیکس ڈبلیو کا ایک راستہ ایک دوسرے سے ملنے والا سلسلہ ہے۔
- سائیکل - یہ ایک ایسا راستہ ہے جہاں پہلے اور آخری کونے ایک جیسے ہیں۔
- ڈگری - یہ ایک دہلیز پر کئی کناروں کا واقعہ ہے۔
- مربوط گراف - اگر کسی بے ترتیب ویردار سے لے کر کسی دوسرے دھارے تک جانے کا کوئی راستہ موجود ہے تو وہ گراف ایک مربوط گراف کے نام سے جانا جاتا ہے۔
- ایک درخت میں کسی بھی دو چوٹی کے درمیان صرف ایک ہی راستہ موجود ہے جب کہ گراف میں نوڈس کے بیچ ایک سمت اور دو طرفہ راستے ہوسکتے ہیں۔
- درخت میں ، بالکل ایک جڑ نوڈ ہے ، اور ہر بچے کے صرف ایک ہی والدین ہوسکتے ہیں۔ اس کے برخلاف ، گراف میں ، روٹ نوڈ کا کوئی تصور نہیں ہے۔
- درخت میں لوپ اور سیلف لوپس نہیں ہوسکتے ہیں جب کہ گراف میں لوپ اور سیلف لوپس ہوسکتے ہیں۔
- گراف زیادہ پیچیدہ ہیں کیونکہ اس میں لوپس اور سیلف لوپس ہوسکتے ہیں۔ اس کے برعکس ، گراف کے مقابلے میں درخت آسان ہیں۔
- درخت پری آرڈر ، ترتیب میں اور پوسٹ آرڈر تکنیکوں کا استعمال کرتے ہوئے گزرتا ہے۔ دوسری طرف ، گراف ٹراورسال کے ل we ، ہم بی ایف ایس (بریڈتھ فرسٹ سرچ) اور ڈی ایف ایس (گہرائی کی پہلی تلاش) استعمال کرتے ہیں۔
- ایک درخت میں N-1 کنارے ہوسکتے ہیں۔ اس کے برعکس ، گراف میں ، کناروں کی کوئی وضاحتی تعداد نہیں ہے ، اور یہ گراف پر منحصر ہے۔
- ایک درخت کا درجہ بندی کا ڈھانچہ ہوتا ہے جبکہ گراف کا نیٹ ورک ماڈل ہوتا ہے۔
نتیجہ اخذ کرنا
گراف اور درخت غیر لکیری اعداد و شمار کا ڈھانچہ ہے جو مختلف پیچیدہ مسائل کو حل کرنے کے لئے استعمال ہوتا ہے۔ ایک گراف چوٹیوں اور کناروں کا ایک گروپ ہے جہاں ایک کنارے ایک کونے کو ایک دوسرے کو جوڑتا ہے جب کہ ایک درخت کو کم سے کم منسلک گراف سمجھا جاتا ہے جس کو منسلک ہونا ضروری ہے اور اسے لوپوں سے آزاد ہونا چاہئے۔
