When learning about file systems, you’ve encountered a specific example of the tree structure: your computer files are organized into trees! We will now review the formal vocabulary for how to talk about trees.
⊕ root, node, leaf, branch
⊕ parent, child, sibling
A graph is a broader category which encompasses trees; all graphs can be considered a relationship between a set of vertices and a set of edges which connect nodes. You may have encountered examples of graphs in your daily life. We will now formalize this concept so that we can write and prove rigorous algorithms about graphs.
⊕ vertex, edge
⊕ directed vs undirected graph
⊕ walk, path, circuit, cycle
⊕ breadth-first / depth-first search