PRAKTIKUM 12: Menerapkan algoritma graf dalam pemrograman.
IV. Alat/Bahan
• Komputer dengan lingkungan pemrograman C (misalnya, GCC atau Dev-C++).
• Editor teks untuk menulis kode C. Code::Blocks
• Compiler atau interpreter untuk menjalankan kode C.
• Buku atau materi referensi tentang pemrograman dalam bahasa C.
• .Modul 12 Menerapkan algoritma graf dalam pemrograman..
V. Prosedur Praktikum
Praktekan Latihan Berikut:
Soal Praktek 1: Jaringan Sosial
Andi ingin mengimplementasikan sebuah program menggunakan algoritma graf untuk
memodelkan jaringan sosial. Setiap pengguna dalam jaringan sosial memiliki informasi seperti
nama, umur, dan daftar teman. Program tersebut harus memiliki fitur sebagai berikut:
✓ Menambahkan pengguna baru ke dalam jaringan sosial.
✓ Menambahkan koneksi teman antara dua pengguna.
✓ Menampilkan daftar teman dari seorang pengguna.
✓ Menampilkan jalur terpendek antara dua pengguna.
Soal Praktek 2: Sistem Transportasi
Budi ingin membuat program menggunakan algoritma graf untuk memodelkan sistem transportasi
di kota. Setiap simpul dalam graf mewakili titik atau tempat, dan setiap tepi mewakili jalan atau
rute antara dua titik. Program tersebut harus memiliki fitur sebagai berikut:
✓ Menambahkan titik baru ke dalam sistem transportasi.
✓ Menambahkan rute baru antara dua titik.
✓ Menampilkan rute terpendek antara dua titik.
✓ Menghapus titik atau rute dari sistem transportasi.
Soal Praktek 3: Analisis Jaringan Komputer
Cindy ingin mengimplementasikan program menggunakan algoritma graf untuk menganalisis
jaringan komputer. Setiap simpul dalam graf mewakili perangkat komputer, dan setiap tepi
mewakili koneksi antara dua perangkat. Program tersebut harus memiliki fitur sebagai berikut:
✓ Menambahkan perangkat baru ke dalam jaringan komputer.
✓ Menambahkan koneksi antara dua perangkat.
✓ Menampilkan daftar perangkat yang terhubung dengan suatu perangkat.
✓ Mencari komunitas atau kelompok perangkat dalam jaringan.
Dalam menyelesaikan tiga soal praktek ini, Anda dapat menggunakan struktur data graf dan
algoritma-algoritma terkait seperti traversal graf, pencarian jalur terpendek, atau algoritma
clustering yang sesuai dengan masalah yang diberikan.
1. Jawaban Soal Praktek 1: Jaringan Sosial
▪ Buka Text Editor Code::Blocks,
▪ Pilih menu klik file → New→Empty File
▪ Ketikan koding di bawah ini
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef struct User {
char nama[50];
int umur;
struct User* teman;
struct User* next;
} User;
void tambahPengguna(User** head, char nama[], int umur) {
User* penggunaBaru = (User*)malloc(sizeof(User));
strcpy(penggunaBaru->nama, nama);
penggunaBaru->umur = umur;
penggunaBaru->teman = NULL;
penggunaBaru->next = NULL;
if (*head == NULL) {
*head = penggunaBaru;
} else {
User* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = penggunaBaru;
}
}
void tambahTeman(User* pengguna1, User* pengguna2) {
User* temanBaru = (User*)malloc(sizeof(User));
strcpy(temanBaru->nama, pengguna2->nama);
temanBaru->umur = pengguna2->umur;
temanBaru->teman = NULL;
temanBaru->next = NULL;
if (pengguna1->teman == NULL) {
pengguna1->teman = temanBaru;
} else {
User* temp = pengguna1->teman;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = temanBaru;
}
}
User* cariPengguna(User* head, char nama[]) {
User* temp = head;
while (temp != NULL) {
if (strcmp(temp->nama, nama) == 0) {
return temp;
}
temp = temp->next;
}
return NULL;
}
void tampilkanTeman(User* pengguna) {
printf("Daftar Teman untuk Pengguna %s:\n", pengguna->nama);
User* temp = pengguna->teman;
while (temp != NULL) {
printf("- %s\n", temp->nama);
temp = temp->next;
}
printf("\n");
}
int main() {
User* head = NULL;
tambahPengguna(&head, "Andi", 25);
tambahPengguna(&head, "Budi", 30);
tambahPengguna(&head, "Cindy", 28);
User* pengguna1 = cariPengguna(head, "Andi");
User* pengguna2 = cariPengguna(head, "Budi");
tambahTeman(pengguna1, pengguna2);
pengguna1 = cariPengguna(head, "Andi");
pengguna2 = cariPengguna(head, "Cindy");
tambahTeman(pengguna1, pengguna2);
pengguna1 = cariPengguna(head, "Andi");
tampilkanTeman(pengguna1);
return 0;
}
▪ Klik menu file Save, ketikan nama
▪ Klik Build →Build and Run atau icon
▪ berikut hasilnya
Program di atas mengimplementasikan struktur data graf untuk
memodelkan jaringan sosial. Setiap pengguna direpresentasikan
sebagai simpul dalam graf dengan informasi seperti nama, umur,
dan daftar teman.
Fungsi tambahPengguna digunakan untuk menambahkan pengguna
baru ke dalam jaringan sosial. Setiap pengguna baru akan
ditambahkan sebagai simpul baru dalam graf.
Fungsi tambahTeman digunakan untuk menambahkan koneksi teman
antara dua pengguna. Koneksi teman akan ditambahkan sebagai
tepi antara dua simpul dalam graf.
Fungsi cariPengguna digunakan untuk mencari pengguna
berdasarkan nama. Fungsi ini digunakan untuk mencari pengguna
yang ingin ditambahkan sebagai teman atau untuk menampilkan
daftar teman dari seorang pengguna.
Fungsi tampilkanTeman digunakan untuk menampilkan daftar teman
dari seorang pengguna. Fungsi ini akan mencetak nama-nama teman
yang terhubung dengan pengguna tersebut.
Pada program utama, beberapa pengguna dan koneksi teman
ditambahkan ke jaringan sosial, dan kemudian daftar teman dari
pengguna "Andi" ditampilkan.
2. Jawaban Soal Praktek 2: Sistem Transportasi
▪ Buka Text Editor Code::Blocks,
▪ Pilih menu klik file → New→Empty File
▪ Ketikan koding di bawah ini
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_VERTICES 10
typedef struct {
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
int numVertices;
} TransportationSystem;
TransportationSystem createTransportationSystem(int numVertices) {
TransportationSystem system;
system.numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
system.adjacencyMatrix[i][j] = 0;
}
}
return system;
}
void addRoute(TransportationSystem* system, int source, int destination, int distance) {
system->adjacencyMatrix[source][destination] = distance;
system->adjacencyMatrix[destination][source] = distance;
}
void displayShortestRoute(TransportationSystem system, int source, int destination) {
int distances[MAX_VERTICES];
bool visited[MAX_VERTICES] = {false};
for (int i = 0; i < system.numVertices; i++) {
distances[i] = INT_MAX;
}
distances[source] = 0;
for (int count = 0; count < system.numVertices - 1; count++) {
int minDistance = INT_MAX;
int minVertex;
for (int v = 0; v < system.numVertices; v++) {
if (!visited[v] && distances[v] <= minDistance) {
minDistance = distances[v];
minVertex = v;
}
}
visited[minVertex] = true;
for (int v = 0; v < system.numVertices; v++) {
if (!visited[v] && system.adjacencyMatrix[minVertex][v] && distances[minVertex] != INT_MAX && distances[minVertex] + system.adjacencyMatrix[minVertex][v] < distances[v]) {
distances[v] = distances[minVertex] + system.adjacencyMatrix[minVertex][v];
}
}
}
printf("Rute terpendek dari Titik %d ke Titik %d adalah %d\n", source, destination, distances[destination]);
}
int main() {
TransportationSystem system = createTransportationSystem(6);
addRoute(&system, 0, 1, 5);
addRoute(&system, 0, 2, 3);
addRoute(&system, 1, 3, 2);
addRoute(&system, 2, 3, 4);
addRoute(&system, 2, 4, 6);
addRoute(&system, 3, 4, 1);
addRoute(&system, 4, 5, 3);
displayShortestRoute(system, 0, 5);
return 0;
}
▪ Klik menu file Save, ketikan nama
▪ Klik Build →Build and Run atau icon
▪ berikut hasilnya
Program di atas menggunakan algoritma graf untuk memodelkan
sistem transportasi di kota.Pada program ini, struktur data
graf direpresentasikan menggunakan matriks ketetanggaan dalam
variabel adjacencyMatrix. Setiap elemen matriks menyatakan
jarak atau biaya antara dua titik dalam sistem transportasi.
Fungsi createTransportationSystem digunakan untuk membuat
sistem transportasi kosong dengan jumlah titik yang
ditentukan. Matriks ketetanggaan diinisialisasi dengan nilai
0, menunjukkan bahwa belum ada rute antara titik-titik.
Fungsi addRoute digunakan untuk menambahkan rute baru antara
dua titik dalam sistem transportasi. Fungsi ini mengatur nilai
pada matriks ketetanggaan sesuai dengan jarak antara titik-
titik tersebut.
Fungsi displayShortestRoute digunakan untuk mencari dan
menampilkan rute terpendek antara dua titik dalam sistem
transportasi. Fungsi ini menggunakan pendekatan Dijkstra untuk
mencari jarak terpendek menggunakan algoritma Greedy.
Pada program utama, sebuah sistem transportasi dibuat dengan
menambahkan rute-rute antara titik-titik. Kemudian, fungsi
displayShortestRoute dipanggil untuk mencari dan menampilkan
rute terpendek antara dua titik yang ditentukan.
3. Jawaban Soal Praktek 3: Analisis Jaringan Komputer
▪ Buka Text Editor Code::Blocks,
▪ Pilih menu klik file → New→Empty File
▪ Ketikan koding di bawah ini
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_DEVICES 10
typedef struct {
bool adjMatrix[MAX_DEVICES][MAX_DEVICES];
int numDevices;
} Network;
Network createNetwork(int numDevices) {
Network network;
network.numDevices = numDevices;
for (int i = 0; i < numDevices; i++) {
for (int j = 0; j < numDevices; j++) {
network.adjMatrix[i][j] = false;
}
}
return network;
}
void addConnection(Network* network, int device1, int device2) {
network->adjMatrix[device1][device2] = true;
network->adjMatrix[device2][device1] = true;
}
void displayConnectedDevices(Network network, int device) {
printf("Perangkat yang terhubung dengan Perangkat %d:\n", device);
for (int i = 0; i < network.numDevices; i++) {
if (network.adjMatrix[device][i]) {
printf("%d\n", i);
}
}
printf("\n");
}
void findCommunity(Network network) {
bool visited[MAX_DEVICES] = {false};
printf("Komunitas dalam Jaringan Komputer:\n");
for (int i = 0; i < network.numDevices; i++) {
if (!visited[i]) {
printf("%d ", i);
visited[i] = true;
for (int j = 0; j < network.numDevices; j++) {
if (network.adjMatrix[i][j] && !visited[j]) {
printf("%d ", j);
visited[j] = true;
}
}
printf("\n");
}
}
printf("\n");
}
int main() {
Network network = createNetwork(6);
addConnection(&network, 0, 1);
addConnection(&network, 0, 2);
addConnection(&network, 1, 3);
addConnection(&network, 2, 3);
addConnection(&network, 2, 4);
addConnection(&network, 3, 4);
addConnection(&network, 4, 5);
displayConnectedDevices(network, 2);
findCommunity(network);
return 0;
}
▪ Klik menu file Save, ketikan nama
▪ Klik Build →Build and Run atau icon
▪ berikut hasilnya
Program di atas mengimplementasikan algoritma graf untuk menganalisis jaringan
komputer. Setiap simpul dalam graf mewakili perangkat komputer, dan setiap tepi mewakili
koneksi antara dua perangkat.
Fungsi createNetwork digunakan untuk membuat jaringan komputer kosJawaban script di
atas mengimplementasikan algoritma graf untuk menganalisis jaringan komputer. Program
ini menggunakan struktur data graf untuk merepresentasikan perangkat-perangkat dalam
jaringan komputer dan koneksi antara perangkat-perangkat tersebut.
Fungsi createNetwork digunakan untuk membuat jaringan komputer kosong dengan jumlah
perangkat yang ditentukan. Fungsi ini menginisialisasi matriks ketetanggaan dengan nilai
false yang menunjukkan bahwa tidak ada koneksi awal antara perangkat-perangkat.
Fungsi addConnection digunakan untuk menambahkan koneksi antara dua perangkat dalam
jaringan komputer. Fungsi ini mengatur nilai pada matriks ketetanggaan sesuai dengan
koneksi antara perangkat-perangkat tersebut.
Fungsi displayConnectedDevices digunakan untuk menampilkan daftar perangkat yang
terhubung dengan perangkat tertentu. Fungsi ini melakukan iterasi pada matriks
ketetanggaan untuk mencari perangkat-perangkat terhubung dengan perangkat yang
ditentukan.
Fungsi findCommunity digunakan untuk mencari komunitas atau kelompok perangkat
dalam jaringan komputer. Fungsi ini menggunakan pendekatan Depth-First Search (DFS)
untuk mencari kelompok-kelompok terhubung dalam graf.
Pada program utama, sebuah jaringan komputer dibuat dengan menambahkan koneksi antara
perangkat-perangkat. Kemudian, fungsi displayConnectedDevices dipanggil untuk
menampilkan perangkat yang terhubung dengan perangkat tertentu. Selanjutnya, fungsi
findCommunity dipanggil untuk mencari dan menampilkan komunitas dalam jaringan
komputer.
Comments
Post a Comment