This wiki has no edits or logs made within the last 45 days, therefore it is marked as inactive. If you would like to prevent this wiki from being closed, please start showing signs of activity here. If there are no signs of this wiki being used within the next 15 days, this wiki may be closed per the Dormancy Policy. This wiki will then be eligible for adoption by another user. If not adopted and still inactive 135 days from now, this wiki will become eligible for deletion. Please be sure to familiarize yourself with Miraheze's Dormancy Policy. If you are a bureaucrat, you can go to Special:ManageWiki and uncheck "inactive" yourself. If you have any other questions or concerns, please don't hesitate to ask at Stewards' noticeboard.

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

از 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;
    }
}