GRAPH

Graph (grafik) berupa kumpulan dari vertex (titik) yang dihubungkan oleh garis yang dinamai edge.

Beberapa jenis dalam graph adalah:

  • Graph tak berarah

Picture2

  • Graph berarah

11

  • Graph berbobot

34eqg6b

 

ADJACENCY LIST MATRIX

Adjacency list matrix adalah bentuk representasi graph dalam bentuk matrix yang menyatakan hubungan antar simpul (vertex).

2wp3zpy

Gambar 2b adalah bentuk representasi matrix dari 2a.

MINIMUM SPANNING TREE

Minimum Spanning Tree (MST) adalah tree yang tidak mempunyai loop.

Metode dalam MST adalah:

A. Algoritma Prim

  • Pilih salah satu vertex sebagai vertex awal
  • Pilih edge dengan nilai terkecil yang terhubung dengan vertex tersebut
  • Lakukan tahap tersebut sampai semua vertex telah terhubung dan tidak ada loop

B. Algoritma Kruskal

  • Urutkan semua edge dengan bobot paling kecil
  • Hubungkan vertex yang terhubung oleh edge paling kecil, jika terjadi looping maka skip edge tersebut
  • Lakukan tahap tersebut sampai semua vertex terhubung

SHORTEST PATH

Shortest Path adalah pemilihan / metode untuk memilih jalan terpendek / dengan bobot terkecil dalam suatu graph berbobot.

Metode yang digunakan dalam shortest path adalah Algoritma Dijkstra.