كيف تقترح المنصات أصدقاءك؟ تحليل عملي لتفوق خوارزمية BFS على الـ Graph

كيف تسبب الاختيار الخاطئ لخوارزمية البحث بالعمق (DFS) في استهلاك جنوني للذاكرة واقتراح أصدقاء من قارات أخرى، وكيف أنقذ التحول نحو خوارزمية البحث بالعرض (BFS) النظام ووفر حلاً معمارياً ذكياً ومستقراً لبناء ميزة "أشخاص قد تعرفهم".

بيئة العمل والمتطلبات التقنية

كنت أحدق في سجلات الخادم في وقت متأخر من ليلة الخميس. طلب المدير المنتج بناء ميزة "أشخاص قد تعرفهم" (People You May Know) لشبكة التواصل الاجتماعي الخاصة بنا. قلت لنفسي وقتها: "الأمر مجرد تنقل في شبكة من المستخدمين (Graph Traversal)، سأستخدم خوارزمية البحث بالعمق المعتادة وانتهى الأمر".

كان هذا خطأً فادحاً.

خلال دقائق من تشغيل الكود المبدئي، ارتفع استهلاك الذاكرة بشكل جنوني، وبدأت الخوارزمية تقترح على المستخدمين أشخاصاً من قارات أخرى يبعدون عنهم بـ 50 مستوى من الاتصالات، متجاهلة تماماً الأصدقاء المشتركين في الدائرة القريبة! السبب؟ خوارزمية البحث بالعمق كانت تغوص في مسار واحد حتى نهايته، وتتجاهل الطبقات القريبة. هنا أدركت ضرورة التحول المعماري نحو خوارزمية البحث بالعرض. في هذه المقالة، سأشاركك كيف أعدنا هندسة هذه الميزة بالكامل.

تمثيل البيانات: هندسة الرسم البياني

قبل أن نتمكن من البحث، احتجنا إلى بناء هيكل بيانات يمثل شبكة المستخدمين والاتصالات بينهم. أفضل طريقة لتمثيل ذلك في Python هي باستخدام قوائم الجوار (Adjacency List).

graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['F'],
  'F': []
}

في هذا الكود، استخدمنا Dictionary لتمثيل الرسم البياني. كل مفتاح (Key) يمثل عقدة (Node)، والقيمة (Value) هي قائمة تحتوي على العقد المجاورة.

هذا الأسلوب يوفر كفاءة عالية في استهلاك الذاكرة مقارنة بمصفوفة الجوار (Adjacency Matrix)، حيث نقوم فقط بتخزين الاتصالات الفعلية.

من الناحية المعمارية، البحث عن جيران أي عقدة يتم بتعقيد زمني \mathcal{O}(1) بفضل آلية عمل الـ Hash Maps التي يعتمد عليها الـ Dictionary في بايثون.

البحث بالعرض: استكشاف الطبقات القريبة أولاً

بما أننا نبحث عن أصدقاء الأصدقاء (الدرجة الثانية أو الثالثة)، كان الحل هو Breadth-First Search أو اختصاراً BFS. الخوارزمية تستكشف الشبكة طبقة بطبقة وتعتمد على بنية Queue بنظام FIFO (الأول دخولاً هو الأول خروجاً). هذا يجعلها الخيار الأمثل لإيجاد أقصر مسار (Shortest Path).

from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)
    
    print("BFS Traversal Order:")
    while queue:
        current_node = queue.popleft()
        print(current_node, end=" -> ")
        
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

نبدأ السطر الأول باستدعاء deque. استخدمنا طابوراً مزدوجاً لأنه مصمم خصيصاً لعمليات الإضافة والسحب السريعة.

قمنا بتعريف visited كـ Set بدلاً من List لأن التحقق من وجود عنصر داخل Set يتم بتعقيد \mathcal{O}(1)، مما يحمينا من الدورات اللانهائية.

حلقة while queue: تضمن استمرار العمل حتى يتم فحص كل العقد المطلوبة. نستخدم popleft() لسحب العقدة الحالية، ثم نمر على جميع جيرانها.

إذا لم تتم زيارة الجار، نضيفه إلى الـ Set فوراً ثم نضعه في نهاية الـ Queue ليتم فحصه في الطبقة التالية. هذا يضمن بقاءنا في الدوائر القريبة أولاً.

البحث بالعمق: متى نحتاجه حقاً؟

