GRAPH

 

Graph terdiri dari sekumpulan titik (verteks) yang dihubungkan oleh garis atau sisi (edge).

2 macam Graph:

  • Undirected Graph (tidak mempunyai arah)

mPzx7

 

  • Directed Graph (punya arah)

directed_graph_example1

 

Minimum Spanning Tree

Cara menggambarkan graph tanpa adanya looping dengan biaya terkecil.

Beberapa cara mencari minimum spanning tree:

  • Prim’s algorithm
  • Kruskal’s algorithm

 

I. Prim’s algorithm

prim

 

II. Kruskal’s algorithm

6RCFr

 

Shortest Path

Mencari jalur terpendek dari suatu vertex ke vertex tertentu.

Caranya dengan menggunakan Dijkstra’s algorithm.

 

Dijkstra’s Algorithm

Lihat video Youtube dibawah untuk penggunaan dijkstra algorithm