ساختارهای غیرخطی شامل درخت‌ها (Trees) و گراف‌ها (Graphs) هستند. در واقع، یک درخت را می‌توان گرافی در نظر گرفت که هیچ چرخه‌ای ندارد. تنها تفاوت عمده بین این دو ساختار در هنگام استفاده از الگوها این است که برای گرافی که ممکن است شامل چرخه باشد، نیاز به یک مجموعه بازدید شده (visited set) دارید تا گره‌هایی را که قبلاً پیمایش کرده‌اید، پیگیری کنید.
الگوریتم‌هایی که برای حل مسائل ساختارهای غیرخطی استفاده می‌شوند، شامل جستجوی سطح اول و جستجوی عمق اول هستند:
۱. جستجوی سطح اول (Breadth-First Search - BFS)
BFS الگوریتمی است که برای پیمایش گره‌ها در یک گراف یا درخت به صورت سطح به سطح (level by level) استفاده می‌شود.
- مکانیسم: این الگوریتم از یک گره معین (که معمولاً ریشه نامیده می‌شود) شروع می‌کند و ابتدا تمام همسایگان مستقیم آن را کاوش می‌کند، قبل از اینکه به سراغ همسایگان همسایگان و الی آخر برود.
- ساختار داده مورد استفاده: BFS برای پیگیری گره‌هایی که باید کاوش شوند و برای حفظ ترتیب صحیح، از یک صف (Queue) استفاده می‌کند. صف ساختار داده‌ای است که بر اساس اصل “اولین ورودی، اولین خروجی” (First In, First Out) عمل می‌کند. این امر تضمین می‌کند که گره‌ها به ترتیب صحیح، از نزدیک‌ترین تا دورترین به ریشه، پیمایش می‌شوند.
- کاربرد اصلی: BFS الگوریتمی است که برای حل مسائلی که نیاز به کاوش لایه به لایه دارند، مانند یافتن کوتاه‌ترین مسیر (Shortest Path)، یا پیمایش سطح به سطح یک درخت دودویی (level order traversal) ایده‌آل است.
مثال: پیمایش سطح به سطح یک درخت دودویی
فرض کنید می‌خواهید مقادیر گره‌ها را سطح به سطح جمع‌آوری کنید.
- گره ریشه (root node) را به صف اضافه می‌کنید.
- برای هر سطح، تمام گره‌هایی را که در حال حاضر در صف هستند، پردازش می‌کنید.
- گره پردازش‌شده از صف حذف می‌شود و مقادیر آن به نتیجه اضافه می‌گردد.
- سپس، فرزندان چپ و راست آن گره (در صورت وجود) به صف اضافه می‌شوند تا در سطح بعدی پردازش شوند.
- این فرآیند تکرار می‌شود تا زمانی که صف خالی شود. این کار تضمین می‌کند که همه گره‌ها در یک سطح قبل از رفتن به سطح بعدی پیمایش شوند.
۲. جستجوی عمق اول (Depth-First Search - DFS)
DFS بر مبنای BFS ساخته شده است، اما ساختار را به شیوه متفاوتی کاوش می‌کند. در حالی که BFS بر کاوش سطح به سطح تمرکز دارد، DFS تا جایی که ممکن است در یک مسیر عمیق می‌شود، و سپس به عقب برگشته و مسیر بعدی را کاوش می‌کند.
- ساختار داده مورد استفاده: برخلاف BFS که از صف استفاده می‌کند، DFS از یک پشته (Stack) برای کاوش گره‌ها به شیوه عمق اول استفاده می‌کند.
- مکانیسم: شما در یک شاخه عمیق می‌شوید تا به انتهای آن برسید، سپس برمی‌گردید تا شاخه‌های دیگر را کاوش کنید. اغلب، پشته‌ای که DFS استفاده می‌کند همان پشته تماس (Call Stack) است، زیرا اکثر پیاده‌سازی‌های DFS از بازگشت (Recursion) استفاده می‌کنند.
- کاربرد اصلی: DFS برای مسائلی مناسب‌تر است که نیاز به کاوش تمام مسیرها یا بررسی هر پیکربندی ممکن دارند، مانند یافتن تمام مسیرها در یک درخت، جستجو برای یک شرط خاص در عمق ساختار، یا تشخیص چرخه‌ها.
- کارایی حافظه: ماهیت عمق اول DFS باعث می‌شود که در برخی موارد از نظر حافظه کارآمدتر باشد.
مثال: مسئله شمارش جزایر (Number of Islands)
این مسئله از شما می‌خواهد که تعداد جزایر موجود در یک شبکه دو بعدی را بشمارید، جایی که “۱” نشان‌دهنده خشکی و “۰” نشان‌دهنده آب است.
- شما شبکه را پیمایش می‌کنید و هر بار که با یک خشکی (‘1’) مواجه می‌شوید، متوجه می‌شوید که این شروع یک جزیره است.
- از آنجا، DFS را انجام می‌دهید تا تمام خشکی‌های متصل (همسایگان در چهار جهت) را تا جایی که می‌توانند عمیقاً کاوش کند.
- در حین DFS، هر سلول بازدید شده را با تغییر مقدار آن به “۰” علامت‌گذاری می‌کنید تا اطمینان حاصل شود که دوباره شمرده نمی‌شود.
- پس از بازدید از تمام سلول‌های متصل برای آن جزیره، شمارنده جزایر را افزایش داده و جستجو را در بقیه شبکه ادامه می‌دهید.
۳. پس‌گشت (Backtracking)
پس‌گشت در واقع صرفاً گسترشی از جستجوی عمق اول (DFS) است.
- تفاوت با DFS: در DFS، معمولاً ساختاری از پیش ساخته شده (مانند یک درخت یا گراف) را پیمایش می‌کنیم که گره‌ها و اتصالات آن تعریف شده‌اند. در الگوی پس‌گشت، اغلب باید درخت راه‌حل (Solution Tree) را خودتان بسازید، به ویژه در مسائل ترکیبی (combinatorial problems) که ساختار درخت به صراحت داده نشده و به صورت پویا در حین اتخاذ تصمیمات تولید می‌شود.
- مکانیسم: در پس‌گشت، شما تمام راه‌حل‌های ممکن را با اتخاذ یک سری تصمیمات کاوش می‌کنید. هر تصمیم یک گره در درخت را نشان می‌دهد. هنگامی که یک تصمیم منجر به بن‌بست می‌شود، به تصمیم قبلی باز می‌گردید (backtrack)، آن را لغو کرده و مسیر دیگری را امتحان می‌کنید.
این الگوها (BFS، DFS و Backtracking) ستون فقرات حل مسائل مرتبط با ساختارهای غیرخطی در مصاحبه‌های کدنویسی را تشکیل می‌دهند.