پیدا کردن دور در گراف

از shaazzz
پرش به ناوبری پرش به جستجو

بررسی وجود دور در گراف و پیدا کردن آن با O(M)[ویرایش]

یک گراف(جهت دار یا بدون جهت) داریم که یال چندگانه و طوقه(Loop) ندارد. می خواهیم چک کنیم که آیا این گراف دور دارد یا نه؟! و اگر داشت ، تمام دورهای آن را پیدا کنیم. این مساله را میتوانیم با استفاده از جست و جوی عمق اول (DFS) و با O(M) که M تعداد یال های گراف است ، انجام دهیم.

الگوریتم[ویرایش]

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

پیاده سازی[ویرایش]

این پیاده سازی برای یک گراف جهت دار است.

int n;
vector<vector<int>> adj;
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;

bool dfs(int v) {
    color[v] = 1;
    for (int u : adj[v]) {
        if (color[u] == 0) {
            parent[u] = v;
            if (dfs(u))
                return true;
        } else if (color[u] == 1) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
    }
    color[v] = 2;
    return false;
}

void find_cycle() {
    color.assign(n, 0);
    parent.assign(n, -1);
    cycle_start = -1;

    for (int v = 0; v < n; v++) {
        if (dfs(v))
            break;
    }

    if (cycle_start == -1) {
        cout << "Acyclic" << endl;
    } else {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);
        reverse(cycle.begin(), cycle.end());

        cout << "Cycle found: ";
        for (int v : cycle)
            cout << v << " ";
        cout << endl;
    }
}