Data Structures: Unweighted Graphs

What is an Unweighted Graph?

An Unweighted Graph is an abstract data structure that functions as a Graph implementation where all edges are assumed to have no 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 void Creates an edge between vertexes.
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 void Creates an edge between current vertex and that of input
removeEdge VERTEX void Removes 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 unweighted edges are bidirectional or not. It thus needs to be extended by one of below:


Share