How to represent a graph on a computer?

[Pithikos]

I want to represent a graph with v vertices and e edges. Each vertex represents a city and each edge the distance between two cities.

I am aware of adjacency matrix but I found that it took more than double space so I went with an array. Each item in the list keeps a point1, a point2 and the distance between those two.

So for example to represent these two connections:
Stockholm Athens 34km
Athens Amsterdam 23km

My array would look like this:

          _______0__________________1__________
point1   | Stockholm     |     Athens          |
point2   | Athens        |     Amsterdam       |
distance |   34          |      23             |
         ---------------------------------------

Now I have my doubts if I took the right decision. I surely save space but what about going through the array? Later in the project I will need to find the shortest path. Is the list going to be slower?

 

[Mark44]

An adjacency matrix would be easier to work with than an array like the one you show. The matrix would need to be v X v, but you need entries in only half of the elements. (The distance from city vi to city vj is the same as the distance from city vj to vi.)
This matrix would need to hold .5v² ints. To find the distance from vi to vj, get the value at D[j], where D is the name of the matrix.

Your array, as you show it doesn't save any space, since you will still need v*(v - 1) elements, plus you are storing the names of all the cities (it appears).

 

[Pithikos]

An adjacency matrix would be easier to work with than an array like the one you show. The matrix would need to be v X v, but you need entries in only half of the elements. (The distance from city vi to city vj is the same as the distance from city vj to vi.)
This matrix would need to hold .5v² ints. To find the distance from vi to vj, get the value at D[j], where D is the name of the matrix.

Your array, as you show it doesn't save any space, since you will still need v*(v - 1) elements, plus you are storing the names of all the cities (it appears).

Why v*(v-1)? The list would have the same amount of elements as many edges there are. The graph is bidirectional so Athens->Stockholm is the same as Stockholm->Athens. As about the names I was thinking to make a list with the city names so that each city corresponds to an integer number.

 

[Mark44]

In a graph with v nodes, each node can have an edge to the other v - 1 nodes. That makes v(v - 1) edges in all, counting all of them twice (i.e. the edge or path from, say Stockholm to Athens and the edge from Athens to Stockholm). If you got rid of duplicates, you would still have (1/2)v(v - 1) edges, assuming that each node is connected to each other node.

You really don't save anything with a one-dimensional array of distances as compared to a two-dimensional adjacency array.