Graphs are a collection of nodes connected by edges. Programmers run into graphs fairly regularly because almost any collection of things with binary relationships can be viewed as a graph. As practitioners we need to understand both graph theory (abstract structures) and graph data structures (concrete representations).
Three common families of graphs are:
- Digraphs (directed graphs): Graphs with directed edges (arcs).
- Dags (directed-acyclic graphs): Digraphs that don’t contain cycles.
- Trees: Dags with a single root and where non-roots have one parent. (Technically this is a rooted tree.)
This article looks at digraphs, dags, and trees from a programmer’s perspective. Where do we see them in practice? How can we recognize them? What can we do with them?
This article also includes a Java library for working with digraphs, dags, and trees. The library code is available at https://github.com/stevewedig/blog and is published to Maven for easy usage as a dependency. This is the third in a series of Java libraries I’m sharing on this blog. The first two were:
Article Outline
Steve Wedig's Notes 