Data Structures: Weighted Graphs

What is a Weighted Graph?

A Weighted Graph is an abstract data structure that functions as a Graph implementation where all edges are assumed to have weights associated.

What are the operations it requires?

Apart of implementing operations required by Graph abstract data type, following operations are added:

Operation Arguments Returns Description
createEdge VERTEX, VERTEX, WEIGHT void Creates a weighted edge between vertexes along.
isPath VERTEX, VERTEX boolean Checks if there is a path of edges between vertexes.
removeEdge VERTEX, VERTEX void Removes edge between vertexes.

And completes Graph VERTEX with following operations:

Operation Arguments Returns Description
getEdges   EDGES Gets vertexes current vertex points to in edges.
isEdge VERTEX boolean Checks if current vertex has an edge with that of input
addEdge VERTEX, WEIGHT void Creates a weighted edge between current vertex and that of input
removeEdge VERTEX void Removes edge between current vertex and that of input
setEdgeWeight VERTEX, WEIGHT void Sets weight of edge between current vertex and that of input
getEdgeWeight VERTEX WEIGHT Gets weight of edge between current vertex and that of input

Regarding implementation chosen to store a VERTEX's edges, which reflects into "EDGES" above, following data structures can be used:

What are the data structures that implement it?

As an abstract data structure, provides only a partial implementation that takes no assumption on whether or not weighted edges are bidirectional or not. It thus needs to be extended by one of below:


Share