Агуулгыг алгасах

Граф дахь холбоост компонентыг хайх

Бидэнд $n$ орой, $m$ ирмэгтэй чиглэлгүй граф $G$ өгөгдсөн. Бид түүн дэх бүх холбоост компонентыг олох ёстой, өөрөөр хэлбэл бүлэг бүрийн дотор орой бүрээс нөгөө орой руу нь хүрч болох ба өөр өөр бүлгүүдийн хооронд ямар ч зам байхгүй байхаар оройнуудыг хэд хэдэн бүлэгт хуваана.

Бодлогыг бодох алгоритм

  • Бодлогыг бодохын тулд бид гүнзгийрүүлэх хайлт эсвэл өргөнөөр эхлэх хайлт ашиглаж болно.

  • Үнэндээ бид цуврал DFS ажиллуулна: эхний удаа эхний оройноос эхлэх ба эхний холбоост компонент дахь бүх оройг тойрно (олно). Дараа нь бид үлдсэн оройнуудаас хамгийн эхний зочлоогүй оройг олж, түүн дээр гүнзгийрүүлэх хайлт ажиллуулснаар хоёр дахь холбоост компонентыг олно. Бүх оройд зочлох хүртэл ингэж үргэлжилнэ.

  • Энэ алгоритмын нийт асимптот ажиллах хугацаа $O(n + m)$ юм: үнэндээ энэ алгоритм нэг оройг хоёр удаа боловсруулахгүй бөгөөд энэ нь ирмэг бүрийг яг хоёр удаа (нэг үзүүрт нь болон нөгөө үзүүрт нь) харна гэсэн үг.

Implementation

int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;

void dfs(int v) {
    used[v] = true;
    comp.push_back(v);
    for (int u : adj[v]) {
        if (!used[u])
            dfs(u);
    }
}

void find_comps() {
    used.assign(n, false);
    for (int v = 0; v < n; ++v) {
        if (!used[v]) {
            comp.clear();
            dfs(v);
            cout << "Component:" ;
            for (int u : comp)
                cout << ' ' << u;
            cout << endl ;
        }
    }
}

  • The most important function that is used is find_comps() which finds and displays connected components of the graph.

  • The graph is stored in adjacency list representation, i.e adj[v] contains a list of vertices that have edges from the vertex v.

  • Vector comp contains a list of nodes in the current connected component.

Iterative implementation of the code

Deeply recursive functions are in general bad. Every single recursive call will require a little bit of memory in the stack, and per default programs only have a limited amount of stack space. So when you do a recursive DFS over a connected graph with millions of nodes, you might run into stack overflows.

It is always possible to translate a recursive program into an iterative program, by manually maintaining a stack data structure. Since this data structure is allocated on the heap, no stack overflow will occur.

int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;

void dfs(int v) {
    stack<int> st;
    st.push(v);

    while (!st.empty()) {
        int curr = st.top();
        st.pop();
        if (!used[curr]) {
            used[curr] = true;
            comp.push_back(curr);
            for (int i = adj[curr].size() - 1; i >= 0; i--) {
                st.push(adj[curr][i]);
            }
        }
    }
}

void find_comps() {
    used.assign(n, false);
    for (int v = 0; v < n ; ++v) {
        if (!used[v]) {
            comp.clear();
            dfs(v);
            cout << "Component:" ;
            for (int u : comp)
                cout << ' ' << u;
            cout << endl ;
        }
    }
}

Дасгал бодлогууд