Scenario

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

Aim

To write a code in Java for implementing the adjacency matrix representation of a weighted undirected graph.

Prerequisites

For this activity, you have to implement methods addEdge() and edgeWeight() of class AdjacencyMatrixWeightedUndirected available at the following URL: 

https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson6/activity/weightedundirected/AdjacencyMatrixWeightedUndirected.java

The methods should add an edge and return the edge weight between two vertices, respectively.

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)). Using that strategy, we also don't need to store the full matrix, thereby saving some space.

In this first section, we learned two different ways of representing a graph in a computer program. We briefly examined the pros and cons of each representation, and we will take a look at their usefulness when implementing graph algorithms in the following sections.