Graph adalah struktur data yang merepresentasikan hubungan antar objek. Setiap objek disebut node atau vertex, dan hubungan antar node disebut edge. Graph dipakai di mana-mana: peta jalan (kota = node, jalan = edge), jaringan sosial (orang = node, pertemanan = edge), ketergantungan task (task = node, dependensi = edge). Pada chapter ini kita akan mengimplementasikan dua representasi graph: adjacency matrix (array 2D) dan adjacency list (array of linked list), lalu menjalankan BFS untuk traversal.

Konsep Graph #

Beberapa tipe graph yang umum:

  • Directed: edge punya arah (A→B tidak sama dengan B→A).
  • Undirected: edge tidak berarah (A-B sama dengan B-A).
  • Weighted: edge punya bobot (jarak, biaya, waktu).
  • Unweighted: edge hanya ada/tidak, tanpa bobot.
  • Cyclic: ada siklus (path dari node kembali ke dirinya sendiri).
  • Acyclic: tidak ada siklus (DAG = Directed Acyclic Graph).

Pemilihan representasi memengaruhi kompleksitas operasi:

  • Adjacency matrix: cek edge O(1), iterasi tetangga O(V). Memori O(V^2). Cocok untuk graph padat (banyak edge).
  • Adjacency list: cek edge O(deg(v)), iterasi tetangga O(deg(v)). Memori O(V+E). Cocok untuk graph jarang (sedikit edge).

Representasi Adjacency Matrix #

Adjacency matrix adalah array 2D matriks[V][V]. matriks[i][j] berisi bobot edge i→j, atau 0 bila tidak ada edge. Untuk graph undirected, matrix simetris: matriks[i][j] == matriks[j][i].

c 
#include <stdio.h>
#include <stdlib.h>

#define JUMLAH_NODE 6

typedef struct {
    int matriks[JUMLAH_NODE][JUMLAH_NODE];
    int jumlah_node;
} graph_matrix;

void gm_init(graph_matrix *g, int n) {
    g->jumlah_node = n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g->matriks[i][j] = 0;
}

void gm_tambah_edge(graph_matrix *g, int dari, int ke, int berat) {
    if (dari < 0 || dari >= g->jumlah_node) return;
    if (ke < 0 || ke >= g->jumlah_node) return;
    g->matriks[dari][ke] = berat;
}

void gm_cetak(graph_matrix *g) {
    printf("Adjacency Matrix (%d node):\n     ", g->jumlah_node);
    for (int j = 0; j < g->jumlah_node; j++) printf("%3d", j);
    printf("\n");
    for (int i = 0; i < g->jumlah_node; i++) {
        printf("%3d:", i);
        for (int j = 0; j < g->jumlah_node; j++) {
            printf("%3d", g->matriks[i][j]);
        }
        printf("\n");
    }
}

int gm_tetangga(graph_matrix *g, int node, int *out, int maks) {
    int count = 0;
    for (int j = 0; j < g->jumlah_node && count < maks; j++) {
        if (g->matriks[node][j] != 0) out[count++] = j;
    }
    return count;
}

int main(void) {
    graph_matrix g;
    gm_init(&g, JUMLAH_NODE);

    /* Bangun graph directed */
    gm_tambah_edge(&g, 0, 1, 1);
    gm_tambah_edge(&g, 0, 2, 1);
    gm_tambah_edge(&g, 1, 3, 1);
    gm_tambah_edge(&g, 2, 3, 1);
    gm_tambah_edge(&g, 3, 4, 1);
    gm_tambah_edge(&g, 3, 5, 1);
    gm_tambah_edge(&g, 4, 5, 1);

    gm_cetak(&g);

    int tetangga[10];
    int n = gm_tetangga(&g, 3, tetangga, 10);
    printf("\nTetangga node 3: ");
    for (int i = 0; i < n; i++) printf("%d ", tetangga[i]);
    printf("\n");

    return 0;
}

Output yang Dihasilkan:

