Graph Problems

Banyak soal graph di kompetisi pemrograman maupun wawancara teknis tidak meminta kita menerapkan algoritma dari nol, melainkan mengenali pola tertentu lalu memetakan masalah ke operasi graph standar. Pada Chapter ini kita akan membahas beberapa pola paling sering muncar: flood fill pada grid, perhitungan jumlah komponen terhubung, deteksi pulau, dan friend circles. Setiap pola dijelaskan dengan analogi, kode C++ yang dapat dijalankan, dan analisis kompleksitas.

Flood Fill pada Grid #

Flood fill adalah teknik menandai semua sel yang terhubung (4-arah atau 8-arah) dengan nilai tertentu. Soal klasik: ubah semua sel bernilai 0 yang terhubung dengan sel awal menjadi 2. Masalah ini sebenarnya adalah DFS/BFS pada graph implisit yang dibentuk oleh sel-sel grid.

#include <iostream>
#include <vector>
using namespace std;

void floodFill(vector<vector<int>>& grid, int r, int c, int newColor) {
    int rows = grid.size();
    int cols = grid[0].size();
    int oldColor = grid[r][c];
    if (oldColor == newColor) return;

    auto dfs = [&](auto& self, int i, int j) -> void {
        if (i < 0 || i >= rows || j < 0 || j >= cols) return;
        if (grid[i][j] != oldColor) return;
        grid[i][j] = newColor;
        self(self, i + 1, j);
        self(self, i - 1, j);
        self(self, i, j + 1);
        self(self, i, j - 1);
    };
    dfs(dfs, r, c);
}

int main() {
    vector<vector<int>> grid = {
        {1, 1, 1, 0},
        {1, 0, 0, 0},
        {1, 0, 2, 2},
        {0, 0, 2, 2}
    };
    floodFill(grid, 1, 1, 3);

    for (const auto& row : grid) {
        for (int v : row) cout << v << ' ';
        cout << '\n';
    }
}

Output yang Dihasilkan:

1 1 1 3 
1 3 3 3 
1 3 2 2 
3 3 2 2 

Karena grid[1][1] = 0, semua sel 0 yang terhubung dengan (1,1) diubah menjadi 3. Sel bernilai 1 dan 2 tidak ikut berubah karena warnanya berbeda.

Mari kita telaah baris-baris kode di atas:

1. Baris 6–7: Ambil dimensi grid. Sel awal (r,c) menentukan warna lama oldColor yang akan diganti.
2. Baris 8: Jika warna baru sama dengan warna lama, fungsi berhenti. Tanpa cek ini, rekursi bisa berputar tanpa henti.
3. Baris 10–19: Lambda rekursif dfs menandai sel saat ini, lalu memanggil dirinya sendiri untuk empat tetangga ortogonal. Cek batas dan warna dilakukan di awal setiap pemanggilan.
4. Baris 16–19: Empat arah: bawah, atas, kanan, kiri. Variasi 8-arah cukup menambah empat diagonal.

Kompleksitas: O(rows × cols) karena setiap sel dikunjungi paling banyak sekali.

Number of Islands #

Soal “number of islands” meminta kita menghitung jumlah pulau (komponen terhubung sel bernilai 1) dalam grid. Solusinya adalah iterasi semua sel: setiap kali menemukan 1 yang belum dikunjungi, jalankan DFS/BFS untuk menandai seluruh pulau tersebut, lalu tambah counter.

#include <iostream>
#include <vector>
using namespace std;

int countIslands(vector<vector<char>>& grid) {
    int rows = grid.size();
    int cols = grid[0].size();
    int count = 0;

    auto dfs = [&](auto& self, int i, int j) -> void {
        if (i < 0 || i >= rows || j < 0 || j >= cols) return;
        if (grid[i][j] != '1') return;
        grid[i][j] = '2';  // tandai sudah dikunjungi
        self(self, i + 1, j);
        self(self, i - 1, j);
        self(self, i, j + 1);
        self(self, i, j - 1);
    };

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == '1') {
                ++count;
                dfs(dfs, i, j);
            }
        }
    }
    return count;
}

int main() {
    vector<vector<char>> grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    cout << "Jumlah pulau: " << countIslands(grid) << '\n';
}

