Trees and graphs

A graph is a structure made of vertices (nodes) and the edges that connect them. Cities and the roads between them, friends in a social network, and web pages and the links between them are described by graphs. Edges can be directed (a one-way road) or undirected, and a number such as a distance or a cost can be attached to an edge. The degree of a vertex is the number of edges that meet at it; in any undirected graph the sum of all degrees equals twice the number of edges.

A tree is a connected graph with no cycles (closed paths). It has one special vertex, the root; every other vertex has exactly one “parent”, and vertices without children are called leaves. Examples of trees are the folder structure of a computer, a family tree and a diagram of logical choices. A tree with n vertices always has exactly n − 1 edges.

In Python it is convenient to store a graph as lists of neighboring vertices: each vertex is matched with the list of its neighbors. For example, create a dictionary with g = dict(), then g["A"] = ["B", "C"], g["B"] = ["A", "D"], g["C"] = ["A"], g["D"] = ["B"]. With this notation the neighbors of vertex A are in g["A"], they are easy to find and little memory is used.

The most common task on a graph is traversing its vertices. Breadth-first search starts at a vertex, first visits all its neighbors, then the neighbors of those neighbors (using a queue); it finds the path with the fewest edges. Depth-first search goes along one path as far as possible and then returns (using a stack or recursion). Navigation apps, recommendation systems and network routing are based on graph algorithms.

Key takeaways

• A graph consists of vertices and edges; edges may be directed or undirected.
• A tree is a connected graph without cycles; a tree with n vertices has n − 1 edges.
• A tree has a root, a parent-child relation and leaves.
• In Python a graph is conveniently stored in a dictionary with lists of neighbors.
• Breadth-first search finds the shortest path (by number of edges).