GRAF

Tugas Pertemuan ke-14  ·  Struktur Data - D

Implementasi & Studi Kasus
Graf (Graph)

Memahami struktur data non-linear Graf: konsep dasar, representasi dengan Adjacency Matrix & Adjacency List, traversal DFS & BFS, hingga penerapannya pada sistem pertemanan media sosial menggunakan C++.

GitHub Repository

Mata KuliahStruktur Data - D

Pertemuanke-14

BahasaC++

Topik UtamaGraf (Graph)

Apa Itu Graf?

Graf (Graph) adalah struktur data non-linear yang digunakan untuk merepresentasikan hubungan antar objek. Berbeda dengan struktur data linear seperti array atau linked list, graf mampu menggambarkan relasi yang lebih kompleks karena terdiri dari kumpulan simpul (vertex) dan garis penghubung antar simpul (edge).

Komponen Utama dalam Graf

⚫

Vertex Titik/simpul yang mewakili objek atau entitas

➖

Edge Garis yang menghubungkan dua vertex

🔢

Degree Jumlah edge yang terhubung ke satu vertex

🛣️

Path Rangkaian vertex yang saling terhubung edge

   A ----- B
   |       |
   |       |
   C ----- D

Vertex: A B C D  ·  Edge: (A,B) (A,C) (B,D) (C,D)

Jenis-Jenis Graf

Undirected GraphHubungan dua arah, edge tidak punya arah

Directed GraphHubungan satu arah (punya panah arah)

Weighted GraphSetiap edge memiliki bobot/nilai

Unweighted GraphEdge tidak memiliki bobot

Cyclic GraphMemiliki siklus (jalur yang kembali)

Acyclic GraphTidak memiliki siklus

Operasi yang Diimplementasikan

addEdge()

Add EdgeMenambahkan hubungan antar dua vertex

display()

DisplayMenampilkan representasi graf

DFS()

Depth First SearchMenelusuri graf secara mendalam

BFS()

Breadth First SearchMenelusuri graf per level

---

Program 1 — Adjacency Matrix

Adjacency Matrix menyimpan graf dalam bentuk matriks 2D berukuran V×V. Nilai 1 berarti ada edge antar dua vertex, dan 0 berarti tidak ada. Mudah dipahami, tapi boros memori karena kompleksitasnya O(V²).

adjacency_matrix.cpp C++

#include <iostream>
using namespace std;

class Graph {
private:
    int matrix[100][100];
    int vertices;

public:
    Graph(int v) {
        vertices = v;
        for (int i = 0; i < v; i++)
            for (int j = 0; j < v; j++)
                matrix[i][j] = 0;
    }

    void addEdge(int u, int v) {
        matrix[u][v] = 1;
        matrix[v][u] = 1;  // undirected (dua arah)
    }

    void display() {
        cout << "Adjacency Matrix" << endl;
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++)
                cout << matrix[i][j] << " ";
            cout << endl;
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.display();
    return 0;
}

Output Program

Terminal Output

Adjacency Matrix
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

• matrix[100][100]Array 2D untuk menyimpan hubungan antar vertex.
• Graph(int v)Constructor yang mengisi seluruh sel matriks dengan 0 (belum ada edge).
• addEdge()Mengisi matrix[u][v] dan matrix[v][u] dengan 1 karena graf dua arah.
• display()Menampilkan isi matriks baris per baris ke layar.

---

Program 2 — Adjacency List

Adjacency List menyimpan graf sebagai daftar tetangga tiap vertex menggunakan vector. Lebih hemat memori dibanding matrix, terutama untuk graf yang edge-nya sedikit (sparse).

adjacency_list.cpp C++

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void display() {
        for (int i = 0; i < V; i++) {
            cout << i << " -> ";
            for (int node : adj[i])
                cout << node << " ";
            cout << endl;
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.display();
    return 0;
}

Output Program

Terminal Output

0 -> 1 2
1 -> 0 3
2 -> 0 3
3 -> 1 2

• vector<vector<int>>Setiap index mewakili satu vertex, isinya daftar vertex tetangganya.
• addEdge()Menambahkan v ke daftar tetangga u, dan sebaliknya (dua arah).
• display()Menampilkan tiap vertex diikuti daftar tetangga langsungnya.

---

Program 3 — DFS (Depth First Search)

DFS menelusuri graf sedalam mungkin di satu cabang sebelum berpindah ke cabang lain. Diimplementasikan secara rekursif dengan bantuan array visited agar tidak terjadi perulangan tak terbatas.

       0
      / \
     1   2
     |   |
     3   4

Edge: (0,1) (0,2) (1,3) (2,4)  ·  DFS dari 0 → 0 1 3 2 4

dfs.cpp C++

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;
    vector<bool> visited;

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
        visited.resize(V, false);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void DFS(int v) {
        visited[v] = true;
        cout << v << " ";
        for (int u : adj[v])
            if (!visited[u])
                DFS(u);
    }
};

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

    cout << "DFS : ";
    g.DFS(0);
    return 0;
}

Output Program

Terminal Output

DFS : 0 1 3 2 4

• visitedArray boolean untuk menandai vertex yang sudah dikunjungi.
• DFS()Menandai vertex, mencetaknya, lalu menelusuri tetangga yang belum dikunjungi secara rekursif (mendalam dulu).

---

Program 4 — BFS (Breadth First Search)

