 |
| Soal Graph |
Dari graph diatas ini, buatlah program (boleh dalam bahasa pemrograman apapun – selain pseudocode) yang melakukan:
1. Representasi graph dalam bentuk adjacency matrix
2. Buatlah fungsi untuk menghitung degree dari sebuah vertex. Fungsi ini memiliki input Array dari graph dan vertex yang dihitung
3. Jalankan fungsi tersebut untuk semua vertex
4. Buatlah fungsi untuk menghitung jarak terpendek menggunakan algoritma Djikstra. Fungsi yang dibuat memiliki input Array dari graph dan vertex asal, outputnya berupa
jarak terpendek ke setiap vertex dan lintasannya
5. Jalankan fungsi tersebut untuk setiap vertex dalam graph
6. Jika program lebih dari 1 file source code, zip semua file dan submit di dropbox e- learning. Program tidak perlu di-compile, cukup source code saja.
Jawab :
- Adjacency Matrix
 |
| Adjacency Matrix |
- Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Jumlah degree selalu genap.
Jumlah degree adalah 2 kali jumlah sisi (edge).
Edge = 12 buah { (A-B),(A-C),(A-D),(B-D),(B-E),(C-D),(C-F),(D-E),(D-F),(D-G),(E-G),(F-G) }
Maka jumlah degree adalah 2 x 12 = 24
Dengan rincian : d(A) + d(B) + d(C) + d(D) + d(E) + d(F) + d(G)
: 3 + 3 + 3 + 6 + 3 + 3 + 3
: 24
- Jarak terpendek menggunakan Algoritma Djikstra
 |
| Jarak Terpendek |
No comments:
Post a Comment