• Beranda
  • Kelas
  • Blog
  • Lainnya
    • Event
    • Webinar
      • DaftarLogin
    InformatikawanInformatikawan
    • Beranda
    • Kelas
    • Blog
    • Lainnya
      • Event
      • Webinar
      • DaftarLogin

      Analisis Algoritma

      • Beranda
      • Blog
      • Analisis Algoritma
      • Minimum Spanning Tree – Algoritma Prim

      Minimum Spanning Tree – Algoritma Prim

      • Ditulis oleh Muhammad Fadillah Arsa
      • Kategori Analisis Algoritma
      • Tanggal 16/05/2019
      • Komentar 0 komentar

      DEFINISI

      Pohon rentangan adalah total weight (bobot) semua edge dalam pohon dan tidak jarang pohon rentangan bisa berjumlah lebih dari satu. Istilah Minimum spanning tree merujuk kepada pohon rentangan yang memiliki kompleksitas terendah di antara semua pohon rentangan. Sama halnya dengan pohon rentangan pada umumnya, (pohon rentangan minimum) juga bisa berjumlah lebih dari satu.

      ALGORITMA PRIM

      Algoritme Prim juga menggunakan pendekatan greedy untuk menemukan minimum spanning tree. Dalam algoritme Prim, kita mengembangkan spanning tree dari posisi asal. Bagian yang berbeda dari algoritme Kruskal adalah ditambahkannya edge ke growing spanning tree; sedangkan pada algoritme Prim, verteks yang ditambahkan ke growing spanning tree.

      LANGKAH ALGORITMA

      1. Terdapat dua disjoint set verteks. Salah satu disjoint set berisi verteks dalam growing spanning tree, dan yang lainnya berisi verteks yang tidak dalam growing spanning tree.
      2. Pilih verteks paling ringan yang terhubung dengan growing spanning tree dan yang tidak dalam growing spanning tree lalu tambahkan ke growing spanning tree. Hal ini dapat dilakukan menggunakan Priority Queue. Sisipkan verteks yang ada dalam growing spanning tree ke dalam Priority Queue.
      3. Pastikan tidak ada siklus yang terjadi. Untuk melakukan hal tersebut, tandai node yang sudah dipilih dan hanya sisipkan node yang tidak bertanda ke dalam Priority Queue.

      TAHAP 1

      Simpul r sebagai simpul start.

      TAHAP 2

      Memilih simpul t karena memiliki nilai jarak terkecil dibandingkan simpul lainnya yang terhubung ke simpul r.

      TAHAP 3

      Memilih simpul x karena memiliki nilai jarak terkecil dibandingkan simpul lainnya yang terhubung ke simpul t.

      TAHAP 4

      Memilih simpul s karena memiliki nilai jarak terkecil dibandingkan simpul lainnya yang terhubung ke simpul t atau x.

      TAHAP 5

      Memilih simpul w karena memiliki nilai jarak terkecil dibandingkan simpul lainnya yang terhubung ke simpul t atau x.

      TAHAP 6

      Memilih simpul v karena memiliki nilai jarak terkecil dibandingkan simpul lainnya yang terhubung ke simpul t, x, atau w.

      TAHAP 7

      Memilih simpul u karena memiliki nilai jarak terkecil dibandingkan simpul lainnya yang terhubung ke simpul t atau x.

      TAHAP 8

      Memilih simpul y karena memiliki nilai jarak terkecil dibandingkan simpul lainnya yang terhubung ke simpul x.

      HASIL

      • Bagikan:
      Muhammad Fadillah Arsa
      Founder Informatikawan dan Digidik. Mengenyam pendidikan di S1 Teknik Informatika Universitas Padjadjaran. Penulis buku Buku Sakti WordPress. Selengkapnya www.fadillaharsa.id

      Pos sebelumnya

      Bandwith dan Throughput: Pengertian, Perbedaan, dan Faktor yang Memengaruhi Keduanya
      16/05/2019

      Pos selanjutnya

      Modul Aljabar Linear untuk Teknik Informatika
      10/06/2019

      Mungkin kamu juga suka

      ilustrasi-mergesort
      #SourceCode Merge Sort C++
      18 Juni, 2019
      ebook informatika
      Ebook: Introduction to Algorithms Third Edition – Thomas H. Cormen
      10 Juni, 2019
      modul analisis algoritma
      Modul Analisis Algoritma untuk Teknik Informatika
      10 Juni, 2019

      Cari

      Pos-pos Terbaru

      • Webinar Flutter for Startup with Ilzam Mulkhaq 05/11/2020
      • Webinar UI/UX Designer with Yunilucki Siswantari 05/11/2020
      • Algoritma Rabin Karp – Metode Pencarian String 15/10/2020

      Kelas Populer

      Ethical Hacking Practical

      Ethical Hacking Practical

      Kelas Terbaru

      UI/UX Design

      UI/UX Design

      Aplikasi Web dengan Python Django

      Aplikasi Web dengan Python Django

      WHATSAPP 3 ADMIN
      BANDUNG INDONESIA
      INFORMATIKAWAN @GMAIL.COM
      BUKA SENIN - SABTU MINGGU: SLOWRESPON

      Informatikawan adalah platform pembelajaran bidang informatika. Menyediakan materi yang lengkap, terarah, dan dibimbing oleh pengajar berpengalaman di bidangnya.

      Fitur

      • Cara Belajar
      • Cara Membeli Kelas

      Lainnya

      • Aturan Penggunaan
      • Kebijakan Privasi
      • Refund Policy
      • Kontak Kami

      Menerima Berbagai Metode Pembayaran

      • ATM Bersama - Pembayaran Informatikawan
      • Prima - Pembayaran Informatikawan
      • Alto - Pembayaran Informatikawan
      • Bank BNI - Pembayaran Informatikawan
      • Bank Mandiri - Pembayaran Informatikawan
      • QRIS - Pembayaran Informatikawan
      • GOPAY GOJEK - Pembayaran Informatikawan
      • LinkAja - Pembayaran Informatikawan
      • OVO - Pembayaran Informatikawan
      • DANA - Pembayaran Informatikawan

      Informatikawan © 2020

      Login with your site account

      Masuk dengan Facebook Masuk dengan Google


      Lost your password?

      Not a member yet? Register now

      Register a new account

      Are you a member? Login now

      Tanya Kelas Berbayar
      Chat Whatsapp kami untuk bertanya perihal kelas online berbayar.
      * Hanya untuk bertanya perihal kelas online berbayar.
      Muhammad Fadillah Arsa
      Admin
      Muhammad Hafidz Alfarizi
      Admin
      I will be back soon
      Naufal Ariful Amri
      Admin