Instructions. You are provided one skeleton program named Graph2.java. The sourc
ID: 3704744 • Letter: I
Question
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));
}
}
Explanation / Answer
Below is your code: -
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;
}
int minKey(int key[], Boolean mstSet[]) {
// Initialize min value
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < n; v++)
if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}
return min_index;
}
public int prim(int r) {
int parent[] = new int[n];
int key[] = new int[n];
Boolean mstSet[] = new Boolean[n];
for (int i = 0; i < n; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < n - 1; count++) {
// Pick the minimum key vertex from the set of vertices not yet
// included in MST
int u = minKey(key, mstSet);
mstSet[u] = true;
// Update key value and parent index of the adjacent
// vertices of the picked vertex
for (int v = 0; v < n; v++)
// A[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if A[u][v] is smaller than key[v]
if (A[u][v] != 0 && mstSet[v] == false && A[u][v] < key[v]) {
parent[v] = u;
key[v] = A[u][v];
}
}
r = 0;
for (int i = 1; i < n; i++)
r += A[i][parent[i]];
return 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));
}
}
Output
37