praktikum 12 .Menerapkan algoritma graf dalam pemrograman.

Kumpulan Soal Praktikum Bahasa C

Soal Praktek 1: Sistem Manajemen Buku 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.

Codingan:

#include <stdio.h> #include <stdlib.h> #include <string.h> // Struktur data untuk pengguna dalam jaringan sosial typedef struct User { char nama[50]; int umur; struct User* teman; struct User* next; } User; // Fungsi untuk menambahkan pengguna baru ke dalam jaringan sosial 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; } } // Fungsi untuk menambahkan koneksi teman antara dua pengguna 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; } } // Fungsi untuk mencari pengguna berdasarkan nama 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; } // Fungsi untuk menampilkan daftar teman dari seorang pengguna 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"); } // Fungsi utama int main() { User* head = NULL; // Menambahkan pengguna baru tambahPengguna(&head, "Andi", 25); tambahPengguna(&head, "Budi", 30); tambahPengguna(&head, "Cindy", 28); // Menambahkan koneksi teman User* pengguna1 = cariPengguna(head, "Andi"); User* pengguna2 = cariPengguna(head, "Budi"); tambahTeman(pengguna1, pengguna2); pengguna1 = cariPengguna(head, "Andi"); pengguna2 = cariPengguna(head, "Cindy"); tambahTeman(pengguna1, pengguna2); // Menampilkan daftar teman dari seorang pengguna pengguna1 = cariPengguna(head, "Andi"); tampilkanTeman(pengguna1); return 0; }

Hasil:

Output Program

Analisa Program:

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.

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.

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <limits.h> // Include for INT_MAX #define MAX_VERTICES 10 // Struktur data untuk merepresentasikan graf typedef struct { int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]; int numVertices; } TransportationSystem; // Fungsi untuk membuat sistem transportasi kosong 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; // Inisialisasi matriks dengan 0 } } return system; } // Fungsi untuk menambahkan rute baru antara dua titik dalam sistem transportasi void addRoute(TransportationSystem* system, int source, int destination, int distance) { system->adjacencyMatrix[source][destination] = distance; system->adjacencyMatrix[destination][source] = distance; // Untuk graf tak terarah } // Fungsi untuk menampilkan rute terpendek antara dua titik dalam sistem transportasi 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; // Set jarak awal ke tak terhingga } distances[source] = 0; for (int count = 0; count < system.numVertices - 1; count++) { int minDistance = INT_MAX; int minVertex = -1; 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] > 0 && 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]); } // Fungsi utama int main() { TransportationSystem system = createTransportationSystem(6); // Menambahkan rute-rute antara titik-titik dalam sistem transportasi 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); // Menampilkan rute terpendek antara dua titik displayShortestRoute(system, 0, 5); return 0; }

Hasil:

Output Program

Analisa Program:

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.

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.

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_DEVICES 10 // Struktur data untuk representasi graf typedef struct { bool adjMatrix[MAX_DEVICES][MAX_DEVICES]; int numDevices; } Network; // Fungsi untuk membuat jaringan komputer kosong 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; // Inisialisasi matriks dengan false } } return network; } // Fungsi untuk menambahkan koneksi antara dua perangkat dalam jaringan komputer void addConnection(Network* network, int device1, int device2) { network->adjMatrix[device1][device2] = true; network->adjMatrix[device2][device1] = true; // Untuk graf tak terarah } // Fungsi untuk menampilkan daftar perangkat yang terhubung dengan perangkat tertentu 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"); } // Fungsi untuk mencari komunitas atau kelompok perangkat dalam jaringan komputer 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("Komunitas: %d ", i); visited[i] = true; // Menggunakan DFS untuk menemukan semua perangkat dalam komunitas ini 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"); } // Fungsi utama int main() { Network network = createNetwork(6); // Menambahkan koneksi antara perangkat-perangkat dalam jaringan komputer 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); // Menampilkan perangkat yang terhubung dengan perangkat tertentu displayConnectedDevices(network, 2); // Mencari komunitas dalam jaringan komputer findCommunity(network); return 0; }

Hasil:

Output Program

Analisa Program:

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. Politeknik Semen Indonesia Program Studi Diploma Tiga Teknologi Informasi 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.

Eka Kurniawan Zein

Program Studi: Teknologi Informasi

"Pengalaman adalah guru yang terbaik, hari ini harus lebih baik dari hari kemarin."

Dosen Pembimbing: Pak Totok Mulyono