توضح هذه المقالة إجراء تنفيذ DFS للشجرة أو الرسم البياني المتوفر.
كيف يتم تنفيذ Depth First Search أو DFS للرسم البياني في Java؟
يستخدم DFS بشكل أساسي للبحث في الرسم البياني من خلال زيارة كل فرع / قمة مرة واحدة بالضبط. يمكنه اكتشاف أو تحديد الدورات في رسم بياني يساعد في منع حالات الجمود. يمكن استخدامه لحل مشاكل الألغاز أو المتاهة. يمكن تنفيذ / استخدام DFS في خوارزميات الرسم البياني وزحف الويب وتصميم المحول البرمجي.
للحصول على شرح ، قم بزيارة الكود أدناه الخاص بـ Depth First Search أو DFS:
فصل رسم بياني {
خاص لينكدليست addNode [ ] ؛
خاص قيمة منطقية اجتاز [ ] ؛
رسم بياني ( int الرؤوس ) {
addNode = جديد لينكدليست [ الرؤوس ] ؛
اجتاز = جديد قيمة منطقية [ الرؤوس ] ؛
ل ( int أنا = 0 ؛ أنا < الرؤوس ؛ أنا ++ )
addNode [ أنا ] = جديد لينكدليست ( ) ؛
}
فارغ addEdge ( int src ، int يبدأ ) {
addNode [ src ] . يضيف ( يبدأ ) ؛
}
وصف الكود أعلاه:
- أولاً ، الفصل المسمى ' رسم بياني ' أنشئ. داخلها ، تعلن ' لينكدليست ' اسم الشيئ ' addNode [] 'ومصفوفة من النوع المنطقي تسمى' اجتاز [] '.
- بعد ذلك ، مرر الرؤوس لمنشئ ' رسم بياني فئة 'كمعامل.
- بعد ذلك ، ' ل 'حلقة للتنقل عبر كل عقدة من الفرع المحدد.
- في النهاية ، نوع الفراغ ' addEdge () 'يستخدم لإضافة الحواف بين الرؤوس. تأخذ هذه الوظيفة معلمتين: مصدر الرأس ' src 'ورأس الوجهة' يبدأ '.
بعد إنشاء الرسم البياني ، دعنا الآن نضيف رمز بحث العمق أولاً أو DFS للرسم البياني الذي تم إنشاؤه أعلاه:
فارغ DFS ( int قمة الرأس ) {
اجتاز [ قمة الرأس ] = حقيقي ؛
نظام . خارج . مطبعة ( قمة الرأس + '' ) ؛
التكرار هذا = addNode [ قمة الرأس ] . القائمة ( ) ؛
بينما ( هذا. hasNext ( ) ) {
int صفة = هذا. التالي ( ) ؛
لو ( ! اجتاز [ صفة ] )
DFS ( صفة ) ؛
}
}
في كتلة التعليمات البرمجية أعلاه:
- لأول مرة ' DFS () 'يتم إنشاء الوظيفة التي تحصل على' قمة الرأس 'كمعامل. تم وضع علامة على هذا الرأس على أنه تمت زيارته.
- بعد ذلك ، اطبع الرأس الذي تمت زيارته باستخدام ' out.print () ' طريقة.
- ثم أنشئ مثيلًا لـ ' التكرار 'الذي يتكرر فوق الرؤوس المجاورة للرأس الحالي.
- إذا لم تتم زيارة الرأس ، فإنه يمرر ذلك الرأس إلى ' DFS () ' وظيفة.
الآن ، دعونا ننشئ ' رئيسي() 'لإنشاء الرسم البياني ثم تطبيق DFS على ذلك:
عام ثابتة فارغ رئيسي ( خيط أرجس [ ] ) {
الرسم البياني ك = جديد رسم بياني ( 4 ) ؛
ك. addEdge ( 0 و 1 ) ؛
ك. addEdge ( 1 و 2 ) ؛
ك. addEdge ( 2 و 3 ) ؛
ك. addEdge ( 3 و 3 ) ؛
نظام . خارج . println ( 'التالي هو اجتياز العمق أولاً' ) ؛
ك. DFS ( 1 ) ؛
}
}
شرح الكود أعلاه:
- أولاً ، قم بإنشاء كائن ' ك 'من أجل' رسم بياني() ' طريقة.
- بعد ذلك ، ' addEdge () تستخدم طريقة ”لإضافة حواف بين رؤوس متعددة. هذا يخلق هيكل الرسم البياني لدينا.
- في النهاية ، قم بتمرير أي قيمة رأس كوسيطة إلى ' DFS () ' وظيفة. للعثور على مسار الرأس هذا من الجذر ، استخدم خوارزمية بحث العمق أولاً. على سبيل المثال ، قيمة ' 1 'إلى' DFS () ' وظيفة.
بعد نهاية مرحلة التجميع:
توضح المخرجات أنه تم تنفيذ بحث العمق أولاً بنجاح.
خاتمة
Depth First Search هو خوارزمية اجتياز الرسم البياني التي تشكل الأساس للعديد من خوارزميات الرسم البياني مثل العثور على أقصر مسار ، والأشجار الممتدة ، وتحليل الاتصال. يبدأ من عقدة الجذر ثم ينتقل إلى عمق أكبر قدر ممكن حتى عقدة المغادرة أو العقدة الأخيرة من ذلك الفرع قبل التراجع. لقد أوضحت هذه المقالة إجراء تنفيذ بحث العمق أولاً أو DFS للرسم البياني في Java.