Instructions. You are provided one skeleton program named Graph2.java. The source ?les are available on Canvas in a folder named HW8. Please modify the skeleton code to solve the following tasks.

Task 1 (100 pts). Implement the prim(int r) function as discussed in Lecture 18.

Note: You should return an integer that indicates the total weight of the minimum spanning tree.

Hint 1: We use an adjacent matrix to represent the graph. If A[i][j] = 0, it means there is no edge between the i-th and j-th node. If A[i][j] > 0, then it means the weight of the edge between the i-th and j-th node.

Hint 2: To learn how to use Priority Queue in Java, google Java PriorityQueue API. Also ?nd some tutorials on Java PriorityQueue to understand it better.

Hint 3: In order to associate each node with a weight and place it into the queue, you may need to create another class. Check ListNode.java and LinkedList.java in HW3 to get an example of auxiliary class.

Skeleton code is:

package graph;

public class Graph2 { public int n; //number of vertice public int[][] A; //the adjacency matrix public Graph2 () { n = 0; A = null; } public Graph2 (int _n, int[][] _A) { this.n = _n; this.A = _A; } public int prim (int r) { }

/** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int n = 9; int A[][] = { {0, 4, 0, 0, 0, 0, 0, 8, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0, 0, 7, 0, 9, 14, 0, 0, 0}, {0, 0, 0, 9, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 2, 0, 1, 6}, {8, 11, 0, 0, 0, 0, 1, 0, 7}, {0, 0, 2, 0, 0, 0, 6, 7, 0} }; Graph2 g = new Graph2(n, A); System.out.println(g.prim(0)); }

}