 # Abstract Data Types: Graphs

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

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

• 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 VERTEX@EDGE is not visited 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 VERTEX@EDGE is not visited VISITOR(VERTEX@EDGE) push VERTEX@EDGE to STACK```