البحث بالعرض على الرسوم البيانية العامة

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

BFS فكرتها: “زر كل شيء يبعد خطوة واحدة، ثم خطوتين، ثم ثلاث خطوات…”

فيمَ تُستخدم BFS

BFS هي الأداة الأساسية لـ:

  • أقصر مسار في رسم بياني غير موزون (تكلفة كل حرف = 1)
  • أقل عدد أحرف من عقدة البداية إلى جميع العقد
  • التحقق من الاتصال / المكونات

الضمان الأساسي:

في رسم بياني غير موزون، BFS تجد أقصر مسافة (أقل عدد أحرف) من عقدة البداية إلى كل عقدة يمكن الوصول لها.

الفكرة الأساسية: طابور + زيارة / مسافة

BFS تستخدم طابوراً (queue) حتى تتم معالجة العقد بنفس ترتيب اكتشافها.

نحافظ على:

  • dist[v] = أقصر عدد أحرف من البداية إلى v
    (-1 يعني “لم تتم زيارتها بعد”)

الخطوات:

  1. ضع عقدة البداية في الطابور، واجعل dist[start] = 0

  2. اسحب عقدة v من الطابور

  3. لكل جار to:

    • إذا كان غير مُزار، اجعل dist[to] = dist[v] + 1
    • ثم أدخله إلى الطابور

بما أن الطابور يعالج الطبقات الأقرب أولاً، فأول مرة تزور فيها عقدة تكون مضمونة عبر أقصر مسار.

التنفيذ

نفترض قائمة مجاورات:

int n;
vector<int> g[n];

BFS من مصدر واحد:

vector<int> dist(n, -1);
queue<int> q;

int s = 0;
dist[s] = 0;
q.push(s);

while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int to : g[v]) {
        if (dist[to] != -1) continue;     // already visited
        dist[to] = dist[v] + 1;
        q.push(to);
    }
}

الآن dist[v] تكون:

  • 0 لعقدة البداية
  • 1 للعقد التي تبعد حرفاً واحداً
  • 2 للعقد التي تبعد حرفين
  • …إلخ
  • -1 إذا كانت غير قابلة للوصول من s

حدس “الطبقات” في BFS (لماذا تعمل أقصر المسارات)

عند تشغيل BFS:

  • الطابور يحتوي أولاً على جميع العقد ذات المسافة 0
  • ثم يكبر ليضم جميع العقد ذات المسافة 1
  • ثم جميع العقد ذات المسافة 2
  • …

لذلك إذا تم اكتشاف to من v، فأول مرة تضبط فيها dist[to] لابد أن تكون dist[v] + 1، و v أصلاً في أبكر طبقة ممكنة يمكنها الوصول إليه.

لهذا السبب BFS تعطي أقصر المسارات في الرسوم البيانية غير الموزونة.

استخراج أقصر مسار فعلياً (ليس فقط المسافة)

خزن parent[to] عند اكتشاف to.

vector<int> dist(n, -1), parent(n, -1);
queue<int> q;

int s = 0;
dist[s] = 0;
q.push(s);

while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int to : g[v]) {
        if (dist[to] != -1) continue;
        dist[to] = dist[v] + 1;
        parent[to] = v;
        q.push(to);
    }
}

إعادة بناء المسار من s إلى t:

vector<int> path;
int t = 7;
if (dist[t] != -1) {
    for (int v = t; v != -1; v = parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());
}

BFS مقابل DFS (فرق عملي)

  • DFS ممتازة لـ:

    • استكشاف البنية
    • كشف الدورات
    • المكونات المتصلة
    • الفرز الطوبولوجي (في الرسوم الموجهة اللا دورية)

  • BFS ممتازة لـ:

    • أقصر المسارات في الرسوم غير الموزونة
    • مسائل “أقل عدد خطوات”
    • الاستكشاف طبقة بطبقة

ملخص سريع

  • BFS تستخدم طابوراً (queue)
  • تزور العقد بترتيب مسافة متزايدة من البداية
  • تعطي أطوال أقصر المسارات في الرسوم غير الموزونة
  • باستخدام parent[] يمكنك إعادة بناء أقصر مسار