Pertemuan 14 - Graf

 

Graf di C++

Nama: Hadryan Rizky Dimas Saputra

NRP: 5025251027

Kelas: Struktur Data (D) 2026

Pertemuan: 14

Source Code: pertemuan_14

1. Implementasi Adjacency Matrix

Deskripsi (Fungsi) Program: 

Program ini merepresentasikan graf tak berarah menggunakan matriks dua dimensi berukuran tetap, di mana nilai 1 pada indeks baris dan kolom menunjukkan adanya koneksi antar vertex, sedangkan nilai 0 menunjukkan tidak ada koneksi.

Code:

// Implementasi Adjacency Matrix

#include <bits/stdc++.h>

using namespace std;

class Graph {

private:

int mat[100][100];

int ver;

public:

Graph(int v) {

ver = v;

int i, j;

for(i = 0; i < v; i++) {

for(j = 0; j < v; j++) {

mat[i][j] = 0;

}

}

}

void addEdge(int u, int v) {

mat[u][v] = 1;

mat[v][u] = 1;

}

void display(void) {

cout << "Adjancency Matrix" << endl;

ver = v;

int i, j;

for(i = 0; i < v; i++) {

for(j = 0; j < v; j++) {

cout << mat[i][j] << " ";

}

cout << endl;

}

}

};

