DFS & nbsp؛ DFS
يعد بحث العمق الأول ( DFS ) أحد الخوارزميات الرئيسية في الرسوم البيانية. تعمل الخوارزمية في O (N + M) .
نبسب ؛
الخوارزمية
بادئ ذي بدء ، نبدأ من الأعلى ، ونفكر في أطفال هذا الجزء العلوي ، وإذا لم نقم بإدخالهم مطلقًا ، فسنبدأ منهم DFS .
|
DFS & nbsp؛ DFS
يعد بحث العمق الأول ( DFS ) أحد الخوارزميات الرئيسية في الرسوم البيانية. تعمل الخوارزمية في O (N + M) .
نبسب ؛
الخوارزمية
بادئ ذي بدء ، نبدأ من الأعلى ، ونفكر في أطفال هذا الجزء العلوي ، وإذا لم نقم بإدخالهم مطلقًا ، فسنبدأ منهم DFS .
|
رسم بياني ثنائي الأجزاء
نبسب ؛
رسم بياني ثنائي الأجزاء - رسم بياني يمكن تقسيم رؤوسه إلى مجموعتين بحيث تربط كل حافة الرؤوس من مجموعات مختلفة.
في كثير من الأحيان في سياق الرسوم البيانية ثنائية الأجزاء ، يتم استخدام مفهوم & nbsp؛ الألوان & nbsp؛ القمم. يسمى تقسيم الرسم البياني إلى قسمين & nbsp؛ تلوين & nbsp؛ رؤوسه بلونين مختلفين. يجب أن تربط كل حافة رؤوس بلون مختلف.
DFS . & nbsp؛
على & nbsp؛
الخوارزمية
نبدأ الرسم من قمة عشوائية ، نرسمها بلون عشوائي.
عند المرور على طول كل حافة ، قم بطلاء الرأس التالي باللون المعاكس.
إذا وجدنا أثناء التكرار على الرؤوس المجاورة رأسًا مرسومًا بالفعل بنفس لون الرأس الحالي ، فهناك دورة فردية في الرسم البياني ، مما يعني أنه ليس ثنائيًا.
|
يمكن وصف الخوارزمية على النحو التالي:
إعطاء رسم بياني موجه برؤوس n وحواف m. مطلوب إعادة ترقيم رؤوسها بطريقة تؤدي بها كل حافة من قمة ذات رقم أقل إلى قمة ذات رأس أعلى.
بعبارة أخرى ، مطلوب إيجاد تبديل للرؤوس (ترتيب طوبولوجي) يتوافق مع الترتيب الذي تقدمه جميع حواف الرسم البياني.
سنستخدم بحث العمق أولاً (dfs (v))
إذا أضفنا رأسنا إلى بداية القائمة وقت الخروج من & nbsp؛ \ (dfs (v) \) & nbsp ؛، ثم في النهاية في هذه القائمة تحصل على تصنيف طوبولوجي.
وهكذا ، النوع الطوبولوجي المطلوب & [مدش] ؛ يتم ترتيب ذلك بترتيب تنازلي لأوقات الخروج.
|