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

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:

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!