Connected Components

Pada graph tak berarah, dua vertex yang dapat saling menjangkau berada dalam connected component yang sama. Bila graph memiliki bagian-bagian terpisah, masing-masing bagian adalah satu komponen. Menemukan seluruh komponen ini berguna untuk: menghitung jumlah cluster di social network, mendeteksi isolated nodes, mengelompokkan area koneksi jaringan, atau sebagai preprocessing sebelum algoritma graph lain. Pada Chapter ini kita akan mengimplementasikan algoritma connected components menggunakan DFS dan BFS, menganalisis kompleksitas, lalu mengaplikasikannya pada contoh soal “friend circles”.

Aturan: Definisi Connected Component #

Pada undirected graph G:

• Dua vertex u dan v berada dalam komponen yang sama bila ada path dari u ke v (atau keduanya adalah vertex yang sama).
• Connected component adalah himpunan maksimal vertex-vertex yang saling terhubung.
• Setiap vertex pasti berada di tepat satu komponen — relasi “berada dalam komponen yang sama” bersifat equivalence relation (refleksif, simetris, transitif).

Untuk directed graph, konsep analog adalah strongly connected component (SCC), yang akan dibahas tuntas pada Chapter khusus di Section algoritma-graph.

Pada graph di atas:

• Komponen 1: {0, 1, 2} — semua saling terhubung.
• Komponen 2: {3, 4, 5} — semua saling terhubung.
• Komponen 3: {6} — isolated vertex, komponen berukuran 1.

Mekanisme: DFS/BFS untuk Connected Components #

Algoritma menemukan connected components sangat sederhana:

1. Inisialisasi visited[] = false dan component_id[] = -1.
2. Loop setiap vertex s = 0..V-1:
   • Bila visited[s] sudah true, skip (sudah ditandai ke komponen lain).
   • Bila belum visited, mulai DFS/BFS dari s. Semua vertex yang terjangkau adalah satu komponen baru. Tandai mereka dengan component_id[v] = current_component.
   • Increment current_component.
3. Setelah loop selesai, current_component = jumlah komponen.

Kompleksitas: O(V+E) karena setiap vertex dan edge dikunjungi tepat satu kali.

Implementasi dengan DFS #

Kode: Connected Components dengan DFS #

#include <iostream>
#include <vector>

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

void dfs(const Graph& g, int u, int comp_id,
         std::vector<int>& component_id, std::vector<bool>& visited) {
    visited[u] = true;
    component_id[u] = comp_id;
    for (int v : g.neighbors(u)) {
        if (!visited[v]) dfs(g, v, comp_id, component_id, visited);
    }
}

int find_components(const Graph& g, std::vector<int>& component_id) {
    int n = g.v_count();
    component_id.assign(n, -1);
    std::vector<bool> visited(n, false);
    int count = 0;
    for (int s = 0; s < n; ++s) {
        if (!visited[s]) {
            dfs(g, s, count, component_id, visited);
            count++;
        }
    }
    return count;
}

