Abstract Data Types: Graphs

What is a graph?

A graph is a non-sequential abstract data type where following rules have to be obeyed:

What are the operations a graph requires?

Like trees, graphs are very varied in usage, so hardly reductible to a common ground outside theory. A standard graph, however, would require from data structures that implement it to provide support for this minimal set of operations:

Operation Arguments Returns Description
createVertex DATA VERTEX Creates vertex storing DATA and adds it to graph
removeVertex VERTEX void Removes vertex from graph.
getSize   ULONG Gets number of vertexes in graph.

And a VERTEX that must implement these operations:

Operation Arguments Returns Description
setData DATA void Sets vertex value (data)
getData   DATA Gets vertex value (data)

What are the data structures that implement graph?

Depending how edges work in a standard graph, four implementations are possible:

What are the methods to traverse a graph?

Depending on when a VERTEX is visited during traversal, following methods are in most common usage: