الگوریتم جستجوی گراف (Graph Search Algorithms)

یه ابزار قدرتمنده که برای پیمایش و جستجوی اطلاعات تو ساختار های گراف استفاده میشه که دو تا الگوریتم پر کاربرد داره؛ BFS و DFS که اولی عالی برای پیدا کردن کوتاه ترین مسیره و دومی عالی برای چک کردن همه راه‌ها، حالا بیاید تا این موضوع رو بیشتر باز کنیم:


۱. جستجوی اول سطح (BFS)
فرض کن توی یه مهمونی هستی و دنبال دوستت می‌گردی. اول از همه نزدیک‌ترین آدم‌ها رو می‌بینی و می‌پرسی، بعدش میری سراغ کسانی که دورترن. اینطوری، تو همه رو به ترتیب از نزدیک به دور چک می‌کنی.
حالا کاربردش چیه؟ پیدا کردن کوتاه‌ترین مسیر از یک نقطه به نقطه دیگه در یک شبکه (مثل پیدا کردن کوتاه‌ترین راه توی یک نقشه).

مزایا
- برای پیدا کردن کوتاه‌ترین مسیر عالیه.
- نظم داره و اول همه نزدیک‌ها رو چک می‌کنه.

معایب
- اگه شبکه خیلی بزرگ باشه، ممکنه حافظه زیادی مصرف کنه.
- برای شبکه‌های خیلی بزرگ شاید زمان بیشتری بگیره.

۲. جستجوی اول عمق (DFS)
حالا دوباره فرض کن توی همون مهمونی هستی، ولی این بار تصمیم می‌گیری از یکی از درها وارد بشی و تا ته بری، هر اتاق رو چک کنی و اگه دوستت نبود، برگردی و بری سراغ اتاق بعدی. اینطوری همیشه تا ته میری بعد برمی‌گردی.
کاربرد؟ پیدا کردن همه مسیرهای ممکن و چک کردن کامل یک ساختار (مثل جستجو توی یه پرونده کامپیوتری برای پیدا کردن همه فایل‌ها).

مزایا:
- حافظه کمتری مصرف می‌کنه چون فقط مسیر فعلی رو توی حافظه نگه می‌داره.
- برای حل مسائل پیچیده که همه مسیرها باید بررسی بشن خیلی خوبه.

معایب:
- ممکنه به جایی برسه که مسیر بی‌نهایت طولانی بشه و زمان زیادی بگیره.
- لزوماً کوتاه‌ترین مسیر رو پیدا نمی‌کنه.

نکات بیشتر درباره BFS:

۱.گراف‌های وزن‌دار و بدون وزن:
- الگوریتم BFS معمولاً برای گراف‌های بدون وزن (یا گراف‌هایی که همه یال‌ها وزن یکسان دارن) به کار می‌ره. برای گراف‌های وزن‌دار، الگوریتم Dijkstra بیشتر استفاده می‌شه.

۲. پیدا کردن اجزای همبند:
- الگوریتم BFS می‌تونه برای پیدا کردن اجزای همبند (Connected Components) در یک گراف استفاده بشه. به این معنی که می‌تونیم بفهمیم کدوم قسمت‌های گراف به هم متصل هستن و کدوم‌ها مستقلن.

۳. پیدا کردن حلقه‌ها:
- با استفاده از BFS می‌تونیم حلقه‌ها یا چرخه‌ها (Cycles) در یک گراف رو تشخیص بدیم. اگه در طول جستجو به یک گره‌ای برسیم که قبلاً بازدید شده و همسایه هم باشه، این نشون‌دهنده وجود حلقه است.

۴. پیچیدگی زمانی و مکانی:
- پیچیدگی زمانی (Time Complexity): الگوریتم BFS زمانی برابر با $$O(V + E)$$ داره، که در اون $$V$$ تعداد گره‌ها و $$E$$ تعداد یال‌هاست.
- پیچیدگی مکانی (Space Complexity): الگوریتم BFS فضایی برابر با $$O(V)$$ مصرف می‌کنه، چون نیاز به ذخیره گره‌ها و وضعیت بازدید اونها داره.

5. کاربردهای دیگر:
- تحلیل شبکه‌های اجتماعی: برای پیدا کردن دوستان مشترک یا پیشنهاد دوستان جدید.
- پیدا کردن کوتاه‌ترین مسیر در بازی‌ها: مثل بازی‌های پازلی که باید راهی برای خروج پیدا کنی.
- حل مسائل جریان شبکه: مثل مسئله بیشینه جریان (Maximum Flow).

حالا اگه اطلاعات بیشتری می‌خواید بیایم یه مثال از جستجوی اول سطح (BFS) رو توی زبان سی پلاس پلاس پیاده‌سازی کنیم. فرض کن یه نقشه شهری داریم و می‌خواهیم کوتاه‌ترین مسیر رو از یک نقطه به نقطه دیگه پیدا کنیم. هر نقطه توی نقشه به عنوان یک گره و هر جاده به عنوان یال در نظر گرفته شده.

cpp
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// تابع BFS برای پیدا کردن کوتاه‌ترین مسیر در یک گراف
void BFS(const vector<vector<int>>& graph, int start, vector<int>& distance) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    distance[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[current] + 1;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // تعریف گراف به صورت یک لیست مجاورت (Adjacency List)
    vector<vector<int>> graph = {
        {1, 2},      // همسایه‌های گره 0
        {0, 3, 4},   // همسایه‌های گره 1
        {0, 4},      // همسایه‌های گره 2
        {1, 5},      // همسایه‌های گره 3
        {1, 2, 5},   // همسایه‌های گره 4
        {3, 4}       // همسایه‌های گره 5
    };

    int start = 0; // شروع از گره 0
    vector<int> distance(graph.size(), -1);
BFS(graph, start, distance);

    // چاپ فاصله‌ها از نقطه شروع
    for (int i = 0; i < distance.size(); ++i) {
        cout << &quotفاصله از &quot << start << &quot تا &quot << i << &quot برابر است با: &quot << distance[i] << endl;
    }

    return 0;
},

در این کد، ابتدا گراف به صورت یک لیست مجاورت (Adjacency List) تعریف شده که هر گره و همسایه‌هاش رو نشون می‌ده. بعدش با استفاده از الگوریتم BFS، فاصله هر گره از نقطه شروع حساب می‌شه. در نهایت فاصله‌ها چاپ می‌شن.
این مثال نشون می‌ده که چطوری می‌تونیم با استفاده از BFS توی یه نقشه شهری کوتاه‌ترین مسیرها رو پیدا کنیم.

امیدوارم این مطلب به دردت خورده باشه و مثل آخر همه بلاگ‌ها می‌خوام بگم اطلاعات این پست خیلی بیسیکه و اگه قصد دارید از این الگوریتم استفاده کنید دقیق مطالعه‌اش کنید.