Impulse - 1 year ago 88

C++ Question

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

Answer Source

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.