Output yang Dihasilkan:

Jumlah pulau: 3

Pola yang dipakai di sini adalah component counting: setiap kali DFS baru dimulai, counter bertambah satu. Trik grid[i][j] = '2' menghindari penggunaan array visited terpisah sehingga memori tambahan berkurang. Kompleksitas tetap O(rows × cols).

Friend Circles #

Masalah friend circles sebenarnya adalah connected components pada graph tak berarah. Diberikan matriks adjacency n×n yang menyatakan hubungan pertemanan, hitung jumlah kelompok teman. Berbeda dengan number of islands, graph ini tidak berbentuk grid melainkan matriks relasi antar orang.

#include <iostream>
#include <vector>
using namespace std;

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    vector<bool> visited(n, false);
    int count = 0;

    auto dfs = [&](auto& self, int u) -> void {
        visited[u] = true;
        for (int v = 0; v < n; ++v) {
            if (isConnected[u][v] == 1 && !visited[v]) {
                self(self, v);
            }
        }
    };

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            ++count;
            dfs(dfs, i);
        }
    }
    return count;
}

int main() {
    vector<vector<int>> m = {
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 1}
    };
    cout << "Friend circles: " << findCircleNum(m) << '\n';
}

Output yang Dihasilkan:

Friend circles: 2

Pada matriks di atas, orang 0 dan 1 saling terhubung, sementara orang 2 terisolasi sehingga membentuk circle sendiri. Algoritma DFS menjelajah semua orang dalam satu circle sebelum berpindah ke circle berikutnya. Alternatif yang lebih efisien secara memori adalah Disjoint Set Union, terutama bila yang ditanya hanya jumlah komponen (tanpa perlu daftar anggota).

Topological Sort sebagai Graph Problem #

Banyak soal nyata dapat dipetakan ke topological sort: build order proyek software, urutan ambil mata kuliah, urutan task dengan dependency. Inti pemetaannya adalah: setiap entitas menjadi vertex, setiap prerequisite menjadi edge berarah u → v.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> topoSort(int n, vector<vector<int>>& adj) {
    vector<int> inDegree(n, 0);
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) ++inDegree[v];

    queue<int> q;
    for (int i = 0; i < n; ++i)
        if (inDegree[i] == 0) q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--inDegree[v] == 0) q.push(v);
        }
    }
    return order;
}

int main() {
    int n = 6;
    vector<vector<int>> adj(n);
    adj[5] = {2, 0};
    adj[4] = {0, 1};
    adj[2] = {3};
    adj[3] = {1};

    auto order = topoSort(n, adj);
    if ((int)order.size() != n) {
        cout << "Cycle terdeteksi, tidak ada urutan topologis\n";
    } else {
        cout << "Urutan topologis: ";
        for (int x : order) cout << x << ' ';
        cout << '\n';
    }
}

Output yang Dihasilkan:

Urutan topologis: 4 5 0 2 3 1

Pola Kahn di atas memanfaatkan inDegree untuk menemukan vertex tanpa prerequisite secara efisien. Jika hasil order.size() != n, ada siklus sehingga topological sort tidak mungkin. Bandingkan dengan pendekatan DFS yang menggunakan post-order reverse: keduanya menghasilkan urutan yang valid, tetapi Kahn lebih mudah diadaptasi untuk deteksi cycle.

Ringkasan Pola #

Latihan #

1. Diberikan grid n×m dengan nilai 0 (air) dan 1 (daratan), hitung luas pulau terbesar. Petunjuk: modifikasi countIslands untuk melacak ukuran tiap komponen.
2. Diberikan daftar prasyarat mata kuliah [a, b] yang berarti a harus diambil sebelum b, tentukan apakah mungkin menyelesaikan semua mata kuliah. Petunjuk: deteksi cycle pada DAG.
3. Diberikan matriks adjacency pertemanan, tentukan apakah graph tersebut bipartite (pemilih dua kelompok tanpa pertemanan internal). Petunjuk: BFS 2-coloring.

Pola-pola pada Chapter ini menjadi fondasi penting sebelum melangkah ke Chapter algoritma graph lanjutan seperti shortest path dan minimum spanning tree.