جستجوی عمیق DFS


DFS DFS
جستجوی اول عمق (DFS) یکی از الگوریتم های اصلی در نمودارها است. الگوریتم در O(N + M) اجرا می شود.
 
الگوریتم
برای شروع، از بالا شروع می کنیم، فرزندان این بالا را در نظر می گیریم و اگر هرگز آنها را وارد نکرده ایم، DFS را از آنها شروع می کنیم.


Training problem

DFS: شروع (C++)

DFS DFS
جستجوی اول عمق (DFS) یکی از الگوریتم های اصلی در نمودارها است. الگوریتم در O(N + M) اجرا می شود.
 
الگوریتم
برای شروع، از بالا شروع می کنیم، فرزندان این بالا را در نظر می گیریم و اگر هرگز آنها را وارد نکرده ایم، DFS را از آنها شروع می کنیم.


Training problem

DFS: Start (Python)

گراف دو بخشی
 
گراف دو قسمتی - نموداری که رئوس آن را می توان به دو مجموعه تقسیم کرد به طوری که هر یال آن را به هم متصل کند رئوس از مجموعه های مختلف.


اغلب در زمینه نمودارهای دوبخشی، از مفهوم رنگ ها رئوس استفاده می شود. تقسیم یک نمودار به دو قسمت، رنگ آمیزی رأس آن با دو رنگ متفاوت نامیده می شود. هر لبه باید رئوس رنگ متفاوتی را به هم متصل کند.

DFS. 
 

الگوریتم

نقاشی را از یک راس دلخواه شروع می کنیم که آن را با رنگ دلخواه رنگ می کنیم.
هنگام عبور از هر لبه، رأس بعدی را به رنگ مخالف رنگ کنید.
اگر در حین تکرار بر روی رئوس همسایه، راسی را پیدا کنیم که قبلاً به همان رنگ راس فعلی رنگ شده است، در این صورت یک چرخه فرد در نمودار وجود دارد که به این معنی است که دو قسمتی نیست.

Training problem

نمودار دو بخشی

الگوریتم را می توان به صورت زیر توصیف کرد:
یک نمودار جهت دار با n رأس و m یال داده می شود. لازم است که رئوس آن را مجدداً شماره گذاری کنید به گونه ای که هر یال از یک راس با عدد کمتر به یک راس با عدد بالاتر منتهی شود.
به عبارت دیگر، لازم است جایگشتی از رئوس (ترتیب توپولوژیکی) مطابق با ترتیب داده شده توسط تمام یال های نمودار پیدا شود.
ما از جستجوی عمق (dfs(v))
استفاده خواهیم کرد
اگر راس خود را در زمان خروج از \(dfs(v)\)  به ابتدای لیست اضافه کنیم، در پایان در این لیست شما یک مرتب سازی توپولوژیکی دریافت می کنید.
بنابراین، مرتب‌سازی توپولوژیکی مورد نظر — این به ترتیب نزولی زمان خروج مرتب شده است.

Training problem

مرتب سازی توپولوژیکی