BFS menelusuri graf per level — dari vertex terdekat ke yang terjauh. Menggunakan struktur queue (FIFO) untuk mengatur urutan kunjungan.

bfs.cpp C++

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;

public:
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        visited[start] = true;
        q.push(start);

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << v << " ";
            for (int u : adj[v])
                if (!visited[u]) {
                    visited[u] = true;
                    q.push(u);
                }
        }
    }
};

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

    cout << "BFS : ";
    g.BFS(0);
    return 0;
}

Output Program

Terminal Output

BFS : 0 1 2 4 3

• queueMenyimpan vertex yang akan dikunjungi dengan urutan FIFO (yang masuk dulu, keluar dulu).
• BFS()Mengambil vertex terdepan, mencetaknya, lalu memasukkan seluruh tetangganya yang belum dikunjungi ke queue. Hasilnya penelusuran per level.

⚠️ Catatan — DFS vs BFS Untuk graf yang sama, urutan hasilnya berbeda. DFS menelusuri sedalam mungkin di satu cabang dulu (cocok untuk cek keterhubungan / pencarian jalur), sedangkan BFS menelusuri per level (cocok untuk mencari jarak/jalur terpendek pada graf tak berbobot).

---

Studi Kasus — Sistem Pertemanan Media Sosial

Graf sangat cocok untuk memodelkan jaringan pertemanan. Setiap pengguna menjadi vertex, dan hubungan pertemanan menjadi edge. DFS dipakai untuk menemukan seluruh pengguna yang terhubung, sedangkan BFS untuk menentukan tingkat kedekatan pertemanan.

       Andi
       /  \
    Budi   Citra
     |       |
    Dina    Eko

Relasi: Andi↔Budi · Andi↔Citra · Budi↔Dina · Citra↔Eko

social_graph.cpp C++

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

class SocialGraph {
private:
    int V;
    vector<vector<int>> adj;
    vector<bool> visited;
    vector<string> users;

public:
    SocialGraph(int v, vector<string> names) {
        V = v;
        adj.resize(V);
        visited.resize(V, false);
        users = names;
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void showFriends(int v) {
        cout << "Teman " << users[v] << " : ";
        for (int u : adj[v]) cout << users[u] << " ";
        cout << endl;
    }

    void DFS(int v) {
        visited[v] = true;
        cout << users[v] << " ";
        for (int u : adj[v])
            if (!visited[u]) DFS(u);
    }

    void BFS(int start) {
        vector<bool> vis(V, false);
        vector<int> level(V, -1);
        queue<int> q;
        vis[start] = true;
        level[start] = 0;
        q.push(start);

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << users[v] << " (tingkat " << level[v] << ")" << endl;
            for (int u : adj[v])
                if (!vis[u]) {
                    vis[u] = true;
                    level[u] = level[v] + 1;
                    q.push(u);
                }
        }
    }
};

int main() {
    vector<string> users = {"Andi", "Budi", "Citra", "Dina", "Eko"};
    SocialGraph g(5, users);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);

    cout << "===== DATA PERTEMANAN =====" << endl;
    for (int i = 0; i < 5; i++) g.showFriends(i);

    cout << "\nDFS (semua yang terhubung dari Andi): ";
    g.DFS(0);

    cout << "\n\nBFS (tingkat pertemanan dari Andi):" << endl;
    g.BFS(0);
    return 0;
}

Output Program

Terminal Output

===== DATA PERTEMANAN =====
Teman Andi : Budi Citra
Teman Budi : Andi Dina
Teman Citra : Andi Eko
Teman Dina : Budi
Teman Eko : Citra

DFS (semua yang terhubung dari Andi): Andi Budi Dina Citra Eko

BFS (tingkat pertemanan dari Andi):
Andi (tingkat 0)
Budi (tingkat 1)
Citra (tingkat 1)
Dina (tingkat 2)
Eko (tingkat 2)

• usersVector string yang menyimpan nama tiap vertex, agar output menampilkan nama, bukan angka.
• showFriends()Menampilkan daftar teman langsung dari satu pengguna.
• DFS()Menelusuri seluruh pengguna yang terhubung — membuktikan jaringan ini saling terhubung.
• BFS()Menghitung tingkat kedekatan: tingkat 0 diri sendiri, tingkat 1 teman langsung, tingkat 2 teman dari teman.

---

Kelebihan & Kekurangan Graf

✅ Kelebihan

• Mampu merepresentasikan hubungan kompleks antar objek
• Banyak dipakai di sistem nyata (media sosial, Google Maps, jaringan)
• Mendukung banyak algoritma pencarian & optimasi (DFS, BFS, Dijkstra)
• Fleksibel: bisa berarah, tak berarah, atau berbobot

⚠️ Kekurangan

• Implementasi lebih kompleks dari struktur data linear
• Adjacency matrix boros memori, O(V²)
• Pengolahan makin berat saat vertex & edge bertambah banyak

Kesimpulan

Graf adalah struktur data non-linear yang memodelkan hubungan antar objek lewat vertex dan edge. Lewat program di atas, kita memahami dua cara representasi (Adjacency Matrix & List) dan dua metode traversal (DFS & BFS), serta penerapannya pada studi kasus sistem pertemanan media sosial.

Pemahaman graf menjadi fondasi untuk mempelajari algoritma lanjutan:

Weighted Graph Dijkstra Minimum Spanning Tree Topological Sort A* Search