A graph is made up of nodes and edges. A directed graph consists of a set of nodes and a set of directed edges. Most graphs are undirected.

Applications of graphs include transportation networks, communication networks, information networks, social networks, and dependency networks.

A path traversing a graph is simple if all its vertices are distinct from one another. A cycle is a series of nodes that cycles back to where it began. In a directed graph, the path or cycle must respect the directionality of edges.

An undirected graph is connected if there is a path for every pair of nodes. The distance between two nodes is the minimum number of edges in the path.

A tree is an undirected graph not containing a cycle. Relationships between adjacent nodes are define by ancestor or descendant. A leaf is a node with no descendants.

Every n-node tree has exactly n-1 edges.

Let G be an undirected graph on n nodes. Any two of the following statements implies the third:

1. G is connected
2. G does not contain a cycle
3. G has n-1 edges

Explored outward from root adding one ‘layer’ at a time. The root and all nodes joined to the root make up the first later.

For each j >= 1, layer L(j) produced by BFS consists of all nodes at distance j from root (s). There is a path from s to t iff t appears in some layer.

Let T be a BFS tree, let x and y be nodes in T belonging to layers L(i) and L(j) respectively, and let (x,y) be an edge of G. Then i and j differ by at most 1.

The set produced at the end of the algorithm is precisely the connected component containing the starting node. The actual path is recovered by finding the targeted node then tracing back to the starting node.

In depth-first search, begin at the root and follow the leading edge until a dead end. Backtrack until you find a node with an unexplored neighbor. This is best implemented recursively.

For a given recursive call DFS(u), all nodes that are marked “Explored” between the invocation and end of this recursive call are descendants of u in T. Let x and y be nodes in T, and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.

For any two nodes s and t in a graph, their connected components are either identical or disjoint. An algorithm, either BFS or DFS, visits each node, connecting it properly.