Graph

Pada sesi kemarin, kami membahas mengenai Graph. Graph yang ada di mata kuliah ini sama seperti matematika diskrit yang ada di semester 1.

Graph terdiri dari vertex dan edges. Vertex digambarkan seperti node atau lingkaran, sedangkan edges digambarkan seperti garis penghubung antara vertex yang satu dengan yang lain.

Minimum Spanning Tree

MST ini bertujuan mencari cost termurah/jarak terpendek. Ada 2 cara ,yaitu Prim dan Kruskal. Prim pada dasarnya memilih 1 titik start lalu mencari titik selanjutnya dengan jarak terpendek. Sedangkan kruskal memilih seluruh jarak terpendek tetapi menghindari adanya looping.

MST ini mudah jika kita menggunakan notepad atau semacamnya.

PRIM:

AB 2

AC 1

AF 4

=> AC 1

----------------

AB 2

AF 4

CB 5

CD 1

CE 2

CF 3

=> CD 1

----------------

AB 2

AF 4

CB 5

CE 2

CF 3

DB 3

DE 2

=> AB 2

----------------

AF 4

CB 5

CE 2

CF 3

DB 3

DE 2

BE 4

=> CE 2

----------------

AF 4

CB 5

CF 3

DB 3

DE 2

BE 4

EF 1

=> EF 1

----------------

AF 4

CB 5

CF 3

DB 3

DE 2

BE 4

=> DE 2 (X)

----------------

AF 4

CB 5

CF 3

DB 3

BE 4

=> CF 3 (X)

----------------

AF 4

CB 5

DB 3

BE 4

=> DB 3 (X)

----------------

AF 4

CB 5

BE 4

.... DST

 

VISITED : A C D B E F

EDGE     : AC CD AB CE EF

 

KRUSKAL:

AC 1

CD 1

EF 1

AB 2

CE 2

DE 2

BD 3

CF 3

AF 4

BE 4

BC 5

 

EDGE     : AC CD EF AB CE

VISITED : A C D F B E

Kurang lebih contoh prim dan kruskal seperti itu. Jika ada pertanyaan bias ditanyakan ya J . Terima kasih