الگوی جستوجوی عمقی (DFS): کاوش درختها و گرافها
پایتونClaude Sonnet 5خلاصهٔ کاملتر
فرانکو فرناندو تو آخرین قسمت از سری آموزش بازگشتیاش، الگوی DFS (جستوجوی عمقیاول) رو برای پیمایش درخت و گراف توضیح میده. ایدهٔ اصلی سادس: از یه گره شروع میکنی، تا جایی که میشه رو یه مسیر عمیق میری، و وقتی به بنبست رسیدی برمیگردی و مسیر دیگهرو امتحان میکنی.
سادهترین مثال، چککردن اینه که یه مقدار تو یه درخت دوتایی هست یا نه:
def contains(node, target):
if node is None:
return False
if node.value == target:
return True
return contains(node.left, target) or contains(node.right, target)اینجا پیچیدگی زمانی و فضایی هر دو O(n) هستن، چون تو بدترین حالت باید همهٔ گرهها رو ببینی و عمق پشتهٔ بازگشتی هم میتونه تا n بره.
وقتی از درخت بریم سراغ گراف، قضیه یه پیچیدگی جدید داره: امکان وجود حلقه. برای همین باید یه «سِت بازدیدشدهها» نگه داری و قبل از رفتن سراغ هر گره چک کنی که قبلاً بازدید شده یا نه، وگرنه ممکنه بیفتی تو یه حلقهٔ بینهایت. با این تکنیک، پیچیدگی زمانی میشه O(V+E).
اگه بخوای نه فقط یه مسیر، بلکه همهٔ مسیرهای ممکن بین دو گره رو پیدا کنی، باید بکترکینگ به کار ببری: گره رو قبل از بررسی همسایههاش به ست بازدیدشدهها اضافه کن، ولی بعدش که کارت باهاش تموم شد، حذفش کن؛ چون ممکنه تو مسیر دیگهای دوباره بهش نیاز داشته باشی. نکتهٔ جالب اینه که همین الگو رو میشه مستقیم رو ماتریسها هم پیاده کرد، بدون اینکه لازم باشه ماتریس رو تبدیل به گراف کنی؛ خونهها گرهان و خونههای همسایه، یال.
فرناندو میگه DFS بهترین انتخابه وقتی دنبال یه مسیر خاص میگردی، میخوای همهٔ مسیرهای ممکن رو لیست کنی، یا اصلاً مسئله رو میشه به شکل درخت یا گراف مدل کرد. در مقابل، BFS برای پیدا کردن کوتاهترین مسیر تو گراف بدون وزن مناسبتره. این مطلب همچنین به پایان سری ششقسمتیاش دربارهٔ الگوهای بازگشتی رسیده: تکرار، زیرمسئله، انتخاب، ترتیب، تقسیموغلبه و در نهایت DFS.
نکات کلیدی:
- DFS یعنی از یه گره شروع کنی، تا جای ممکن عمیق بری و سر بنبست برگردی
- برای درختها پیچیدگی O(n)ه؛ برای گراف باید یه ست بازدیدشدهها نگه داری تا تو حلقه نیفتی (O(V+E))
- برای پیدا کردن همهٔ مسیرها باید بکترکینگ کنی: گره رو بعد از بررسی از ست بازدیدشدهها حذف کنی
- ماتریسها رو هم میشه بدون تبدیل به گراف، مستقیم با DFS پیمایش کرد
- DFS برای پیداکردن/شمردن مسیر و بررسی رسیدنیبودن خوبه؛ BFS برای کوتاهترین مسیر بهتره
