Exercises: Graph Data Structures
Mar 052018Before attempting these exercises, you should read the posts about graphs, graph problems, and graph data structures.
Graph Problems
Mar 052018Graphs 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”.
Graph Data Structures
Mar 052018A 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.
Graphs
Mar 052018A 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.