Learning About the Graph Construct using Games, Part 1

Certain everyday problems are easier to solve using the graph construct than any other way, such as the classic "shortest distance between cities" problem. Others are ones you might not expect. In this article, we will play some games to help us understand how we can use the graph construct.

Learning About the Graph Construct using Games, Part 1 - Weighted Edges (Page 5 of 7 )

This is easier than the previous case. In our previous examples, we were only interested in the existence of an edge. In some applications, edges also have weights on them. For example, in the cities and highways example, we could put the length of a highway as a weight for the edge between two cities. This will allow us to find the shortest path between two cities precisely.

How could we add weighted edges to the graphs we just created? This one is easy. For an adjacency matrix, we just write the weight of the edge in the corresponding entry in the matrix rather than just “1” and “0”. Notice that in some applications, “0” is a valid weight. In this case, it can’t be used as a “no-edge” value. We will have to look for another value in this case. For example, this graph:

Fig 4.Graphs with weighted edges…

Would be represented by this array:

Fig 4b.… can still be represented using adjacency matrix

We have used an symbol in place of non-existent edges. In reality, we can use any invalid value to denote that no edge exists here.

In the case of an adjacency list, we can add a new field in every node of every linked list, which holds the weight of that edge.

For example, the same graph above would be represented like this:

Fig 4c.… Adjacency list representation of weighted graphs

The first node in the first linked list, means that node a is connected to node f with a weight of 12. (Notice that node counting starts at 0 for obvious reasons!)