algoritma kruskal prim dan dikstral
DESCRIPTION
Matematik KeputusanTRANSCRIPT
Matematik Keputusan :Rangkaian
Pembentang:Tan Li Peng
Teo Mey Lian
Apa itu Algoritma
• Algoritma merupakan langkah-langkah (prosedur) yang harus dilakukan untuk menyelesaikan sebuah masalah.
• Melibatkan Pengiraan.
• Melibatkan Formula
Apa itu Rangkaian•Rangkaian ialah sekumpulan komputer yang dihubungkan untuk berkongsi perkakasan, perisian dan maklumat.
•Rangkaian biasanya terdapat dalam organisasi besar atau bangunan-bangunan berdekatan.
•Setiap komputer atau peranti di dalam rangkaian dinamakan node.
- Bentuk susunan node atau cara node disambungkan untuk membentuk rangkaian dikenali sebagai topologi rangkaian.
Jenis-Jenis Algoritma
1. Algoritma Kruskal
2. Algoritma Prim
3. Algoritma Djikstra
Algoritma Kruskal
• digunakan untuk mencari penghubung yang minimum bagi kesemua titik atau bucu.
• Algoritma Kruskal dimulakan dengan memilih memilih sisi yang terpendek.
• Tiada kitaran berlaku.
• berhenti apabila semua titik dan bucu dalam sesuatu rangkaian telah bersambung.
Contoh soalan Kruskal:Cari laluan yang terpendek bagi rajah di bawah
2
4
6
2
2
3
1
1
2
5
10
5
7
O
F
Jawapannya
2
2
3
1
1
2
5
Jumlah laluan = 2+3+2+1+1+2+5= 16
Algoritma Prim
• Algoritma dimulai dari suatu verteks awal tertentu
• biasanya ditentukan oleh pemanggil atau dipilih sebarangan oleh algoritma.
• Misalnya verteks awal tersebut adalah v.
Contoh Algoritma Prim
Algoritma Djikstra• digunakan untuk mencari jalan atau jarak
terpendek bagi 2 titik tertentu yang terdapat dalam rangkaian.
• Bagi Algoritma Dijkstra, semua bucu dalam rangkaian tidak wajib disambung kesemuanya berbanding dengan Algoritma Kruskal yang mewajibkan semua bucu perlu bersambung.
Contoh
Sekian
Terima Kasih