Praktikum 12 dan Praktikum 13 (Coding Bahasa C: Algoritma graf dan algoritma greedy)

 

Praktikum 12 (Algoritma Graf)

A. Persoalan

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. 

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.

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. 

B. Jawaban

1. Jaringan Sosial:

• Koding Bahasa C:
  
  #include <stdio.h>

  #include <stdlib.h>

  #include <stdbool.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) {

              if (strcmp(temp->nama, pengguna2->nama) == 0) {

                  // Teman sudah ada, hentikan penambahan

                  free(temanBaru);

                  return;

              }

              temp = temp->next;

          }

          temp->next = temanBaru;

      }

  }

  
  

  // Fungsi untuk mencari pengguna berdasarkan nama (case-insensitive)

  User* cariPengguna(User* head, char nama[]) {

      User* temp = head;

      while (temp != NULL) {

          if (strcasecmp(temp->nama, nama) == 0) {

              return temp;

          }

          temp = temp->next;

      }

      return NULL;

  }

  
  

  // Fungsi untuk menampilkan daftar 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:
  
  
  

2. Sistem Transportasi:

• Koding Bahasa C:
  
  #include <stdio.h>

  #include <stdlib.h>

  #include <stdbool.h>

  #include <limits.h>

  
  

  #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;

          }

      }

  
  

      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;

  }

  
  

  // 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;

      }

  
  

      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]);

  }

  
  

  // 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:
  
  
  
  
  

3.  Analisis Jaringan Komputer:

• Koding Bahasa C:
  
  #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;

          }

      }

  
  

      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;

  }

  
  

  // 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("%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");

  }

  
  

  // 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:
  
  

 

 

 

 

Praktikum 13 (Algoritma Greedy)

A. Persoalan

1. Penjadwalan Tugas:

Budi memiliki sejumlah tugas yang perlu diselesaikan dengan waktu mulai dan waktu selesai  tertentu, serta bobot atau keuntungan yang terkait dengan setiap tugas. Budi ingin  menggunakan algoritma greedy untuk menjadwalkan tugas-tugas tersebut sehingga  keuntungan total maksimum diperoleh. Implementasikan program dalam bahasa C yang dapat  menerima input tugas-tugas beserta waktu mulai, waktu selesai, dan bobotnya, dan  menampilkan urutan pelaksanaan tugas yang menghasilkan keuntungan total maksimum. 

2. Penyelesaian Persamaan Linear:

 Andi ingin menyelesaikan sebuah persamaan linier dengan jumlah variabel dan persamaan  yang diberikan. Setiap persamaan memiliki koefisien variabel dan hasil yang diinginkan. Andi  ingin menggunakan algoritma greedy untuk mencari solusi yang memenuhi persamaan persamaan tersebut. Implementasikan program dalam bahasa C yang dapat menerima input  koefisien variabel, hasil, dan persamaan-persamaan, dan menampilkan solusi variabel yang  memenuhi persamaan-persamaan tersebut.

3. Penyelesaian Salesman Traveling Problem: 

 Cindy adalah seorang sales yang ingin mengunjungi sejumlah kota untuk menjual produknya.  Setiap kota memiliki jarak yang terkait dengan kota lainnya. Cindy ingin menggunakan  algoritma greedy untuk menemukan rute perjalanan terpendek yang melintasi semua kota  sekali dan kembali ke kota awal. Implementasikan program dalam bahasa C yang dapat  menerima input jarak antar kota dan menampilkan rute perjalanan terpendek yang memenuhi  persyaratan tersebut.

B. Jawaban

1. Penjadwalan Tugas:

• Koding Bahasa C:
  
  #include <stdio.h>

  #include <stdlib.h>

  
  

  // Definisikan struktur untuk tugas

  typedef struct {

      int waktuMulai;

      int waktuSelesai;

      int bobot;

  } Tugas;

  
  

  // Fungsi pembanding untuk pengurutan tugas berdasarkan waktu selesai

  int compare(const void *a, const void *b) {

      Tugas *tugasA = (Tugas *)a;

      Tugas *tugasB = (Tugas *)b;

      return tugasA->waktuSelesai - tugasB->waktuSelesai;

  }

  
  

  // Fungsi untuk menentukan urutan pelaksanaan tugas dengan keuntungan total maksimum

  void jadwalTugas(Tugas tugas[], int n) {

      // Urutkan tugas berdasarkan waktu selesai

      qsort(tugas, n, sizeof(Tugas), compare);

  
  

      int i, j;

      int *hasil = (int *)malloc(n * sizeof(int)); // Array untuk menyimpan hasil urutan pelaksanaan tugas

      hasil[0] = 0; // Tugas pertama selalu dipilih

  
  

      // Tentukan tugas selanjutnya dengan bobot terbesar yang tidak tumpang tindih dengan tugas sebelumnya

      j = 0;

      for (i = 1; i < n; i++) {

          if (tugas[i].waktuMulai >= tugas[j].waktuSelesai) {

              hasil[++j] = i;

          }

      }

  
  

      // Tampilkan hasil urutan pelaksanaan tugas dan keuntungan total

      printf("Urutan Pelaksanaan Tugas: ");

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

          printf("%d ", hasil[i]);

      }

      printf("\n");

  
  

      int keuntunganTotal = 0;

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

          keuntunganTotal += tugas[hasil[i]].bobot;

      }

      printf("Keuntungan Total: %d\n", keuntunganTotal);

  
  

      free(hasil);

  }

  
  

  int main() {

      int n, i;

  
  

      printf("Masukkan jumlah tugas: ");

      scanf("%d", &n);

  
  

      Tugas *tugas = (Tugas *)malloc(n * sizeof(Tugas));

  
  

      printf("Masukkan waktu mulai, waktu selesai, dan bobot untuk setiap tugas:\n");

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

          printf("Tugas %d: ", i + 1);

          scanf("%d %d %d", &tugas[i].waktuMulai, &tugas[i].waktuSelesai, &tugas[i].bobot);

      }

  
  

      jadwalTugas(tugas, n);

  
  

      free(tugas);

  
  

      return 0;

  }
