- 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:

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) |

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

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!