In the previous lab, we learned graph and how to traverse it. In this lab, we will learn a problem of graph is Minimum Spanning Tree. To find the Minimum Spanning Tree, we have two basic algorithms:

1. Prims algorithm
2. Kruskals algorithm

1. Minimum Spanning Tree

Tree T is a connected graph that has V vertices and V1 edges, only one unique path between any two pair of vertices in T.

Given connected graph G with positive edge weights, find a min weight set of edges that connects all of the vertices.

Figure 1: Graph

A spanning tree of a graph G is a subgraph T that is connected and acyclic. 1

Figure 2: Minimum Spanning Tree

2. Prims Algorithm

The way Prims algorithm works is as follows :

• Initialize the minimum spanning tree with a initial vertex.
• Find all the edges that connect the tree to new vertices, find the minimum, and add it to the tree.
• Keep repeating step 2 until we get a minimum spanning tree (until all vertices are reached).

You can follow this instruction to step by step implement Prim algorithm: 1. Create a boolean array (visited[]) and two integer arrays (parent[], cost[])

2. Choose the initial vertex.
3. Find the vertex which has the minimum cost from the latest vertex and hasnt been visited (we can call this vertex is min_id).
4. Set visited[min_id] = true
5. Update parent[] from min_id to the vertices which havent visited. Update cost[] if the cost from new vertex is smaller than from the previous.
6. Repeat step 3 until all vertices are visited.

3. Kruskals Algorithm

To simplify Kruskals implementation, we will you Edge List to store the graph. The steps for implementing Kruskals algorithm are as follows:

1. Sort all the edges from low weight to high.
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

To check the edge created a cycle or not, you can Union-Find Disjoint Sets.

This is Union-Find code, you can init an instance and use isSameSet(int i, int j) method to check two vertices i, j create a cycle or not.

class UnionFind{private Vector<Integer> p, rank, setSize;public UnionFind(int N) { p = new Vector<Integer>(N); rank = new Vector<Integer>(N);setSize = new Vector<Integer>(N); for (int i = 0; i < N; i++) {p.add(i); rank.add(0); setSize.add(1);}}public int findSet(int i) { if (p.get(i) == i) return i;else { int ret = findSet(p.get(i)); p.set(i, ret);return ret;}}public void unionSet(int i, int j) { if (!isSameSet(i, j)) { int x = findSet(i), y = findSet(j); if (rank.get(x) > rank.get(y)) {p.set(y, x);setSize.set(x, setSize.get(x) + setSize.get(y));} else{p.set(x, y); setSize.set(y, setSize.get(y) + setSize.get(x)); if (rank.get(x) == rank.get(y))rank.set(y, rank.get(y) + 1);}}}public boolean isSameSet(int i, int j){ return findSet(i) == findSet(j);}}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

4. Exercise

Given a graph:

Read this graph from a text file with Adjacency Matrix.

• Write the Kruskal function for the given graph. Print MST result on the screen.
• Write the Prim function for the given graph starting from vertex 0. Print MST result on the screen.

5. Reference

1. https://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf
2. https://www.journaldev.com/43746/prims-algorithm-minimum-spanning-tree-java

THE END