int main(void) {

Graph g(4);

g.addEdge(0,1);

g.addEdge(0,2);

g.addEdge(1,3);

g.addEdge(2,3);

g.display();

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
int mat[100][100]	Array dua dimensi untuk menyimpan hubungan antar vertex.
addEdge(u, v)	Mengisi baris u kolom v dan sebaliknya dengan nilai 1.
display()	Melakukan iterasi bersarang untuk mencetak seluruh isi matriks.

2. Implementasi Adjacency List

Deskripsi (Fungsi) Program: 

Program ini menyimpan graf menggunakan daftar ketetanggaan berupa vector of vectors, yang lebih efisien dalam penggunaan memori dibandingkan matriks karena hanya menyimpan data vertex yang benar-benar terhubung.

Code:

// Implementasi Adjacency List

#include <bits/stdc++.h>

using namespace std;

class gh {

private:

int v;

vector<vector<int>> adj;

public:

gh(int ver) {

v = ver;

adj.resize(v);

}

void addEdge(int u, int v) {

adj[u].push_back(v);

adj[v].push_back(u);

}

void display(void) {

int i;

for(i = 0; i < v; i++) {

cout << i << " -> ";

for(int n : adj[i]) {

cout << n << " ";

}

cout << endl;

}

}

};

int main(void) {

gh g(4);

g.addEdge(0,1);

g.addEdge(0,2);

g.addEdge(1,3);

g.addEdge(2,3);

g.display();

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
vector<vector<int>> adj	Kontainer dinamis untuk menampung daftar tetangga setiap vertex.
addEdge(u, v)	Menambahkan vertex v ke dalam list u dan sebaliknya.
display()	Melakukan iterasi pada setiap vector untuk menampilkan daftar tetangga.

3. Implementasi DFS

Deskripsi (Fungsi) Program: 

Program ini menerapkan algoritma penelusuran graf Depth First Search yang mengeksplorasi sedalam mungkin pada satu cabang sebelum melakukan backtracking menggunakan teknik rekursi.

Code:

// Implementasi DFS

#include <bits/stdc++.h>

using namespace std;

class gh {

private:

int v;

vector<vector<int>> adj;

vector<bool> vis;

public:

gh(int ver) {

v = ver;

adj.resize(v);

vis.resize(v, false);

}

void add(int u, int v) {

adj[u].push_back(v);

adj[v].push_back(u);

}

void dfs(int v) {

vis[v] = true;

cout << v << " ";

for(int u : adj[v]) {

if(!vis[u]) {

dfs(u);

}

}

}

};

int main(void) {

gh g(5);

g.add(0,1);

g.add(0,2);

g.add(1,3);

g.add(2,4);

cout << "DFS: ";

g.dfs(0);

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
vector<bool> vis	Array penanda untuk melacak vertex yang sudah dikunjungi.
dfs(int v)	Fungsi rekursif untuk mengunjungi tetangga yang belum dikunjungi.
!vis[u]	Kondisi pengecekan agar tidak terjadi perulangan tak terbatas.

4. Implementasi BFS

Deskripsi (Fungsi) Program: 

Program ini menerapkan algoritma Breadth First Search yang menelusuri graf lapis demi lapis berdasarkan jarak terdekat dari vertex awal menggunakan struktur data antrean (queue).

Code:

// Implementasi BFS

#include <bits/stdc++.h>

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(void) {

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;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
queue<int> q	Struktur data untuk menyimpan vertex yang akan dikunjungi selanjutnya.
q.front() & q.pop()	Mengambil vertex untuk diproses dari antrean.
visited	Array boolean untuk memastikan setiap vertex hanya diproses sekali.

5. Implementasi Graf Berbobot

Deskripsi (Fungsi) Program: 

Program ini memodifikasi struktur penyimpanan graf untuk menyertakan bobot pada setiap sisi menggunakan pair, yang memungkinkan representasi biaya atau jarak antar vertex secara spesifik.

Code:

// Implementasi Graf Berbobot

#include <bits/stdc++.h>

using namespace std;

class gh {

private:

map<char, vector<pair<char, int>>> adj;

public:

gh(int ver) {}

void add(char u, char v, int w) {

adj[u].push_back({v, w});

adj[v].push_back({u, w});

}

void display() {

for(auto const& [vertex, edges] : adj) {

cout << "Vertex " << vertex << ": ";

for(auto const& edge : edges) {

cout << "(" << edge.first << "," << edge.second << ") ";

}

cout << endl;

}

}

};

int main(void) {

gh g(4);

g.add('A', 'B', 5);

g.add('B', 'D', 3);

g.add('D', 'C', 1);

g.add('C', 'A', 2);

g.display();

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
pair<char, int>	Pasangan yang menyimpan vertex tetangga dan nilai bobotnya.
map<char, ...>	Struktur yang memetakan karakter vertex ke daftar tetangganya.
edges	Iterasi melalui pair untuk menampilkan target dan bobotnya.

6. Implementasi Dijkstra

Deskripsi (Fungsi) Program: 

Program ini mencari jalur terpendek dari satu titik awal ke semua titik lain dalam graf berbobot dengan menggunakan priority queue untuk selalu memilih vertex dengan jarak akumulatif terkecil.

Code:

// Implementasi Dijkstra

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000;

vector<pair<int, int>> graph[100];

void dijkstra(int start, int V, const vector<string>& names) {

vector<int> dist(V, INF);

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

dist[start] = 0;

pq.push({0, start});

while (!pq.empty()) {

int d = pq.top().first;

int u = pq.top().second;

pq.pop();

if (d > dist[u]) continue;

for (auto edge : graph[u]) {

int v = edge.first;

int w = edge.second;

if (dist[v] > dist[u] + w) {

dist[v] = dist[u] + w;

pq.push({dist[v], v});

}

}

}

cout << "Jarak Terpendek dari " << names[start] << ":" << endl;

for (int i = 0; i < V; i++) {

cout << names[i] << " : " << dist[i] << endl;

}

}

int main(void) {

int V = 3;

vector<string> names = {"Surabaya", "Sidoarjo", "Gresik"};

graph[0].push_back({1, 5});

graph[1].push_back({0, 5});

graph[0].push_back({2, 3});

graph[2].push_back({0, 3});

dijkstra(0, V, names);

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
priority_queue	Struktur antrean prioritas untuk memilih jarak terpendek secara cepat.
dist[V]	Array untuk menyimpan jarak minimum sementara dari titik awal.
INF	Konstanta angka besar untuk inisialisasi jarak awal yang belum terjangkau.

7. Studi Kasus Praktikum: Sistem Pertemanan di Media Sosial

Deskripsi (Fungsi) Program: 

Program ini mensimulasikan jaringan pertemanan sederhana di media sosial dengan memetakan nama pengguna ke dalam struktur graf dan menampilkan daftar teman untuk setiap individu.

Code:

// Studi Kasus Praktikum: Sistem Pertemanan di Media Sosial

#include <bits/stdc++.h>

using namespace std;

class Graph {

private:

int v;

vector<vector<int>> adj;

vector<string> users;

public:

Graph(int ver, vector<string> userNames) {

v = ver;

users = userNames;

adj.resize(v);

}

void addEdge(int u, int v_idx) {

adj[u].push_back(v_idx);

adj[v_idx].push_back(u);

}

void display() {

for (int i = 0; i < v; i++) {

cout << users[i] << " berteman dengan: ";

for (int neighbor : adj[i]) {

cout << users[neighbor] << " ";

}

cout << endl;

}

}

};

int main(void) {

vector<string> names = {"Andi", "Budi", "Citra", "Dina", "Eko"};

Graph g(5, names);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 3);

g.addEdge(2, 4);

g.display();

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
vector<string> users	Daftar nama pengguna untuk pemetaan indeks vertex.
addEdge	Menghubungkan dua user sebagai teman dalam struktur graf.
display()	Menampilkan relasi pertemanan berdasarkan nama penggunanya.

LATIHAN

A. Graf 8 Vertex dengan Adjacency List

Deskripsi (Fungsi) Program: 

Program ini membuat graf dengan 8 vertex yang saling terhubung membentuk siklus menggunakan adjacency list, sebagai bentuk latihan dasar alokasi memori dinamis pada graf.

Code:

// Graf 8 Vertex dengan Adjacency List

#include <iostream>

#include <vector>

using namespace std;

class Graph {

int V;

vector<vector<int>> adj;

public:

Graph(int V) : V(V), adj(V) {}

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

void printGraph() {

for(int i = 0; i < V; ++i) {

cout << "Vertex " << i << ": ";

for(int v : adj[i]) cout << v << " ";

cout << endl;

}

}

};

int main(void) {

Graph g(8);

g.addEdge(0, 1);

g.addEdge(1, 2);

g.addEdge(2, 3);

g.addEdge(3, 4);

g.addEdge(4, 5);

g.addEdge(5, 6);

g.addEdge(6, 7);

g.addEdge(7, 0);

g.printGraph();

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
Graph g(8)	Inisialisasi graf dengan 8 vertex (0 hingga 7).
addEdge	Menambahkan koneksi antar vertex berurutan hingga membentuk siklus.
printGraph()	Mencetak daftar ketetanggaan untuk setiap vertex.

B. Implementasi DFS dan BFS

Deskripsi (Fungsi) Program: 

Program ini menggabungkan dua algoritma penelusuran graf dalam satu kelas untuk mendemonstrasikan perbedaan urutan kunjungan antara penelusuran mendalam (DFS) dan melebar (BFS).

Code:

// Implementasi DFS dan BFS

#include <iostream>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

class Graph {

int V;

vector<vector<int>> adj;

public:

Graph(int V) : V(V), adj(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);

cout << "BFS: ";

while(!q.empty()) {

int u = q.front(); q.pop(); cout << u << " ";

for(int v : adj[u]) if(!visited[v]) { visited[v]=true; q.push(v); }

}

cout << endl;

}

void DFS(int start) {

vector<bool> visited(V, false);

stack<int> s;

s.push(start);

cout << "DFS: ";

while(!s.empty()) {

int u = s.top(); s.pop();

if(!visited[u]) { visited[u]=true; cout << u << " "; }

for(int v : adj[u]) if(!visited[v]) s.push(v);

}

cout << endl;

}

};

int main() {

Graph g(8);

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

g.BFS(0);

g.DFS(0);

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
stack	Digunakan oleh DFS untuk mengelola urutan kunjungan mendalam.
queue	Digunakan oleh BFS untuk mengelola urutan kunjungan melebar.
visited	Array penanda untuk mencegah pemrosesan vertex yang berulang.

C. Modifikasi menjadi Weighted Graph

Deskripsi (Fungsi) Program: 

Program ini melakukan modifikasi pada graf agar setiap sisi memiliki nilai bobot numerik, yang merupakan langkah persiapan untuk mengimplementasikan algoritma jalur terpendek.

Code:

// Modifikasi menjadi Weighted Graph

#include <iostream>

#include <vector>

using namespace std;

typedef pair<int, int> pii;

struct WeightedGraph {

int V;

vector<vector<pii>> adj;

WeightedGraph(int V) : V(V), adj(V) {}

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

void print() {

for(int i = 0; i < V; ++i) {

cout << "Vertex " << i << ": ";

for(auto& edge : adj[i]) cout << "(" << edge.first << ",w=" << edge.second << ") ";

cout << endl;

}

}

};

int main() {

WeightedGraph wg(8);

wg.addEdge(0, 1, 5);

wg.print();

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
struct WeightedGraph	Wadah untuk mendefinisikan graf dengan bobot.
pair<int, int>	Menyimpan tetangga beserta bobot sisi (weight).
print()	Menampilkan hubungan vertex beserta nilai bobotnya.

D. Implementasi Dijkstra

Deskripsi (Fungsi) Program: 

Program ini menerapkan algoritma Dijkstra secara mandiri untuk mencari jalur terpendek dari vertex 0 ke vertex lain dalam graf berbobot yang telah ditentukan.

Code:

// Implementasi Dijkstra

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

typedef pair<int, int> pii;

struct WeightedGraph {

int V;

vector<vector<pii>> adj;

WeightedGraph(int V) : V(V), adj(V) {}

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

void Dijkstra(int start) {

vector<int> dist(V, INT_MAX);

priority_queue<pii, vector<pii>, greater<pii>> pq;

dist[start] = 0; pq.push({0, start});

while(!pq.empty()) {

int d = pq.top().first, u = pq.top().second; pq.pop();

if(d > dist[u]) continue;

for(auto& edge : adj[u]) {

if(dist[u] + edge.second < dist[edge.first]) {

dist[edge.first] = dist[u] + edge.second;

pq.push({dist[edge.first], edge.first});

}

}

}

for(int i=0; i<V; ++i) cout << "Jarak terpendek ke " << i << ": " << dist[i] << endl;

}

};

int main() {

WeightedGraph wg(8);

wg.addEdge(0, 1, 4); wg.addEdge(0, 2, 1);

wg.Dijkstra(0);

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
dist	Penyimpanan jarak terpendek yang diperbarui secara dinamis.
greater<pii>	Pengatur priority queue agar nilai terkecil selalu diproses lebih dulu.
INT_MAX	Nilai batas maksimal untuk inisialisasi jarak awal yang tak terhingga.

E. Simulasi Jaringan Sosial

Deskripsi (Fungsi) Program: 

Program ini mensimulasikan hubungan sosial antar individu menggunakan map dan vector untuk mempermudah identifikasi pertemanan berbasis nama string dibandingkan indeks angka.

Code:

// Simulasi Jaringan Sosial

#include <iostream>

#include <vector>

#include <map>

#include <string>

using namespace std;

class SocialNetwork {

map<string, vector<string>> network;

public:

void addFriendship(string p1, string p2) {

network[p1].push_back(p2);

network[p2].push_back(p1);

}

void showNetwork() {

for(auto const& [person, friends] : network) {

cout << person << " berteman dengan: ";

for(auto const& f : friends) cout << f << " ";

cout << endl;

}

}

};

int main() {

SocialNetwork sn;

sn.addFriendship("Andi", "Budi");

sn.addFriendship("Budi", "Citra");

sn.showNetwork();

return 0;

}

Hasil/Output Program:

Penjelasan Program:

Bagian Program	Penjelasan
map<string, ...>	Memetakan nama orang langsung ke daftar teman-temannya.
addFriendship	Fungsi untuk mencatat hubungan pertemanan dua arah.
showNetwork	Iterasi melalui map untuk menampilkan daftar teman tiap individu.