## Exercises: Graph Data Structures

Mar 052018Before attempting these exercises, you should read the posts about graphs, graph problems, and graph data structures.

Before attempting these exercises, you should read the posts about graphs, graph problems, and graph data structures.

Graphs and networks are useful because they’re very general — graphs show up almost everywhere.
Given that there are so many different examples of graph *structures,* then, it’s perhaps surprising that there aren’t actually very many different kinds of *problems* involving graphs.

That is, there are many computing problems which graphs can help with, but not many *kinds* of problem.
Usually, after translating from the problem domain into the language of graphs, the problem turns out to be one of a relatively small number of “classical graph problems”.

A graph is an abstract model of a *relation* between pairs of things.
In the previous post we identified many relations which can be modelled as graphs; however, we don’t yet have any data structures to represent graphs in computer programs.

A tree is an abstract idea, a common kind of structure which we find across many different applications.
A tree models a *relation* between pairs of things:

- A section of an article
*contains*another section, - A directory
*contains*another directory, - An HTML tag
*contains*other HTML tags, - An employee
*manages*another employee, - A process
*spawns*another process.

A “relation between pairs of things” is very abstract and very general — in almost any context, there are relations between pairs of things which we might want to model in a computer program. However, not every relation defines a tree structure.