Cari Blog Ini

Jumat, 30 April 2010

Graph dan Contoh Implementasi Graph Pada Struktur Data

Graph adalah sekelompok simpul-simpul (nodes/vertices) V, dan sekelompok sisi (edges) E yang menghubungkan sepasang simpul. Bayangkan simpul-simpul tersebut sebagai lokasi-lokasi, maka himpunan dari simpul-simpul tersebut adalah himpunan lokasi-lokasi yang ada. Dengan analogi ini, maka sisi merepresentasikan jalan yang menghubungkan pasangan lokasi-lokasi tersebut.

Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge ata u arc). biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

contoh implementasi graf pada struktur data :

1. Graf tak berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. salah satu contoh graf tak berarah dimana sisi-sisi yang menghubungkan antar simpul dalam graf tersebut tidak memiliki orientasi arah.
2. Graf Berarah (directed graph)
Graf yang setiap sisinya memiliki orientasi arah disebut sebagai graf berarah. Sisi berarah dalam graf ini dapat dinamakan sebagai busur (arc). Lain halnya dengan graf tak-berarah, urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. contoh dari graf berarah yang memiliki sisi-sisi dengan orientasi arah (busur).

Tidak ada komentar:

Posting Komentar