Minimum Spanning Trees algorithm
1
Algoritma Minimum Spanning Trees
algoritma Kruskal and algoritma Prim. Kedua algoritma ini berbeda dalam metodologinya, tetapi keduanya mempunyai tujuan menemukan minimum spanning •algorithm Kruskal menggunakan edge, dan •algorithm Prim menggunakan vertex yang terhubung 2
Perbedaan antara algoritma prim dan kruskal
Perbedaan prinsip antara algoritma prim dan kruskal adalah, jika pada algoritma prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T. asalkan penambahan sisi tersebut tidak membentuk cycle.
3
Kruskal's Algorithm:
Pada algoritma kruskal, sisi (edge) dari Graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle. 1. T masih kosong 2. pilih sisi (i,j) dengan bobot minimum 3. pilih sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T 4. Ulangi langkah 3 sebanyak (n-2) kali. 5. Total langkah (n-1) kali 4
Kruskal's Algorithm:
a
10
13
15 d
20
b
e
5 21
11 16
Langkah
c
Sisi
bobot
1
e-c
5
2
a-b
10
3
d-e
11
4
c-f
12
5
b-e
13
0 12 f
5
Kruskal's Algorithm:
a
10
b 13
15 d
20
e
c 5 21
11
10
a 12
13
15
f
20
b
e
5
16
f
a
b
13
15 d
20
e
16
13
e
5
12
21
11
d
c
f
16
c 5 21
11
20
b
15
16 10
10
a 12
21
11
d
c
a 12 f
10
13
15 d
20
b
e
c 5 21
11 16
12 6f
Contoh algoritma Kruskal
7
Contoh algoritma Kruskal
8
Contoh algoritma Kruskal
Langkah
Sisi
bobot
1
N1,N2
1
2
N7,N8
1
3
N2,N3
2
4
N1,N6
3
5
N3,N4
4
6
N2,N7
5
7
N4,N5
7
0
9
Contoh algoritma Kruskal Langkah 2
Langkah 1
Langkah 3 10
Contoh algoritma Kruskal Langkah 6
Langkah 4
Langkah
Sisi
bobot
1
1,4
1
2
6,7
1
3
3,4
2
4
1,2
2
5
4,7
4
6
5,7
6
0
Langkah 5
11
12
The execution of Kruskal's algorithm (Moderate part)
•The edges are considered by the algorithm in sorted order by weight. •The edge under consideration at each step is shown with a red weight number. 8 7 c d b 9 4 2
11
a
i
7 8
6
h
14
4
10 g
1
e
f
2
8
4
i
7 8
8 4
c
b i
7 8
h
d
2
11
a
7
6 1
14
4
9 e
10 g
2
f
c
b
11
a
h
2
d
14
4
6 1
7
9 e
10 g
2
f
8 4
7 8 8
4
c
b i
7 8
d
2
11
a
7
6
h
14
4
e
10 g
1
9
f
2
c
b
11
a
h
i
1
7
d
2
14
4
6 g
2
f
9 e
10
8 4
i
7 8 8 4
c
b i
7 8
h
d
2
11
a
7
6 1
14
4
9 e
10 g
2
f
c
b
11
a
h
d
2
14
4
6 1
7
9 e
10 g
2
f
8 c
b
4
i
7 8
h
4
8
c
b
11
a
7 h
i
1
7
d
2
14
4
6 g
2
f
9 e
10
14
4
6
9 e
10 g
1 8
d
2
11
a
7
f
2
8
4
c
b i
7 8 8 4
c
b
11
a
i
7 8
d
2 6
h
14
4
1
9 e
10 g
f
2
h
14
4
6
9 e
10 g
1
7
d
2
11
a
7
f
2
The Mathematics of Networks
What is the minimum spanning tree (MST) of the network shown in (b)? 19
Algorithma Prim
Pada algoritma prim, dimulai pada vertex yang mempunyai sisi (edge) dengan bobot terkecil. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang bersisian dengan sebuah simpul di T, sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle. (NOTE: dua atau lebih edge kemungkinan mempunyai bobot yang sama, sehingga terdapat pilihan vertice, dalam hal ini dapat diambil salah satunya.) 20
Algorithma Prim 1. Ambil sisi (edge) dari graph yg berbobot minimum, masukkan ke dalam T 2. Pilih sisi (edge) (i,j) yg berbobot minimum dan bersisisan dengan simpul di T, tetapi (i,j) tidak membentuk cycle di T. tambahkan (i,j) ke dalam T 3. Ulangi prosedur no 2 sebanyak (n-2) kali
21
Algorithma Prim
PROCEDURE Prim (G: weighted connected undirected graph with n vertices) BEGIN T := a minimum-weight edge FOR i := 1 to n-2 DO BEGIN e := a minimum-weight edge one of whose vertices is in T, and one is not in T T := T with e added END RETURN T END 22
Algorithma Prim
a
10
d
20
b 13
15
Langkah
e
c 5 21
11 16
Sisi
bobot
1
e-c
5
2
d-e
11
3
c-f
12
4
b-e
13
5
a-b
10
0 12 f
23
Algorithm Prim
a
10
b 13
15 d
20
e
c 5 21
11
10
a 12
13
15
f
20
b
e
5
16
f
a
b
13
15 d
20
e
16
13
e
5
12
21
11
d
c
f
16
c 5 21
11
20
b
15
16 10
10
a 12
21
11
d
c
a 12 f
10
13
15 d
20
b
e
c 5 21
11 16
12 24f
Algorithm Prim LANGKAH
8
B 4
C
7
D
A
4
I
8 H
14
E
6
7 1
BOBOT
1
(H,G)
1
2
(G,F)
2
3
(F,C)
4
4
(C,I)
2
5
(C,D)
7
6
(C,B)
8
7
(B,A)
4
8
(D,E)
9
9
2
11
SISI
G
2
10 F
25
Algorithm Prim Langkah 1
Langkah 3 C
H
1
G 4
H
1
G
2
F
2
F
Langkah 3
Langkah 2
C 2
H
1
G
2
F
4
I
H
1
G
26
Algorithm Prim Langkah 6
Langkah 4 7
C
D
B
2
8
4 A
1
H
2
G
F
Langkah 5
1
2
G
F
Langkah 7
8
C
7
D
B
2
G
2
C
7
D 9
2
4
A 1
8
4
I
H
D
4
I
H
B
7
2
4
I
C
4
I
E
F
H
1
G
2
F
27
Algorithm Prim
28
Prim's algorithm(basic part) MST_PRIM(G,w,r) 1. A={} 2. S:={r} (r is an arbitrary node in V) 3. Q=V-{r}; 4. while Q is not empty do { 5 take an edge (u, v) such that (1) u S and v Q (v S ) and (u, v) is the shortest edge satisfying (1) 6 add (u, v) to A, add v to S and delete v from Q }
Grow the minimum spanning tree from the root vertex r. Q is a priority queue, holding all vertices that are not in the tree now. key[v] is the minimum weight of any edge connecting v to a vertex in the tree. parent[v] names the parent of v in the tree. When the algorithm terminates, Q is empty; the minimum spanning tree A for G is thus A={(v,parent[v]):v∈V-{r}}. Running time: O(|E|+|V|lg |V|). (Analysis is not required)(Fibonacci heap: decreas-key in O(1) time)
The execution of Prim's algorithm(moderate part) 8
the root vertex
c
b
4
i
7 8
4
8
f
1
2
8
7 c
d
2 i
7
14
4
6
h
9 e
10 g
1
e
10 g
b
9
14
4
6
h
11
a
d
2
11
a
7
f
2
8 4
c
b i
7
8
4
8
f
1
2
8
7 c
d
2 i
7
14
4
6
h
9 e
10 g
1
e
10 g
b
9
14
4
6
h
11
a
d
2
11
a
7
f
2
8 4
c
b i
7 8
4
8
f
1
2
8
7 c
d
2 i
7
14
4
6
h
9 e
10 g
1
e
10 g
b
9
14
4
6
h
11
a
d
2
11
a
7
f
2
8 4
c
b i
7
8
4
8
f
1
2
8
7 c
d
2 i
7
14
4
6
h
9 e
10 g
1
e
10 g
b
9
14
4
6
h
11
a
d
2
11
a
7
f
2
8 4
c
b i
7 8
d
2
11
a
7
6
h
14
4
e
10 g
1
9
f
2
Bottleneck spanning tree: A spanning tree of G whose largest edge weight is minimum over all spanning trees of G. The value of the bottleneck spanning tree is the weight of the maximum-weight edge in T. Theorem:
A minimum spanning tree is also a bottleneck spanning tree. (Challenge problem)
soal Cari minimum spanning tree dengan menggunakan algoritma prim dan kruskal ! 8
2 4
2
11
1
5
3 6
5 9 4
7
1
6
36
Barůvka‘s Algorithm
37
Barůvka‘s Algorithm 1. For all vertices search the edge with the smallest weight of this vertex and mark these edges 2. Search connected vertices (clusters) and replace them by a “new“ vertex Ci (cluster)
3. Remove the cycles and, if two vertices are connected by more than one edge, delete all edges except the “cheapest“
Baruvka's Algorithm
5
A 4
6 2
C
B 2
1
3 E
3
D
2 4
Baruvka's Algorithm
F
5
A 4
6 2
C
B 2
1
3 E
3
D
2 4
Baruvka's Algorithm
F
5
A 4
6 2
C
B
E
3
D
1
3
Ci
2
2 4
Baruvka's Algorithm
F
5
A 4
6 2
C
B 2
1
3 E
3
D
2 4
Baruvka's Algorithm
F
A
B 2
2
C
D
1
3 E
2 F
Baruvka's Algorithm
minimum- spanning tree
A
B 2
2
C
D
1
3 E
2 F
Baruvka's Algorithm
soal Tentukan minimum spanning tree dengan menggunakan algoritma kruskal, baruvka dan prim 13
6
2
11
18 20
3
12 17
1
5
12 22
4
16
24
11
7 15
15 45