text 
Adjacency Matrix (6 node):
       0  1  2  3  4  5
  0:  0  1  1  0  0  0
  1:  0  0  0  1  0  0
  2:  0  0  0  1  0  0
  3:  0  0  0  0  1  1
  4:  0  0  0  0  0  1
  5:  0  0  0  0  0  0

Tetangga node 3: 4 5

Matrix jelas terlihat sebagai grid 6x6. Node 3 terhubung ke node 4 dan 5 (matriks[3][4]=1, matriks[3][5]=1). Untuk graph directed, matrix tidak simetris—matriks[0][1]=1 tetapi matriks[1][0]=0.

Mari kita telaah baris-baris kode di atas:

  1. Baris 6-9 (graph_matrix struct): array 2D statis dengan ukuran JUMLAH_NODE x JUMLAH_NODE. Field jumlah_node melacak jumlah node aktif (boleh kurang dari JUMLAH_NODE).
  2. Baris 11-16 (gm_init): reset semua sel ke 0 (tidak ada edge). Loop nested sederhana.
  3. Baris 18-22 (gm_tambah_edge): cek batas, lalu set matriks[dari][ke] = berat. Untuk graph undirected, tambahkan baris g->matriks[ke][dari] = berat; juga.
  4. Baris 24-37 (gm_cetak): cetak matrix sebagai grid. Header kolom di atas, label baris di kiri. Format %3d merapikan alignment.
  5. Baris 39-45 (gm_tetangga): iterasi baris matriks[node][j] untuk semua j, kumpulkan indeks j yang tidak 0. Berguna untuk BFS/DFS.
  6. Baris 47-62 (main): bangun graph directed dengan 7 edge. Cetak matrix. Cetak tetangga node 3.

Representasi Adjacency List #

Adjacency list menyimpan daftar tetangga tiap node sebagai linked list. Setiap node punya pointer ke head list tetangga. Memori O(V + E)—hemat pada graph jarang.

c 
#include <stdio.h>
#include <stdlib.h>

typedef struct edge {
    int tujuan;
    int berat;
    struct edge *next;
} edge;

typedef struct {
    edge **adj;
    int jumlah_node;
} graph_list;

void gl_init(graph_list *g, int n) {
    g->jumlah_node = n;
    g->adj = calloc((size_t)n, sizeof(edge *));
}

void gl_tambah_edge(graph_list *g, int dari, int ke, int berat) {
    if (dari < 0 || dari >= g->jumlah_node) return;
    if (ke < 0 || ke >= g->jumlah_node) return;
    edge *e = malloc(sizeof(edge));
    if (e == NULL) return;
    e->tujuan = ke;
    e->berat = berat;
    e->next = g->adj[dari];
    g->adj[dari] = e;
}

void gl_hapus_semua(graph_list *g) {
    for (int i = 0; i < g->jumlah_node; i++) {
        edge *cur = g->adj[i];
        while (cur != NULL) {
            edge *tmp = cur->next;
            free(cur);
            cur = tmp;
        }
        g->adj[i] = NULL;
    }
    free(g->adj);
    g->adj = NULL;
}

void gl_cetak(graph_list *g) {
    printf("Adjacency List (%d node):\n", g->jumlah_node);
    for (int i = 0; i < g->jumlah_node; i++) {
        printf("  %d ->", i);
        for (edge *e = g->adj[i]; e != NULL; e = e->next) {
            printf(" %d(w=%d)", e->tujuan, e->berat);
        }
        printf("\n");
    }
}

/* BFS sederhana */
void bfs(graph_list *g, int mulai) {
    int *dikunjungi = calloc((size_t)g->jumlah_node, sizeof(int));
    int *antrian = malloc(sizeof(int) * (size_t)g->jumlah_node);
    int depan = 0, belakang = 0;

    printf("BFS mulai dari %d: ", mulai);
    antrian[belakang++] = mulai;
    dikunjungi[mulai] = 1;

    while (depan < belakang) {
        int cur = antrian[depan++];
        printf("%d ", cur);
        for (edge *e = g->adj[cur]; e != NULL; e = e->next) {
            if (!dikunjungi[e->tujuan]) {
                dikunjungi[e->tujuan] = 1;
                antrian[belakang++] = e->tujuan;
            }
        }
    }
    printf("\n");

    free(dikunjungi);
    free(antrian);
}

