2 الخوارزميات الأساسية لإيجاد الحد الأدنى من الأشجار الممتدة

This post is also available in: English (الإنجليزية)

ضع في اعتبارك سيناريو شركة تلفزيون الكابل تمد الكابلات إلى منطقة جديدة. القيد في ذلك هو أنه يمكن أن يدفن الكبل فقط على طول مسارات معينة ، ثم سيكون هناك رسم بياني يمثل النقاط التي ترتبط بهذه المسارات.

قد تكون بعض هذه المسارات أكثر تكلفة ، لأنها أطول ، أو تتطلب دفن الكابل بشكل أعمق ؛ سيتم تمثيل هذه المسارات بحواف ذات أوزان أكبر.

ستكون الشجرة الممتدة لهذا الرسم البياني عبارة عن مجموعة فرعية من تلك المسارات التي لا تحتوي على دورات ولكنها لا تزال متصلة بكل منزل. قد يكون هناك العديد من الأشجار الممتدة الممكنة. الحد الأدنى للشجرة الممتدة هو الشجرة ذات التكلفة الإجمالية الأقل.

ما هو الحد الأدنى لشجرة الامتداد؟

الحد الأدنى للشجرة الممتدة هو شجرة. وهي تختلف عن الأشجار الأخرى من حيث أنها تقلل إجمالي الأوزان المرتبطة بالحواف. اعتمادًا على شكل الرسم البياني ، قد يكون هناك أكثر من الحد الأدنى للشجرة الممتدة.

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

ما هي الحاجة لإيجاد الحد الأدنى من الأشجار الممتدة؟

يُطلق على عدد من المشكلات من نظرية الرسم البياني الحد الأدنى من مشكلات الشجرة الممتدة. في نظرية الرسم البياني ، الشجرة هي طريقة لربط جميع الرؤوس معًا ، بحيث يكون هناك مسار واحد بالضبط من أي رأس إلى أي رأس آخر للشجرة.

إذا كان الرسم البياني يمثل عددًا من المدن المتصلة بواسطة الطرق ، فيمكن للمرء تحديد عدد من الطرق ، بحيث يمكن الوصول إلى كل مدينة من بعضها البعض ، ولكن لا توجد أكثر من طريقة للتنقل من مدينة إلى أخرى.

يمكن أن يحتوي الرسم البياني على أكثر من شجرة ممتدة ، تمامًا مثلما قد يكون هناك أكثر من طريقة لتحديد الطرق بين المدن.

في معظم الأحيان ، يتم ترجيح الرسوم البيانية ؛ كل اتصال بين مدينتين له وزن. يمكن أن تكون المسافة أو تكلفة النقل أو وقت السفر.

الخوارزميات للعثور على الحد الأدنى من شجرة الامتداد

هناك نوعان من الخوارزميات الشهيرة للعثور على الحد الأدنى من شجرة الامتداد.

خوارزمية كروسال

يبني الشجرة الممتدة عن طريق إضافة حواف واحدة تلو الأخرى إلى شجرة ممتدة متنامية. تتبع خوارزمية Kruksal نهجًا جشعًا حيث تجد في كل تكرار حافة ذات وزن أقل وتضيفها إلى الشجرة الممتدة المتنامية.

خطوات في خوارزمية كروسال

• افرز حواف الرسم البياني وفقًا لأوزانها.
• ابدأ بإضافة الحواف إلى الحد الأدنى لشجرة الامتداد من الحافة ذات الوزن الأصغر حتى حافة الوزن الأكبر.
• أضف فقط الحواف التي لا تشكل دورة ، الحواف التي تربط المكونات غير المتصلة فقط.

في خوارزمية Kruskal ، في كل تكرار ، سنختار الحافة ذات الوزن الأقل. لذلك ، سنبدأ بالحافة الأقل ترجيحًا أولاً ، أي الحواف ذات الوزن 1.

بعد ذلك ، سنختار ثاني أدنى حافة مرجحة ، أي حافة بوزن 2. لاحظ أن هاتين الحافتين منفصلتان تمامًا.

الآن ، ستكون الحافة التالية هي ثالث أدنى حافة مرجحة ، أي حافة بوزن 3 ، والتي تربط بين الجزأين المنفصلين في الرسم البياني.

الآن ، لا يُسمح لنا باختيار الحافة بوزن 4 ، مما سيخلق دورة ولا يمكننا الحصول على أي دورات. لذلك سنختار الحافة الخامسة الأقل ترجيحًا ، أي الحافة بالوزن 5. الآن ستنشئ الحافتان الأخريان دورات لذلك سنتجاهلها. في النهاية ، ينتهي بنا الأمر مع الحد الأدنى من الشجرة الممتدة مع التكلفة الإجمالية 11 (= 1 2 3 5).

برنامج C لتطبيق خوارزمية Kruksal

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];

void initialize()
{
    for(int i = 0;i < MAX;++i)
        id[i] = i;
}

int root(int x)
{
    while(id[x] != x)
    {
        id[x] = id[id[x]];
        x = id[x];
    }
    return x;
}

void union1(int x, int y)
{
    int p = root(x);
    int q = root(y);
    id[p] = id[q];
}