• Hasil:
  
  
  

2. Penyelesaian Persamaan Linear:

• Koding Bahasa C:
  
  #include <stdio.h>

  #include <stdlib.h>

  
  

  // Fungsi untuk mencari solusi persamaan linier dengan algoritma greedy

  void cariSolusi(int n, int m, double koefisien[][n], double hasil[]) {

      double solusi[n];

      int i, j;

  
  

      // Inisialisasi solusi awal dengan nilai 0

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

          solusi[i] = 0.0;

      }

  
  

      // Iterasi sebanyak jumlah persamaan

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

          int variabelTerbesar = -1;

          double nilaiVariabelTerbesar = 0.0;

  
  

          // Cari variabel dengan koefisien terbesar pada persamaan saat ini

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

              if (koefisien[i][j] > nilaiVariabelTerbesar) {

                  nilaiVariabelTerbesar = koefisien[i][j];

                  variabelTerbesar = j;

              }

          }

  
  

          // Hitung solusi untuk variabel tersebut

          solusi[variabelTerbesar] = hasil[i] / koefisien[i][variabelTerbesar];

  
  

          // Update persamaan lain dengan menggunakan solusi variabel tersebut

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

              if (koefisien[j][variabelTerbesar] != 0.0 && j != i) {

                  double faktor = koefisien[j][variabelTerbesar] / koefisien[i][variabelTerbesar];

                  for (int k = 0; k < n; k++) {

                      koefisien[j][k] -= faktor * koefisien[i][k];

                  }

                  hasil[j] -= faktor * hasil[i];

              }

          }

      }

  
  

      // Tampilkan solusi variabel

      printf("Solusi Variabel:\n");

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

          printf("x%d = %f\n", i + 1, solusi[i]);

      }

  }

  
  

  int main() {

      int n, m, i, j;

  
  

      printf("Masukkan jumlah variabel: ");

      scanf("%d", &n);

  
  

      printf("Masukkan jumlah persamaan: ");

      scanf("%d", &m);

  
  

      double koefisien[m][n];

      double hasil[m];

  
  

      printf("Masukkan koefisien variabel dan hasil untuk setiap persamaan:\n");

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

          printf("Persamaan %d: ", i + 1);

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

              scanf("%lf", &koefisien[i][j]);

          }

          scanf("%lf", &hasil[i]);

      }

  
  

      cariSolusi(n, m, koefisien, hasil);

  
  

      return 0;

  }
• Hasil:
  
  
  

3. Penyelesaian Traveling Salesman Problem:

• Koding Bahasa C:
  
  #include <stdio.h>

  #include <stdlib.h>

  
  

  #define MAX 10

  
  

  // Fungsi untuk menemukan rute perjalanan terpendek

  void temukanRuteTerpendek(int n, int jarak[MAX][MAX], int kotaAwal) {

      int rute[MAX];

      int kunjungan[MAX];

      int totalJarak = 0;

      int kunjunganTerakhir = kotaAwal;

  
  

      // Inisialisasi kunjungan dan rute

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

          kunjungan[i] = 0;

          rute[i] = -1;

      }

  
  

      // Set kota awal sebagai kunjungan pertama

      kunjungan[kotaAwal] = 1;

      rute[0] = kotaAwal;

  
  

      // Iterasi sebanyak jumlah kota - 1

      for (int i = 1; i < n; i++) {

          int jarakTerpendek = -1;

          int kotaTujuan = -1;

  
  

          // Cari kota tujuan dengan jarak terpendek dari kunjungan terakhir

          for (int j = 0; j < n; j++) {

              if (kunjungan[j] == 0 && (jarakTerpendek == -1 || jarak[kunjunganTerakhir][j] < jarakTerpendek)) {

                  jarakTerpendek = jarak[kunjunganTerakhir][j];

                  kotaTujuan = j;

              }

          }

  
  

          // Tandai kota tujuan sebagai kunjungan dan tambahkan ke rute

          kunjungan[kotaTujuan] = 1;

          rute[i] = kotaTujuan;

          totalJarak += jarakTerpendek;

          kunjunganTerakhir = kotaTujuan;

      }

  
  

      // Tambahkan kembali kota awal sebagai kunjungan terakhir

      totalJarak += jarak[kunjunganTerakhir][kotaAwal];

      rute[n] = kotaAwal;

  
  

      // Tampilkan rute perjalanan terpendek dan total jarak

      printf("Rute Perjalanan Terpendek:\n");

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

          printf("%d ", rute[i]);

      }

      printf("\nTotal Jarak: %d\n", totalJarak);

  }

  
  

  int main() {

      int n;

      int kotaAwal;

  
  

      printf("Masukkan jumlah kota: ");

      scanf("%d", &n);

  
  

      int jarak[MAX][MAX];

  
  

      printf("Masukkan jarak antar kota:\n");

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

          for (int j = 0; j < n; j++) {

              scanf("%d", &jarak[i][j]);

          }

      }

  
  

      printf("Masukkan kota awal: ");

      scanf("%d", &kotaAwal);

  
  

      temukanRuteTerpendek(n, jarak, kotaAwal);

  
  

      return 0;

  }
• Hasil: