Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm - Hallo sahabat duniaschools, Pada Artikel yang anda baca kali ini dengan judul Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm, kami telah mempersiapkan artikel ini dengan baik untuk anda baca dan ambil informasi didalamnya. mudah-mudahan isi postingan Artikel Struktur Diskrit, yang kami tulis ini dapat anda pahami. baiklah, selamat membaca.

Judul : Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm
link : Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm

Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm

Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm

Spanning Trees

Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex of G. A simple graph is connected if and only if it has a spanning tree. Applied in IP multitasking. 

Exercise

Find a spanning tree for the following graphs.

Minimum Spanning Trees

A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of it edges. 

Two algorithms can be used : 

• Prim’s Algorithm by Robert Prim, 1957 
• Kruskal’s Algorithm by Joseph Kruskal, 1956 

Prim’s Algorithm

1. Chose an edge with the least weight. 
2. Include it in spanning tree, T. 
3. Select an edge of least weight that is incident with a vertex of an edge in T. 
4. If it does not create a cycle (simple circuit) with the edges in T, then include it in T; otherwise discard it. 
5. Repeat STEPS 3 and 4 until T contains n-1 edges.

There may be more than one minimum spanning tree for a given connected weighted simple graph. If there are two edges with similar smallest weight, chose either one.

Example: Prim’s Algorithm

Kruskal’s Algorithm

1. Arrange the edges in G in increasing order. 
2. Chose an edge with the minimum weight. 
3. Include it in spanning tree, T. 
4. Add an edge of least weight to T. 
5. If it does not create a cycle (simple circuit) with the edges in T, then include it in T; otherwise discard it. 
6. Repeat STEPS 4 and 5 until T contains n-1 edges. 

There may be more than one minimum spanning tree for a given connected weighted simple graph. If there are two edges with similar smallest weight, chose either one. 

Example: Kruskal’s Algorithm

Sumber

Slide Strukdis : Spanning Tree

http://informatika.unpar.ac.id/

Demikianlah Artikel Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm

Sekianlah artikel Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm kali ini, mudah-mudahan bisa memberi manfaat untuk anda semua. baiklah, sampai jumpa di postingan artikel lainnya.

Anda sekarang membaca artikel Struktur Diskrit : Pohon Merentang, Kruskal's Algorithm, dan Prim's Algorithm dengan alamat link https://duniaschools.blogspot.com/2019/10/struktur-diskrit-pohon-merentang.html