Impulse Impulse - 2 months ago 24
C++ Question

Two Dimensional Array Representing a Weight Matrix

I'm a bit stumped in how a 2d array(Matrix) such as this

0.0 1.8 9.1 4.0 3.5

1.8 0.0 8.1 5.2 8.6

9.1 8.1 0.0 2.9 8.1

4.0 5.2 2.9 0.0 2.0

3.5 8.6 8.1 2.0 0.0


is supposed to represent a graph. The values represent the weights but then what represents the nodes and edges. I'm trying to brute force find all possible tree's (Which I'm not asking for help on that, just trying to understand how this is supposed to represent this enter image description here

Answer

If you have a (weighted, undirected) graph with 5 vertices---call them v1, v2, v3, v4, v5---the graph can be represented by your matrix.

     v1   v2   v3   v4   v5
v1   0.0  1.8  9.1  4.0  3.5 
v2   1.8  0.0  8.1  5.2  8.6 
v3   9.1  8.1  0.0  2.9  8.1 
v4   4.0  5.2  2.9  0.0  2.0 
v5   3.5  8.6  8.1  2.0  0.0 

The number in, say, (v2, v4), represents an edge connecting v2 and v4 with a weight of 5.2. The zero entry could represent non-edges, or edges with zero weight. Non-weighted graphs are usually represented with a boolean value in each entry, 1 representing an edge, 0 representing no edge. The graph is (well, can be) undirected if the matrix is symmetric.

NB: the picture in your question cannot be represented by the given matrix: the matrix represents a graph with 5 vertices, and the graph represented by the picture has 8 vertices.

Comments