CSE 214 : Data Structures
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE 214 : Data Structures
CSE 214 - Homework 4
This last assignment is much shorter than the previous homework assignments in this semester. Here, you have to work on a single algorithm for a very specific data structure. The data structure is a graph. More specifically, it is an undirected graph with edge weights ranging from 0 to 1 (inclusive). An edge weight of zero simply means that the edge does not exist.
In the lectures, we discussed the concept of a minimum weighted tree covering all vertices of a graph. We also discussed that a “greedy” approach may or may not work for all kinds of graph-related problems, because minimizing something locally in the neighborhood of a vertex may not ultimately lead to an overall minimization in the entire graph. In this homework, however, one graph-problem that can be solved using a “greedy” approach.
There is a skeleton code provided to you as a starting point:
public class Graph {
private final double[][] adjacencyMatrix;
private Graph(double[][] adjacencyMatrix) {
this.adjacencyMatrix = adjacencyMatrix;
}
public static Graph fromMatrixString(String s) { /* TODO: */ }
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < adjacencyMatrix.length; i++) {
for (int j = 0; j < adjacencyMatrix[i].length; j++) {
builder.append(String.format("%1.2f ", adjacencyMatrix[i][j]));
}
builder.append("\n");
}
return builder.toString();
}
public Graph getTree() { /* TODO: */ }
private static final String s =
"0.0 0.0 0.5 0.7 0.0 0.0\n" +
"0.0 0.0 0.7 0.0 1.0 0.0\n" +
"0.5 0.7 0.0 1.0 0.0 0.9\n" +
"0.7 0.0 1.0 0.0 0.0 0.0\n" +
"0.0 1.0 0.0 0.0 0.0 0.7\n" +
"0.0 0.0 0.9 0.0 0.7 0.0";
public static void main(String... args) {
// you can assume that incorrect strings will not be provided as input,
// i.e., any input string will be a valid adjacency matrix
// representation of an undirected weighted graph
Graph g = Graph.fromMatrixString(s);
System.out.println(g);
}
}
As you can see, the class Graph is meant to store a graph as an adjacency matrix, where each entry is a double value. The double value of x at the [i][j] location of the matrix denotes that there is an edge of weight x connecting vertex i and vertex j. The vertices are simply the integer indices (i.e., the index itself serves as the vertex; there is no additional value at a vertex). Moreover, you can assume that the edge weights are all unique. That is, no two edges of a graph have the exact same weight.
Your first task is to complete the given code such that the static method fromMatrixString(String) can be used to create a new Graph instance from a given string input. The main method provided above already shows you how to test if your implementation is correct.
Your second task is to complete the getTree() method. This method must return a tree that consists of a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles. It must also have the minimum possible total edge weight of all such possible trees.
The pseudocode for the solution is already given to you. All you have to do is convert this into working Java code for the adjacency matrix representation.
Pseudocode
1. Choose any vertex. Additional note: please always start with vertex 0.
2. Put this vertex into a tree t. At this point, the tree t consists only of one node (the root node) and no children.
3. Find all the edges that connect t to vertices not in t. Among these edges, find the one with the least weight and add it to the tree (including, of course, the vertex at the other end of this edge).
a. If the inclusion of this edge forms a cycle, then reject this edge and try to add the second least weight edge (and so on, until you are able to add an edge to t without forming a cycle).
4. Repeat step 3 as long as some vertex of the graph is not yet in t.
You are free to add methods in the Graph class as long as your additional methods are private.
NOTE: We have already provided a way to test a graph, and one example test case. But you should always test your code with more examples of your own. This should include testing for corner cases. For example, can your code handle the empty string? Can you code handle the empty graph, or a graph with one vertex but no edges?
Rubric
The rubric for this assignment is very straightforward. As you have probably noticed already, there are just two methods to be tested. So, there will be a fixed number of test cases, and for each case, the grading process will check the fromMatrixString(String) method (worth 20%) and the getTree() method (worth 80%). For example, if there are 10 test cases, each correct instantiation from an input string will be worth 2 points, and each correct tree will be worth 8 points.
2021-12-06