DFS و BFS والتراجع

هذه الأنماط هي مجموعة أدواتك لاستكشاف الأشجار والرسوم البيانية وتوليد جميع التوافيق الممكنة. تظهر في مجموعة واسعة من مسائل المقابلات.

DFS (البحث بالعمق أولاً)

DFS يستكشف بأعمق ما يمكن قبل التراجع. يستخدم مكدسًا (أو مكدس الاستدعاءات في التكرار).

متى تستخدم DFS:

• اجتيازات الأشجار (preorder, inorder, postorder)
• إيجاد المسارات في الرسوم البيانية
• المكونات المتصلة
• كشف الدورات

# عدد الجزر (DFS كلاسيكي)
def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # تحديد كمزار
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

# مجموع المسار في شجرة ثنائية
def has_path_sum(root, target_sum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target_sum
    return (has_path_sum(root.left, target_sum - root.val) or
            has_path_sum(root.right, target_sum - root.val))

BFS (البحث بالعرض أولاً)

BFS يستكشف مستوى بمستوى باستخدام طابور. يضمن أقصر مسار في الرسوم البيانية غير الموزونة.

متى تستخدم BFS:

• أقصر مسار (رسم بياني غير موزون)
• الاجتياز مستوى بمستوى
• مسائل الحد الأدنى من الخطوات/الحركات
• البحث عن أقرب جار

from collections import deque

# أقصر مسار في مصفوفة ثنائية
def shortest_path(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    queue = deque([(0, 0, 1)])  # (صف، عمود، مسافة)
    visited = {(0, 0)}
    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

    while queue:
        r, c, dist = queue.popleft()
        if r == n-1 and c == n-1:
            return dist
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    return -1

متى تختار DFS ومتى BFS

المعيار	DFS	BFS
أقصر مسار	لا (بشكل عام)	نعم (غير موزون)
استخدام الذاكرة	O(h) الارتفاع	O(w) العرض
التطبيق	تكرار أو مكدس	طابور
الأفضل للأشجار	مسائل المسارات	الاجتياز مستوى بمستوى
الأفضل للرسوم البيانية	المكونات المتصلة	أقصر مسافة

التراجع (Backtracking)

التراجع هو DFS مع لمسة: تبني حلاً تدريجيًا وتتخلى عنه ("تتراجع") عندما لا يمكن أن يؤدي لنتيجة صحيحة.

القالب:

def backtrack(candidates, path, result, start):
    if is_valid_solution(path):
        result.append(path[:])  # أضف نسخة
        return
    for i in range(start, len(candidates)):
        path.append(candidates[i])       # اختر
        backtrack(candidates, path, result, i + 1)  # استكشف
        path.pop()                        # ألغِ الاختيار (تراجع)

مسائل التراجع الكلاسيكية:

# المجموعات الفرعية: توليد جميع المجموعات الفرعية
def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

# التباديل
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    backtrack([], nums)
    return result

# N-Queens (الملكات الثمانية)
def solve_n_queens(n):
    result = []
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            board[row][col] = 'Q'
            backtrack(row+1, cols|{col}, diag1|{row-col}, diag2|{row+col}, board)
            board[row][col] = '.'
    board = [['.']*n for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return result

نصيحة للمقابلات: مسائل التراجع تتبع نمط "اختر، استكشف، ألغِ الاختيار". إذا تعرفت على هذا الهيكل، الحل يكتب نفسه.

---

التالي: النمط الذي يخيف معظم المرشحين: البرمجة الديناميكية. :::