int main() {
    Graph g(7);  // 7 vertex: 0,1,2 | 3,4,5 | 6
    g.add_edge_undirected(0, 1);
    g.add_edge_undirected(0, 2);
    g.add_edge_undirected(1, 2);
    g.add_edge_undirected(3, 4);
    g.add_edge_undirected(4, 5);
    // vertex 6 tidak punya edge

    std::vector<int> comp;
    int n_comp = find_components(g, comp);

    std::cout << "Jumlah connected components = " << n_comp << '\n';
    std::cout << "\nVertex -> Komponen:\n";
    for (int v = 0; v < g.v_count(); ++v) {
        std::cout << "  vertex " << v << " -> komponen " << comp[v] << '\n';
    }

    // Kelompokkan vertex berdasarkan komponen
    std::vector<std::vector<int>> groups(n_comp);
    for (int v = 0; v < g.v_count(); ++v) groups[comp[v]].push_back(v);

    std::cout << "\nDaftar vertex per komponen:\n";
    for (int c = 0; c < n_comp; ++c) {
        std::cout << "  Komponen " << c << ": ";
        for (int v : groups[c]) std::cout << v << ' ';
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

Jumlah connected components = 3

Vertex -> Komponen:
  vertex 0 -> komponen 0
  vertex 1 -> komponen 0
  vertex 2 -> komponen 0
  vertex 3 -> komponen 1
  vertex 4 -> komponen 1
  vertex 5 -> komponen 1
  vertex 6 -> komponen 2

Daftar vertex per komponen:
  Komponen 0: 0 1 2
  Komponen 1: 3 4 5
  Komponen 2: 6

1. Baris component_id.assign(n, -1);: reset array ke -1 (belum ter-assign). Penggunaan assign lebih jelas daripada loop manual.
2. Baris for (int s = 0; s < n; ++s): loop seluruh vertex. Setiap vertex yang belum visited menjadi titik mulai komponen baru.
3. Baris dfs(g, s, count, component_id, visited);: DFS rekursif menandai seluruh vertex yang terjangkau dari s dengan count (id komponen saat ini). Kompleksitas per DFS: O(V_c + E_c) untuk komponen berukuran V_c.
4. Baris count++;: setelah satu komponen selesai diproses, naikkan counter. Komponen berikutnya akan mendapat id count+1.
5. Hasil 3 komponen: komponen 0 = {0,1,2}, komponen 1 = {3,4,5}, komponen 2 = {6} (isolated vertex).
6. Hasil komponen 2: 6: vertex 6 tidak punya edge, jadi DFS dari vertex 6 hanya menandai dirinya sendiri sebagai komponen.

Implementasi dengan BFS #

Versi BFS menggantikan rekursi dengan queue eksplisit — menghindari stack overflow pada komponen besar.

Kode: Connected Components dengan BFS #

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

class Graph {
public:
    explicit Graph(int n) : adj_(n) {}
    void add_edge_undirected(int u, int v) {
        adj_[u].push_back(v);
        adj_[v].push_back(u);
    }
    const std::vector<int>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<int>> adj_;
};

int find_components_bfs(const Graph& g, std::vector<int>& component_id) {
    int n = g.v_count();
    component_id.assign(n, -1);
    int count = 0;
    std::queue<int> q;

    for (int s = 0; s < n; ++s) {
        if (component_id[s] != -1) continue;
        component_id[s] = count;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g.neighbors(u)) {
                if (component_id[v] == -1) {
                    component_id[v] = count;
                    q.push(v);
                }
            }
        }
        count++;
    }
    return count;
}

int main() {
    Graph g(7);
    g.add_edge_undirected(0, 1);
    g.add_edge_undirected(0, 2);
    g.add_edge_undirected(1, 2);
    g.add_edge_undirected(3, 4);
    g.add_edge_undirected(4, 5);

    std::vector<int> comp;
    int n_comp = find_components_bfs(g, comp);

    std::cout << "Jumlah komponen (BFS) = " << n_comp << '\n';

    // Ukuran setiap komponen
    std::vector<int> sizes(n_comp, 0);
    for (int v = 0; v < g.v_count(); ++v) sizes[comp[v]]++;
    std::cout << "\nUkuran setiap komponen:\n";
    for (int c = 0; c < n_comp; ++c) {
        std::cout << "  Komponen " << c << ": " << sizes[c] << " vertex\n";
    }
    return 0;
}

Output yang Dihasilkan:

Jumlah komponen (BFS) = 3

Ukuran setiap komponen:
  Komponen 0: 3 vertex
  Komponen 1: 3 vertex
  Komponen 2: 1 vertex

1. Baris if (component_id[s] != -1) continue;: skip vertex yang sudah ter-assign komponen. Skip ini yang memastikan setiap komponen diproses hanya satu kali.
2. Baris component_id[s] = count; q.push(s);: tandai visited (assign komponen) saat push. Berbeda dari DFS iteratif yang menandai saat pop — BFS selalu menandai saat push untuk mencegah duplikasi.
3. Baris if (component_id[v] == -1): cek sebelum push neighbor. Memastikan setiap vertex masuk queue tepat satu kali.
4. Hasil count = 3: sama dengan versi DFS — algoritma benar untuk kedua traversal.
5. Hasil Komponen 2: 1 vertex: vertex 6 isolated, hanya dirinya sendiri dalam komponen.

