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.

 

[LudusRex]

Thank you for your question. Representing a graph on a computer can be done in various ways, including using an adjacency matrix or an array. It seems like you have chosen to use an array to represent your graph with v vertices and e edges, where each item in the array contains the two vertices connected by an edge and the distance between them.

Using an array to represent a graph can indeed save space compared to an adjacency matrix, which requires v^2 space. However, as you mentioned, there may be concerns about the efficiency of accessing and manipulating the data in the array.

In terms of finding the shortest path, the efficiency will depend on the algorithm you use. If you are using a search algorithm that requires you to check all edges connected to a given vertex, then using an array may not be the most efficient option. In this case, an adjacency list may be a better choice, as it allows for faster access to all edges connected to a vertex.

However, if you are using a search algorithm that only requires access to the two vertices connected by an edge, then using an array may be just as efficient as an adjacency list.

Ultimately, the best way to represent a graph on a computer will depend on the specific requirements and algorithms being used in your project. It may be worth considering the pros and cons of each representation and potentially even testing the efficiency of different options in your project to determine the best approach.