long long kruskal(pair<long long, pair<int, int> > p[])
{
    int x, y;
    long long cost, minimumCost = 0;
    for(int i = 0;i < edges;++i)
    {
        // Selecting edges one by one in increasing order from the beginning
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;
        // Check if the selected edge is creating a cycle or not
        if(root(x) != root(y))
        {
            minimumCost += cost;
            union1(x, y);
        }    
    }
    return minimumCost;
}

int main()
{
    int x, y;
    long long weight, cost, minimumCost;
    initialize();
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        p[i] = make_pair(weight, make_pair(x, y));
    }
    // Sort the edges in the ascending order
    sort(p, p + edges);
    minimumCost = kruskal(p);
    cout << minimumCost << endl;
    return 0;
}

خوارزمية بريم

تستخدم خوارزمية Prim أيضًا نهج Greedy للعثور على الحد الأدنى من الشجرة الممتدة. في خوارزمية Prim ، ننمي الشجرة الممتدة من موضع البداية. على عكس الحافة في Kruskal ، نضيف الرأس إلى الشجرة الممتدة المتنامية في Prim’s.

خطوات في خوارزمية Prim

• احتفظ بمجموعتين منفصلتين من الرؤوس. يحتوي أحدهما على رؤوس موجودة في الشجرة الممتدة النامية والآخر غير الموجود في الشجرة الممتدة المتنامية.
• حدد أرخص قمة متصلة بالشجرة الممتدة المتنامية وليست في الشجرة الممتدة المتنامية وأضفها إلى الشجرة الممتدة المتنامية. يمكن القيام بذلك باستخدام قوائم انتظار الأولوية. أدخل القمم المتصلة بالشجرة الممتدة المتنامية في قائمة انتظار الأولوية.
• تحقق من الدورات. للقيام بذلك ، حدد العقد التي تم تحديدها بالفعل وأدخل فقط تلك العقد في قائمة انتظار الأولوية التي لم يتم وضع علامة عليها.

في خوارزمية Prim ، سنبدأ بعقدة عشوائية (لا يهم أي منها) ونضع علامة عليها. في كل تكرار ، سنضع علامة على رأس جديد مجاور للرأس الذي حددناه بالفعل.

كخوارزمية جشعة ، ستقوم خوارزمية Prim بتحديد الحافة الأرخص وتحديد القمة. لذلك سنختار ببساطة الحافة بالوزن 1. في التكرار التالي ، لدينا ثلاثة خيارات ، حواف بالوزن 2 و 3 و 4. لذلك ، سوف نختار الحافة بالوزن 2 ونضع علامة على الرأس. الآن مرة أخرى لدينا ثلاثة خيارات ، حواف بالوزن 3 و 4 و 5. لكن لا يمكننا اختيار حافة بوزن 3 لأنها تخلق دورة. لذلك سنختار الحافة بوزن 4 وننتهي مع الحد الأدنى للشجرة الممتدة للتكلفة الإجمالية 7 (= 1+ 2+ 4).

برنامج C لتنفيذ خوارزمية Prim

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>

using namespace std;
const int MAX = 1e4 + 5;
typedef pair<long long, int> PII;
bool marked[MAX];
vector <PII> adj[MAX];

long long prim(int x)
{
    priority_queue<PII, vector<PII>, greater<PII> > Q;
    int y;
    long long minimumCost = 0;
    PII p;
    Q.push(make_pair(0, x));
    while(!Q.empty())
    {
        // Select the edge with minimum weight
        p = Q.top();
        Q.pop();
        x = p.second;
        // Checking for cycle
        if(marked[x] == true)
            continue;
        minimumCost += p.first;
        marked[x] = true;
        for(int i = 0;i < adj[x].size();++i)
        {
            y = adj[x][i].second;
            if(marked[y] == false)
                Q.push(adj[x][i]);
        }
    }
    return minimumCost;
}

int main()
{
    int nodes, edges, x, y;
    long long weight, minimumCost;
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        adj[x].push_back(make_pair(weight, y));
        adj[y].push_back(make_pair(weight, x));
    }
    // Selecting 1 as the starting node
    minimumCost = prim(1);
    cout << minimumCost << endl;
    return 0;
}

تطبيقات الحد الأدنى من الأشجار الممتدة

• يتم استخدام الحد الأدنى من الأشجار الممتدة لتصميمات الشبكات (مثل شبكات الهاتف أو الكابلات). يتم استخدامها أيضًا لإيجاد حلول تقريبية للمشكلات الرياضية المعقدة مثل “مشكلة بائع متجول”.
• التحليل العنقودي
• تتبع الوجه والتحقق منه في الوقت الفعلي (أي تحديد موقع الوجوه البشرية في دفق فيديو)
• بروتوكولات في علوم الكمبيوتر لتجنب دورات الشبكة
• تسجيل الصور المعتمد على الانتروبيا
• التردد (إضافة ضوضاء بيضاء إلى التسجيل الرقمي لتقليل التشويه)
• التعرف على خط اليد
• تقطيع الصورة

Image Credit: Background vector created by vector_corp – www.freepik.com