Aplikasi: Friend Circles #

Soal klasik: ada n orang dengan relasi pertemanan (matrix isFriend[i][j]). Temukan jumlah “friend circles” — kelompok maksimal di mana setiap orang terhubung langsung atau tidak langsung dengan yang lain.

Kode: Friend Circles (LeetCode 547 style) #

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

// isConnected[i][j] = 1 bila i dan j berteman (matrix simetris)
int count_friend_circles(const std::vector<std::vector<int>>& isConnected) {
    int n = isConnected.size();
    std::vector<int> component_id(n, -1);
    int count = 0;
    std::queue<int> q;

    for (int s = 0; s < n; ++s) {
        if (component_id[s] != -1) continue;
        component_id[s] = count;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v < n; ++v) {
                if (isConnected[u][v] && component_id[v] == -1) {
                    component_id[v] = count;
                    q.push(v);
                }
            }
        }
        count++;
    }
    return count;
}

int main() {
    // 5 orang: {0,1,2} berteman satu sama lain; {3,4} berteman; tidak ada yang lain
    std::vector<std::vector<int>> isConnected = {
        {1, 1, 0, 0, 0},  // 0 berteman dengan 0,1
        {1, 1, 0, 0, 0},  // 1 berteman dengan 0,1
        {0, 0, 1, 0, 0},  // 2 berteman hanya dengan diri sendiri
        {0, 0, 0, 1, 1},  // 3 berteman dengan 3,4
        {0, 0, 0, 1, 1},  // 4 berteman dengan 3,4
    };

    int circles = count_friend_circles(isConnected);
    std::cout << "Jumlah friend circles = " << circles << '\n';
    return 0;
}

Output yang Dihasilkan:

Jumlah friend circles = 3

1. Baris if (isConnected[u][v] && component_id[v] == -1): cek edge melalui matrix — bila ada hubungan dan v belum ter-assign komponen, tambahkan ke komponen saat ini.
2. Baris for (int v = 0; v < n; ++v): iterasi seluruh vertex untuk mencari neighbor (karena input berupa adjacency matrix, bukan adjacency list). Kompleksitas menjadi O(V²) bukan O(V+E).
3. Hasil 3 friend circles: circle 0 = {0, 1}, circle 1 = {2}, circle 2 = {3, 4}. Vertex 2 hanya berteman dengan dirinya sendiri (diagonal), jadi terisolasi.

Kompleksitas dan Optimasi #

Tabel kompleksitas untuk algoritma connected components:

Variasi: Weakly Connected Components pada Directed Graph #

Untuk directed graph, weakly connected component adalah connected component pada underlying undirected graph (semua panah diabaikan). Implementasi: konversi directed → undirected lalu jalankan algoritma di atas.

Untuk strongly connected component (path dua arah untuk setiap pasangan), kita butuh algoritma khusus seperti Kosaraju atau Tarjan — dibahas pada Chapter khusus di Section algoritma-graph.

Ringkasan #

• Connected component pada undirected graph = himpunan maksimal vertex yang saling terjangkau.
• Algoritma: loop seluruh vertex, jalankan DFS/BFS dari yang belum visited, increment counter komponen.
• Kompleksitas O(V+E) pada adjacency list, O(V²) pada adjacency matrix.
• DFS rekursif paling ringkas tetapi berisiko stack overflow pada graph sangat dalam.
• BFS dengan queue eksplisit menghindari masalah stack overflow.
• Aplikasi: friend circles, image segmentation (grid DFS), cluster analysis, connectivity check.
• Variasi: weakly connected component pada directed (abaikan arah); strongly connected component membutuhkan Kosaraju/Tarjan.