في المقابل، تعمل خوارزمية Depth-First Search أو DFS بأسلوب الغوص العميق (Backtracking). فهي تتبع فرعاً واحداً حتى نهايته قبل أن تتراجع للبحث في فروع أخرى. تعتمد الخوارزمية إما على الـ Recursion أو بنية Stack بنظام LIFO (الأخير دخولاً هو الأول خروجاً).

هذا المفهوم مذهل في تطبيقات محددة كحل المتاهات، واكتشاف المسارات المغلقة، وحتى في بناء محركات الشطرنج، حيث يجب تحليل سيناريو حركة معين حتى نهايته باستهلاك ذاكرة أقل مقارنة بـ BFS الذي يحاول حفظ كل الاحتمالات.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=" -> ")
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

هنا نستخدم مبدأ الاستدعاء الذاتي (Recursion). في السطر الأول، قمنا بتعريف visited=None لمعالجة مشكلة الاحتفاظ بالمتغيرات الافتراضية القابلة للتعديل (Mutable Default Arguments) في بايثون.

عند زيارة أي عقدة، نقوم بطباعتها، ثم نبدأ حلقة للمرور على جيرانها. السحر الحقيقي يحدث داخل الـ if؛ فبمجرد إيجاد جار لم تتم زيارتة, نستدعي الدالة dfs داخله فوراً متجاهلين بقية الجيران مؤقتاً!

هذا يضع استدعاء الدالة الجديد فوق القديم في مكدس استدعاءات النظام (Call Stack)، مما يفسر الغوص العميق للمسارات. كلا الخوارزميتين بالمناسبة تمتلكان تعقيداً زمنياً متطابقاً \mathcal{O}(V + E) حيث V تمثل العقد (Vertices) و E الحواف (Edges).

محاكي الويب: السيطرة على عمق البحث

لتوضيح قوة التحكم في الطبقات التي يمنحها لنا BFS، دعنا نبني مشروعاً مصغراً لمحاكي ويب (Mini Web Crawler). في هذا المثال، نريد تتبع الروابط، لكننا لا نريد فهرسة الإنترنت بالكامل والانهيار، بل نريد التوقف عند "عمق" محدد.

from collections import deque

internet = {
    "google.com": ["wikipedia.org", "medium.com"],
    "wikipedia.org": ["foo.com", "bar.org"],
    "medium.com": ["google.com"], 
    "foo.com": [],
    "bar.org": ["end.net"],
    "end.net": []
}

def crawl_internet(start_url, max_depth):
    queue = deque([ (start_url, 0) ])
    visited = set([start_url])
    
    while queue:
        current_url, depth = queue.popleft()
        if depth > max_depth:
            continue
            
        print(f"Found: {current_url} at depth {depth}")
        
        if depth < max_depth:
            for link in internet.get(current_url, []):
                if link not in visited:
                    visited.add(link)
                    queue.append((link, depth + 1))

في هذا التصميم شبكة الإنترنت هي مجرد Dictionary كبير. داخل دالة crawl_internet، قمنا بتغيير نوع البيانات المخزنة داخل الـ deque لتصبح Tuple تحتوي على مسار الرابط وعمقه (start_url, 0).

عند سحب العنصر بـ ()popleft، نقوم بفك حزمته (Unpacking) إلى current_url و depth.

الشرط if depth > max_depth يعمل كمكابح طوارئ لحماية الذاكرة. أثناء إضافة الروابط المجاورة، نقوم بتمرير depth + 1 للطابور. هذا يضمن عدم غوص محاكي الويب في روابط لا نهائية ويحجم الاستهلاك للموارد.

تطوير الكود

الخاتمة

كتابة الخوارزميات ليست مجرد تمارين هي قرارات تحدد مصير خوادمك في بيئة الإنتاج الحقيقية.

اختيارنا لخوارزمية BFS لميزة "أشخاص قد تعرفهم" أنقذ النظام من الانهيار لأننا احترمنا طبيعة المشكلة وبحثنا في الدوائر القريبة. في المقابل، يظل DFS سلاحاً فتاكاً عندما تحتاج لاختبار مسارات كاملة من البداية للنهاية. البرمجة الجيدة تعتمد على فهم "متى" تستخدم الأداة وليس فقط "كيف" تكتبها.

كيف كنتم ستعالجتم مشكلة اكتشاف الأصدقاء في مشاريعكم؟ شاركني رأيك أو حلك للتحدي في التعليقات!