الفرق بين الشجرة والرسم البياني
المحتوى
تندرج الشجرة والرسم البياني ضمن فئة بنية البيانات غير الخطية حيث توفر الشجرة طريقة مفيدة للغاية لتمثيل العلاقة بين العقد في بنية هرمية والرسم البياني يتبع نموذج الشبكة. يتم التمييز بين الشجرة والرسم البياني من خلال حقيقة أن بنية الشجرة يجب أن تكون متصلاً ولا يمكن أن تحتوي على حلقات بينما لا توجد قيود في هذا الرسم البياني.
تتكون بنية البيانات غير الخطية من مجموعة من العناصر التي يتم توزيعها على المستوى ، مما يعني عدم وجود تسلسل بين العناصر كما هو موجود في بنية البيانات الخطية.
-
- رسم بياني للمقارنة
- فريف
- الاختلافات الرئيسية
- استنتاج
رسم بياني للمقارنة
| أساس للمقارنة | شجرة | رسم بياني |
|---|---|---|
| مسار | واحد فقط بين اثنين من القمم. | أكثر من مسار مسموح به. |
| عقدة الجذر | لديها بالضبط عقدة واحدة الجذر. | الرسم البياني ليس لديه عقدة الجذر. |
| الحلقات | لا توجد حلقات مسموح بها. | الرسم البياني يمكن أن يكون الحلقات. |
| تعقيد | أقل تعقيدا | أكثر تعقيدا نسبيا |
| تقنيات عبور | قبل النظام ، في النظام وبعد الطلب. | البحث المتسع والبحث العميق. |
| عدد الحواف | n-1 (حيث n هو عدد العقد) | غير معرف |
| نوع النموذج | الهرمية | شبكة الاتصال |
تعريف الشجرة
ا شجرة هي مجموعة محدودة من عناصر البيانات التي تسمى عادةً بالعقد. كما ذكر أعلاه ، فإن الشجرة هي بنية بيانات غير خطية تقوم بترتيب عناصر البيانات بترتيب فرز. يتم استخدامه لإظهار بنية هرمية بين عناصر البيانات المختلفة وتنظيم البيانات في فروع تربط المعلومات. تؤدي إضافة حافة جديدة في شجرة إلى تشكيل حلقة أو دائرة.
هناك عدة أنواع من الأشجار مثل شجرة ثنائية ، وشجرة بحث ثنائية ، وشجرة AVL ، وشجرة ثنائية مترابطة ، وشجرة B ، وما إلى ذلك. ضغط البيانات ، وتخزين الملفات ، والتعامل مع التعبير الحسابي وأشجار اللعبة هي بعض من تطبيق الشجرة هيكل البيانات.
خصائص الشجرة:
- هناك عقدة مخصصة في أعلى الشجرة تعرف باسم جذر الشجرة.
- تنقسم عناصر البيانات المتبقية إلى مجموعات فرعية منفصلة تشير إلى الشجرة الفرعية.
- يتم توسيع الشجرة في الارتفاع نحو القاع.
- يجب أن تكون الشجرة متصلة مما يعني أنه يجب أن يكون هناك مسار من جذر واحد إلى جميع العقد الأخرى.
- لا يحتوي على أي حلقات.
- الشجرة لها حواف n-1.
هناك العديد من المصطلحات المرتبطة بالأشجار مثل العقدة الطرفية ، الحافة ، المستوى ، الدرجة ، العمق ، الغابة ، إلخ. من بين هذه المصطلحات ، بعضها موصوف أدناه.
- حافة - خط يربط بين العقدتين.
- مستوى - يتم تقسيم الشجرة إلى مستويات بحيث تكون عقدة الجذر عند المستوى 0. ثم ، يكون أولادها المباشرين في المستوى 1 ، وأطفالها المباشرين في المستوى 2 وهكذا إلى العقدة الطرفية أو الورقة.
- الدرجة العلمية - هو عدد الأشجار الفرعية للعقدة في شجرة معينة.
- عمق - هو الحد الأقصى لمستوى أي عقدة في شجرة معينة والمعروف أيضًا باسم ارتفاع.
- العقدة الطرفية - أعلى مستوى من العقدة هو العقدة الطرفية بينما تُعرف العقد الأخرى باستثناء العقدة الطرفية والجذر بالعقد غير الطرفية.
تعريف الرسم البياني
ا رسم بياني هو أيضًا هيكل بيانات غير خطي رياضي يمكنه تمثيل أنواع مختلفة من التركيب المادي. يتكون من مجموعة من القمم (أو العقد) ومجموعة من الحواف التي تربط بين القمتين. يتم تمثيل الرؤوس على الرسم البياني كنقطة أو دوائر وتظهر الحواف كأقواس أو مقاطع خطية. يمثل الحافة E (v ، w) حيث v و w هما أزواج القمم. تؤدي إزالة الحافة من دائرة أو رسم بياني متصل إلى إنشاء رسم فرعي يمثل شجرة.
يتم تصنيف الرسوم البيانية في فئات مختلفة مثل الموجهات ، غير الموجهة ، المتصلة ، غير المتصلة ، بسيطة ومتعددة الرسم البياني. شبكة الكمبيوتر ، ونظام النقل ، والرسم البياني للشبكة الاجتماعية ، والدوائر الكهربائية وتخطيط المشاريع هي بعض من تطبيقات هيكل بيانات الرسم البياني. وهي تستخدم أيضا في تقنية الإدارة اسمه بيرت (تقييم البرنامج وتقنية المراجعة) و CPM (طريقة المسار الحرج) التي يتم فيها تحليل بنية الرسم البياني.
خصائص الرسم البياني:
- يمكن توصيل رأس في رسم بياني بأي عدد من الرؤوس الأخرى باستخدام الحواف.
- يمكن توجيه الحافة أو توجيهها.
- يمكن ترجيح حافة.
في الرسم البياني أيضًا ، نستخدم مصطلحات مختلفة مثل الرؤوس المجاورة والمسار والدورة والدرجة والرسم البياني المتصل والرسم البياني الكامل والرسم البياني المرجح ، إلخ. دعونا نفهم بعضًا من هذه المصطلحات.
- القمم المجاورة - توجد قمة (a) بجوار قمة (ب) إذا كان هناك حافة (أ ، ب) أو (ب ، أ).
- مسار - المسار من قمة عشوائية w هو سلسلة متجاورة من القمم.
- دورة - إنه طريق تتشابه فيه القمم الأولى والأخيرة.
- الدرجة العلمية - هو عدد من حواف الحادث على قمة الرأس.
- الرسم البياني المتصل - إذا كان هناك مسار من قمة عشوائية إلى أي قمة أخرى ، فإن هذا الرسم البياني يعرف باسم الرسم البياني المتصل.
- في شجرة ، يوجد مسار واحد فقط بين أي رأسين ، بينما يمكن أن يحتوي الرسم البياني على مسارات أحادية الاتجاه وثنائية الاتجاه بين العقد.
- في الشجرة ، هناك عقدة جذرية واحدة تمامًا ، ويمكن لكل طفل أن يكون له أصل واحد فقط. في مقابل الرسم البياني ، لا يوجد مفهوم لعقدة الجذر.
- لا يمكن أن تحتوي الشجرة على حلقات وحلقات ذاتية بينما يمكن أن تحتوي الشجرة على حلقات وحلقات ذاتية.
- الرسوم البيانية أكثر تعقيدًا حيث يمكن أن تحتوي على حلقات وحلقات ذاتية. في المقابل ، الأشجار بسيطة بالمقارنة مع الرسم البياني.
- يتم عبور الشجرة باستخدام تقنيات الترتيب المسبق والترتيب وما بعد الطلب. من ناحية أخرى ، بالنسبة لاجتياز الرسم البياني ، نستخدم BFS (البحث المتسع الأول) و DFS (البحث المتعمق الأول).
- يمكن أن تحتوي الشجرة على حواف n-1. على العكس من ذلك ، في الرسم البياني ، لا يوجد عدد محدد مسبقًا من الحواف ، ويعتمد على الرسم البياني.
- تحتوي الشجرة على بنية هرمية بينما يحتوي الرسم البياني على نموذج شبكة.
استنتاج
الرسم البياني وشجرة هي بنية البيانات غير الخطية التي يتم استخدامها لحل مختلف المشاكل المعقدة. الرسم البياني عبارة عن مجموعة من الرؤوس والحواف حيث تقوم الحافة بتوصيل زوج من الرؤوس بينما تعتبر الشجرة رسمًا بيانيًا متصل بأدنى حد ويجب توصيله وخالية من الحلقات.
