Representasi Graph dan Link Download File Referensi
https://eu2.contabostorage.com/00f3241116844f24b628f46d81abb929:st1/folder8/8128/1656361381_representasi_graph___Matematika.pdf
2026-05-31 22:58:04 - Admin
<style> body{ font-family: Arial, Helvetica, sans-serif; line-height: 1.6; margin:0; padding:0 20px; background-color:#f9f9f9; color:#333; } h1, h2, h3{ color:#2c3e50; } nav{ background:#e2e8f0; padding:10px; margin-bottom:20px; } nav a{ margin-right:15px; text-decoration:none; color:#2c3e50; } section{ margin-bottom:30px; } pre{ background:#eee; padding:10px; overflow:auto; } table{ border-collapse:collapse; width:100%; margin-top:10px; } th, td{ border:1px solid #bbb; padding:8px; text-align:center; } th{ background:#d3d3d3; } .example{ background:#fff; border:1px solid #ccc; padding:15px; margin-top:10px; } </style><nav> <a href="#pengantar">Pengantar</a> <a href="#adjacency-matrix">Matriks Ketetanggaan</a> <a href="#adjacency-list">Daftar Ketetanggaan</a> <a href="#edge-list">Daftar Sisi</a> <a href="#pilihan-representasi">Pemilihan Representasi</a></nav><h1>Representasi Graf dalam Ilmu Komputer</h1><section id="pengantar"> <h2>Pengantar</h2> <p> Graf (graph) adalah struktur data yang terdiri atas himpunan simpul (vertex) dan sisi (edge) yang menghubungkan pasangan simpul. Graf banyak digunakan untuk memodelkan hubungan antarobjek, seperti jaringan jalan, jaringan sosial, rangkaian elektronik, dan lainlain. Karena graf dapat memiliki banyak bentuk (arah, berbobot, tidak berbobot, sederhana, multigraf, dll.), cara merepresentasikannya dalam memori komputer menjadi sangat penting. Representasi yang tepat memengaruhi efisiensi algoritmaalgoritma graf seperti pencarian lintasan, penentuan jarak terpendek, dan pencarian komponen terhubung. </p></section><section id="adjacency-matrix"> <h2>Matriks Ketetanggaan (Adjacency Matrix)</h2> <p> Matriks ketetanggaan adalah sebuah matriks berukuran <em>V V</em> (V adalah jumlah simpul). Elemen <em>A[i][j]</em> bernilai 1 (atau bobot sisi) jika terdapat sisi dari simpul <em>i</em> ke simpul <em>j</em>, dan 0 bila tidak ada. Untuk graf tak berarah, matriks bersifat simetris. </p> <h3>Keunggulan</h3> <ul> <li>Memeriksa keberadaan sisi antara dua simpul dapat dilakukan dalam <strong>O(1)</strong>.</li> <li>Implementasi sederhana, cocok untuk graf yang padat (banyak sisi).</li> <li>Mudah mengubah menjadi representasi lain, misalnya menambahkan bobot.</li> </ul> <h3>Kelemahan</h3> <ul> <li>Memakan ruang <strong>O(V)</strong>, tidak efisien untuk graf jarang.</li> <li>Mengiterasi semua tetangga sebuah simpul memerlukan <strong>O(V)</strong> walaupun hanya sedikit tetangga.</li> </ul> <div class="example"> <strong>Contoh:</strong> Graf tak berarah dengan 4 simpul dan sisi { (1,2), (2,3), (3,4) }<br> <pre> 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 </pre> </div></section><section id="adjacency-list"> <h2>Daftar Ketetanggaan (Adjacency List)</h2> <p> Daftar ketetanggaan menyimpan untuk setiap simpul sebuah daftar (biasanya linked list atau array dinamis) yang berisi semua tetangga yang terhubung dengan simpul tersebut. Representasi ini cocok untuk graf jarang, dimana <em>E</em> (jumlah sisi) jauh lebih kecil daripada <em>V</em>. </p> <h3>Keunggulan</h3> <ul> <li>Ruang yang dibutuhkan hanya <strong>O(V + E)</strong>.</li> <li>Mengiterasi tetangga suatu simpul berjalan dalam <strong>O(degree(v))</strong>, sehingga efisien untuk algoritma seperti DFS/BFS.</li> </ul> <h3>Kelemahan</h3> <ul> <li>Memeriksa apakah sisi (u,v) ada memerlukan waktu <strong>O(degree(u))</strong> atau pencarian linear dalam daftar.</li> <li>Implementasinya sedikit lebih kompleks dibanding matriks.</li> </ul> <div class="example"> <strong>Contoh:</strong> Representasi graf di atas menggunakan daftar ketetanggaan<br> <pre> 1 : 2 2 : 1, 3 3 : 2, 4 4 : 3 </pre> </div></section><section id="edge-list"> <h2>Daftar Sisi (Edge List)</h2> <p> Daftar sisi menyimpan setiap sisi dalam bentuk pasangan (u, v) atau tripel (u, v, w) bila berbobot. Representasi ini sangat sederhana dan berguna bila hanya diperlukan iterasi melalui semua sisi, misalnya dalam algoritma Kruskal. </p> <h3>Keunggulan</h3> <ul> <li>Sangat mudah dibangun, hanya sekadar array dari sisi.</li> <li>Ruang <strong>O(E)</strong>, paling efisien bila hanya membutuhkan daftar sisi.</li> </ul> <h3>Kelemahan</h3> <ul> <li>Menemukan semua tetangga sebuah simpul memerlukan pencarian linier <strong>O(E)</strong>.</li> <li>Operasi cek keberadaan sisi (u, v) juga <strong>O(E)</strong>.</li> </ul> <div class="example"> <strong>Contoh:</strong> Edge list graf sebelumnya<br> <pre> (1,2) (2,3) (3,4) </pre> </div></section><section id="pilihan-representasi"> <h2>Bagaimana Memilih Representasi yang Tepat?</h2> <p> Tidak ada satu representasi yang selalu paling baik. Pilihan bergantung pada karakteristik graf dan jenis operasi yang paling sering dilakukan. </p> <table> <tr> <th>Kriteria</th> <th>Matriks Ketetanggaan</th> <th>Daftar Ketetanggaan</th> <th>Daftar Sisi</th> </tr> <tr> <td>Ukuran graf (V, E)</td> <td>Bagus bila V kecil atau graf padat (E V)</td> <td>Bagus bila V besar dan E kecil (graf jarang)</td> <td>Ideal bila hanya iterasi semua sisi yang dibutuhkan</td> </tr> <tr> <td>Pencarian sisi (u,v)</td> <td>O(1)</td> <td>O(degree(u))</td> <td>O(E)</td> </tr> <tr> <td>Iterasi tetangga suatu simpul</td> <td>O(V)</td> <td>O(degree(v))</td> <td>O(E)</td> </tr> <tr> <td>Modifikasi (tambah/hapus sisi)</td> <td>O(1) untuk tambah di matriks; O(V) untuk hapus semua sisi terkait</td> <td>O(1) untuk tambah (jika menggunakan linked list); O(degree(v)) untuk hapus</td> <td>O(1) untuk tambah; O(E) untuk hapus</td> </tr> </table> <p> Contoh pilihan praktis: </p> <ul> <li><strong>Jalur transportasi kota</strong>: biasanya graf jarang, gunakan daftar ketetanggaan.</li> <li><strong>Jaringan sosial kecil</strong>: jika jumlah pengguna terbatas, matriks ketetanggaan mempermudah analisis hubungan langsung.</li> <li><strong>Algoritma Minimum Spanning Tree (Kruskal)</strong>: daftar sisi lebih mudah diproses setelah diurutkan.</li> </ul></section><section> <h2>Kesimpulan</h2> <p> Representasi graf merupakan fondasi bagi semua algoritma graf. Matriks ketetanggaan memberikan kecepatan akses konstan dengan biaya ruang tinggi, cocok untuk graf padat. Daftar ketetanggaan menyeimbangkan antara ruang dan waktu, ideal untuk graf jarang dan operasi traversal. Daftar sisi paling sederhana dan bermanfaat bila fokus pada pengolahan seluruh sisi. Memahami kelebihan dan keterbatasan masingmasing memungkinkan programmer memilih struktur yang optimal untuk permasalahan spesifik. </p></section>