Abstract Data Types: Graphs

├─ What is a GRAPH
├─ What are the operations a GRAPH requires
├─ What are the data structures that implement GRAPH
└─ What are the methods to traverse a GRAPH

What is a graph?

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

every entry is a node (aka VERTEX) that may have links (aka EDGES) to another node
links can be directed (if A->B it doesn't mean B->A) or undirected (if A->B, then B->A)
links can hold weights (eg: roads between NY->LA, LA->SF, each holding different weights expressed in miles)
there can be multiple paths between two nodes (eg: multiple road alternatives from NY-LA)
not all nodes have to be connected
nodes can connect to themselves

How values (or vertexes) and connections (or edges) are added to a directed un-weighted graph:

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 each VERTEX must at least 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:

Unweighted Graph: a standard graph where all edges have no weights. Depending on whether or not edges are bidirectional:
- Unweighted Directed Graph: a version of Unweighted Graph where edges are unidirectional by default
- Unweighted Undirected Graph: a version of Unweighted Graph where edges are always bidirectional
Weighted Graph: a standard graph where all edges have weights. Depending on whether or not edges are bidirectional:
- Weighted Directed Graph: a version of Weighted Graph where edges are unidirectional by default
- Weighted Undirected Graph: a version of Weighted Graph where edges are always bidirectional

What are the methods to traverse a graph?

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

breadth-first search: visitation is performed by going deeper and deeper in depth compared to source VERTEX.
Algorithm:
function bfs(VERTEX, VISITOR): define QUEUE VISITOR(VERTEX) push VERTEX to QUEUE while QUEUE is not empty pop HEAD_VERTEX from QUEUE for each EDGE @ HEAD_VERTEX if IS_NOT_VISITED(VERTEX@EDGE) VISITOR(VERTEX@EDGE) push VERTEX@EDGE to QUEUE
depth-first search: visitation is performed by exploring source VERTEX as far as possible then backtracking.
Algorithm:
function dfs(VERTEX, VISITOR): define STACK VISITOR(VERTEX) push VERTEX to STACK while QUEUE is not empty pop TAIL_VERTEX from STACK for each EDGE @ TAIL_VERTEX if IS_NOT_VISITED(VERTEX@EDGE) VISITOR(VERTEX@EDGE) push VERTEX@EDGE to STACK

Where:

VERTEX: vertex to start traversal from
VISITOR: function to apply on each visited vertex during traversal (eg: outputting data inside)
STACK/QUEUE: data structure to use in storing traversed vertexes
HEAD_VERTEX/TAIL_VERTEX: vertex to remove from data structure above and use in edge traversal
VERTEX@EDGE: vertex to visit during edge traversal and add to data structure above
IS_NOT_VISITED: function to check if vertex visited during edge traversal wasn't visited already
This prevents cycles inside graph being infinitely traversed!