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!)
Next: Labelled nodes >>
More Development Cycles Articles
More By Mohamed Saad
