13.Graph

Graph ABDI PANDU KUSUMA, S.KOM., M.T

Definisi Graph Graph→ ?? ➢Kumpulan 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 (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge). G = (V, E) Dimana G = Graph V = Simpul atau Vertex, atau Node, atau Titik E = Busur atau Edge, atau arc

Bentuk-bentuk Graph terbagi menjadi 3 bentuk: Graph Graph tak berarah (undirected graph atau non-directed graph) : Urutan simpul dalam sebuah busur tidak dipentingkan. Misal busur e1 dapat disebut busur AB atau BA Graph berarah (directed graph) : Urutan simpul mempunyai arti. Misal busur AB adalah e1 sedangkan busur BA adalah e8. Graph Berbobot (Weighted Graph) Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot. Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

Bagian-bagian Vertex Graph → himpunan node / titik pada sebuah graph. Edge → himpunan garis yang menghubungkan tiap node / vertex. Adjacent → dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi. Adalah Sisi e3 = v2v3 insident dengan titik v2 dan titik v3, tetapi sisi e3 = v2v3 tidak insident dengan titik v1 dan titik v4. Titik v1 adjacent dengan titik v2 dan titik v3, tetapi titik v1 tidak adjacent dengan titik v4.

Bagian-bagian Weight Graph → Sebuah graf G = (V, E) disebut sebuah graf berbobot (weight graph), apabila terdapat sebuah fungsi bobot bernilai real W pada himpunan E. Path → Walk dengan setiap vertex berbeda. Cycle → Siklus ( Cycle ) atau Sirkuit ( Circuit ) Lintasan yang berawal dan berakhir pada simpul yang sama.

Adjacency Matrik Graf Tak Berarah Representasi Matriks dalam bentuk Graph Matrik yang digambarkan pada gambar 1b merupakan representasi dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 1a. Beberapa hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik diantaranya: ❖Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya. ❖Matrik yang terbentuk adalah matrik simetris dengan sumbu simetris adalah diagonal dari titik kiri atas ke titik kanan bawah. ❖Data yang tedapat baik dalam baris maupun kolom, dapat menyatakan degree sebuah simpul. Contoh : baik pada baris D maupun kolom D jumlah angka 1 nya adalah 3 buah, dimana jumlah ini menyatakan degree simpul D.

Adjacency Matrik Graf Berarah Representasi Matrik yang digambarkan pada gambar 2b merupakan representasi dalam Matriks dalam bentuk Adjacency Matrik dari graf yang digambarkan pada gambar 2a. Beberapa bentuk Graph hal yang dapat dilihat atau dapat diterangkan pada Adjacency Matrik tersebut sebagai berikut : ❖ Matrik yang terbentuk adalah matrik bujur sangkar n x n, dimana n = jumlah simpul yang ada dalam graf tersebut. Matrik ini menyatakan hubungan antara simpul satu dengan simpul lainnya. ❖ Matrik yang terbentuk mungkin simetris mungkin juga tidak simetris, menjadi Simetris bila hubungan antara dua buah simpul (v1 dan v2) terdapat busur dari v1 ke v2 dan juga sebaliknya. ❖ Hal penting yang dinyatakan oleh matrik ini yakni busur yang ’keluar’ dari suatu simpul. Dengan demikian, data yang terdapat dalam suatu baris, dapat menyatakan outdegree simpul yang bersangkutan. Contoh : Jumlah elemen yang nilainya = 1 pada baris B ada 3 elemen,ini menyatakan jumlah outdegree simpul B adalah 3 buah. ❖ Data yang terdapat dalam suatu kolom, dapat menyatakan indegree simpul bersangkutan. Contoh : Jumlah elemen yang nilainya 1 pada kolom B ada 2 elemen, ini menyatakan indegree simpul B adalah 2 buah.

