Scenario

Creating an adjacency matrix for a weighted undirected graph to be used for social networking website.

Aim

Write code for implementing the adjacency matrix representation of a weighted undirected graph.

Prerequisites

Implement methods addEdge() and edgeWeight() of class AdjacencyMatrixWeightedUndirected:

public class AdjacencyMatrixWeightedUndirected { int[][] adj; public AdjacencyMatrixWeightedUndirected(int nodes) { this.adj = new int[nodes][nodes]; } public void addEdge(int u, int v, int weight) { } public int edgeWeight(int u, int v) { return 0; } }

The methods should add an edge and return the edge weight between two vertices, respectively. You can use the addEdge method from Snippet 6.1 as a baseline for your new implementation:

public void addEdge(int u, int v) { this.adj[u].add(v); }

^{Snippet 6.1: addEdge implementation from an adjacency list representation of a graph}

Steps for Completion

1. Start storing the weights of edges in each cell of the matrix. Since we're dealing with undirected graphs, both (u, v) and (v, u) refer to the same edge, so we need to update both accordingly.
2. It is also possible to not repeat the weight assignment. We just have to be careful and always choose one of (u, v) or (v, u) when referring to that edge. One possible strategy is to always use (min(u, v), max(u, v)).
3. Using that strategy, we also don't need to store the full matrix, thereby saving some space.

Task

Finish the implementation of addEdge() and edgeWeight().

Below is the code given:

public class AdjacencyMatrixWeightedUndirected { int[][] adj;

public AdjacencyMatrixWeightedUndirected(int nodes) { this.adj = new int[nodes][nodes]; }

public void addEdge(int u, int v, int weight) { // write your code here }

public int edgeWeight(int u, int v) { // write your code here return 0; } }