int main(void) {
    graph_list g;
    gl_init(&g, 6);

    gl_tambah_edge(&g, 0, 1, 1);
    gl_tambah_edge(&g, 0, 2, 1);
    gl_tambah_edge(&g, 1, 3, 1);
    gl_tambah_edge(&g, 2, 3, 1);
    gl_tambah_edge(&g, 3, 4, 1);
    gl_tambah_edge(&g, 3, 5, 1);
    gl_tambah_edge(&g, 4, 5, 1);

    gl_cetak(&g);
    printf("\n");
    bfs(&g, 0);
    bfs(&g, 3);

    gl_hapus_semua(&g);
    return 0;
}

Output yang Dihasilkan:

text 
Adjacency List (6 node):
  0 -> 2(w=1) 1(w=1)
  1 -> 3(w=1)
  2 -> 3(w=1)
  3 -> 5(w=1) 4(w=1)
  4 -> 5(w=1)
  5 ->

BFS mulai dari 0: 0 2 1 3 5 4 
BFS mulai dari 3: 3 5 4

Adjacency list lebih ringkas dari matrix—hanya edge yang ada yang disimpan. Node 0 terhubung ke 2 dan 1 (dalam urutan terbalik karena insert di depan linked list). BFS dari node 0 mengunjungi: 0, lalu 2 dan 1 (tetangga), lalu 3 (tetangga 2/1), lalu 5 dan 4 (tetangga 3).

Mari kita telaah baris-baris kode di atas:

  1. Baris 4-8 (struct edge): node linked list dengan tujuan, berat, dan next. Setiap edge direpresentasikan satu node.
  2. Baris 10-14 (graph_list struct): array of edge *. Setiap indeks adj[i] adalah pointer ke head linked list tetangga node i. Field jumlah_node melacak ukuran array.
  3. Baris 16-19 (gl_init): alokasi array adj dengan calloc agar semua pointer awalnya NULL. calloc mengisi memori dengan 0, ekuivalen dengan NULL untuk pointer.
  4. Baris 21-30 (gl_tambah_edge): alokasi node edge baru, isi field, sisip di depan list adj[dari]. Insert depan O(1), urutan edge pada list terbalik dari urutan insert.
  5. Baris 32-44 (gl_hapus_semua): iterasi setiap node, bebaskan linked list tetangga, lalu bebaskan array adj itu sendiri. Wajib free dua tingkat: edges dulu, lalu array of pointers.
  6. Baris 56-78 (bfs): Breadth-First Search. Mulai dari node mulai, masukkan ke queue. Loop: dequeue node, cetak, enqueue semua tetangga yang belum dikunjungi. Array dikunjungi mencegah kunjungan ganda. Kompleksitas O(V + E).
  7. Baris 75-76 (free di akhir BFS): bebaskan array dikunjungi dan antrian agar tidak leak bila BFS dipanggil berulang.

Perbandingan Representasi #

OperasiAdjacency MatrixAdjacency List
Cek edge (u, v)O(1)O(deg(u))
Iterasi tetanggaO(V)O(deg(u))
MemoriO(V^2)O(V + E)
Tambah edgeO(1)O(1) (insert depan)
Hapus edgeO(1)O(deg(u))
Cocok untukGraph padat (E ≈ V^2)Graph jarang (E « V^2)

Algoritma Graph Umum #

Beberapa algoritma graph klasik dan kompleksitasnya:

AlgoritmaKompleksitas (adj list)Kegunaan
BFSO(V + E)Shortest path unweighted, konektivitas
DFSO(V + E)Deteksi siklus, topological sort
DijkstraO((V + E) log V)Shortest path weighted (non-negatif)
Bellman-FordO(V * E)Shortest path dengan edge negatif
KruskalO(E log E)Minimum Spanning Tree
Floyd-WarshallO(V^3)All-pairs shortest path