Adjacency Matrik Graf Berbobot Tak Berarah Representasi Matriks dalam bentuk Graph Nilai yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma, maka dari total bobot seluruh busur yang ada atau yang mungkin ada. Contoh: pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur, maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai 999 dalam kasus ini cukup mewakili nilai tidak terhingga.

Adjacency Matrik Graf Berbobot Tak Berarah Representasi Matriks dalam bentuk Graph Nilai yang ada dalam tiap elemen matrik, menyatakan bobot busur yang menghubungkan dua buah simpul yang bersangkutan. Untuk dua buah simpul yang tidak berhubungan langsung oleh sebuah busur, maka dianggap dihubungkan oleh sebuah busur yang nilai bobotnya tidak terhingga. Dalam pemograman, karena keperluan algoritma, maka dari total bobot seluruh busur yang ada atau yang mungkin ada. Contoh: pada gambar 3a simpul A dan C tidak berhubungan langsung melalui sebuah busur, maka untuk elemen matrik yang bersangkutan diisi dengan nilai 999 karena nilai 999 dalam kasus ini cukup mewakili nilai tidak terhingga.

Adjecency graph dalam list Representasi Graph dalam bentuk linked list Pada gambar diatas terlihat ada 5 buah simpul A,B,C,D,dan E yang dibariskan dari atas kebawah seperti pada gambar 4a. Kemudian dari masing-masing simpul \"keluar\" pointer kearah kanan yang menunjuk simpul-simpul lain. Salah satu contoh, yang dapat dilihat pada gambar 4b dimana A menunjuk simpul B dan simpul D.

Adjecency graph dalam list Representasi Graph dalam bentuk linked list Dalam Adjacency List, kita perlu membedakan antara simpul- vertex dan simpul-edge. Simpul-vertex untuk menyatakan simpul atau vertex, dan simpul-edge untuk menyatakan hubungan antar simpul yang biasa disebut busur. Struktur keduanya bisa sama, bisa juga tidak sama,tergantung kebutuhan.Untuk memudahkan pembuatan program, struktur kedua macam simpul dibuat sama seperti yang digambarkan pada gambar diatas.

??? ADA PERTANYAAN ???

Coding: Contoh implementasi graph berbobot tak berarah

Final Project ➢ Buat sebuah aplikasi program menggunakan C++ dengan tema bebas. (UAS) ➢ Final project dikerjakan sesuai dengan kelompok yang telah dibentuk sebelumnya. ➢ Setiap kelompok tidak diperbiolehkan menggunakan tema yang sama. ➢ Pilihan tema untuk menbuat program menggunakan Linked List, Stack/ Queue, dan Tree. Proposal Final Project. • Buat proposal Final Project yang terdiri dari: ✓Cover ✓Kata Pengantar ✓Daftar Isi ✓Bab 1 Pendahuluan (Latar belakang & ruang lingkup) ✓Bab 2 Dasar Teori ✓Bab 3 Perancangan Program (Desain layout & penjadwalan) ✓Daftar Pustaka ✓Biodata Kelompok. • Proposal final project dikirimkan via Edlink terakhir pada tanggal 19 Januari 2023 bentuk file DOC & PDF beserta file PPT (diupload dalam gdrive) pukul 6.00 WIB. • Proposal final project dipresentasikan per kelompok pada tanggal 20 Januari 2023 mulai jam 15.30.

Final Project Final Project. (UAS) • Buat laporan final project dengan menambahkan: ✓ Bab 4 Pembahasan Program ✓ Bab 5 Kesimpulan & Saran • Laporan final project dikirimkan via Edlink terakhir pada tanggal 1 Februari 2023 dalam bentuk file DOC & PDF beserta file PPT dan file aplikasi dan read-me nya (File RAR) pukul 18.00 WIB. • Final project dipresentasikan secara offline pada tanggal 2 February 2023 sesuai jadwal perkuliahan ini dengan menunjukkan kartu UAS sebelum presentasi per kelompok dimulai.