Sabtu, 30 Juni 2007

Graph

Secara geometri graph digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Sebagai contoh, peta jaringan jalan kereta api yang menghubungkan sejumlah kota di pulau Jawa. Sesungguhnya peta tersebut adalah sebuah graph, yang dalam ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan diberikannya peta tersebut, maka dapat diketahui apakah ada lintasan jalan antara dua buah kota. Selain itu, bila panjang jalan kereta api antara dua buah kota bertetangga diketahui, maka juga dapat ditentukan rute perjalanan tersingkat dari kota A ke kota B.

Dalam pemrograman komputer, graph dapat direpresentasikan dengan menggunakan beberapa macam representasi graph, antara lain adjacency matrix, incidency matrix dan adjacency list. Namun, saya merekomendasikan untuk menggunakan adjacency list karena lebih efisien dan efektif dalam pengkodean dan lebih menghemat memori.

Tidak ada komentar: