10 Trees and Graph Algorithms

Graph Foundations

A graph is an ordered pair $G=(V,E)$, where $V$ is a set of vertices and $E$ is a set of edges. In an undirected graph, an edge joins two vertices without an orientation; in a directed graph, an edge is an ordered pair representing an arc from one vertex to another.

A walk may repeat vertices, whereas a path does not repeat vertices. A cycle is a closed path whose first and last vertices coincide. A graph is connected when every pair of vertices is joined by a path.

Two common representations emphasize different trade-offs:

• An adjacency matrix uses $O(\lvert V\rvert^2)$ space and tests whether a particular edge exists in $O(1)$ time.

• An adjacency list uses $O(\lvert V\rvert+\lvert E\rvert)$ space and is usually preferable for sparse graphs.

These definitions provide the vocabulary needed to understand trees and graph searches.

Trees and Their Structure

A tree is connected and acyclic. Several equivalent properties make trees easy to recognize:

• There is exactly one simple path between every pair of vertices.

• A tree with $n$ vertices has exactly $n-1$ edges.

• Removing any edge disconnects the graph.

• Adding any new edge creates exactly one cycle.

For example, the edges $\{a,b\},\{a,c\},\{b,d\},\{b,e\}$ form a tree with five vertices and four edges. Its leaves are $c$, $d$, and $e$, and the unique path from $c$ to $e$ is:

A leaf is a vertex of degree $1$. Every tree with at least two vertices has at least two leaves; the endpoints of a longest path must be leaves.

Takeaway: Connectivity supplies reachability, while the absence of cycles supplies uniqueness and minimality.

Spanning Trees and Minimum-Cost Connections

A spanning tree keeps every vertex of a connected graph but removes enough edges to eliminate all cycles. If the graph has vertex set $V$, every spanning tree has $\lvert V\rvert-1$ edges. One way to obtain one is to remove edges from cycles until no cycle remains.

In a weighted undirected graph, a minimum spanning tree minimizes the sum of the selected edge weights. Two standard greedy methods are:

• Kruskal's algorithm: Sort edges by increasing weight and add an edge when it joins two previously disconnected components. A disjoint-set structure can detect whether the edge would create a cycle.

• Prim's algorithm: Begin with one vertex and repeatedly add the cheapest edge connecting the current tree to a vertex outside it.

For a graph with vertices $A,B,C,D$ and edges $AB,AC,BC,BD,CD$, removing $BC$ leaves $AB,AC,BD,CD$. These edges connect all four vertices without a cycle, so they form a spanning tree.

Takeaway: A spanning tree is a connected backbone; a minimum spanning tree is the least-cost such backbone.

Rooted and Binary Trees

Choosing a root gives an undirected tree a hierarchical interpretation. The parent of a vertex is the next vertex on its path toward the root, and its children are the vertices immediately below it. Vertices with the same parent are siblings. Ancestors lie on the path toward the root, while descendants lie in the vertex's subtree.

The depth of a vertex is its distance from the root. The height of the tree is the greatest depth of any vertex. A vertex with no children is a leaf.

Suppose $r$ is the root, with children $a$ and $b$; $a$ has children $c$ and $d$; and $b$ has child $e$. Then $c$ and $d$ are siblings, $r$ is an ancestor of every vertex, and the height is $2$.

An ordered rooted tree specifies the order of each vertex's children. A binary tree is a rooted tree in which each vertex has at most two children, conventionally called the left and right children. This structure supports searching, expression parsing, sorting, and decision processes.

Tree Traversals

A tree traversal visits every vertex according to a systematic rule. With adjacency lists, a traversal normally takes $O(n)$ time on a tree with $n$ vertices because each vertex and edge is processed only a constant number of times.

Breadth-first search (BFS) uses a queue and visits vertices level by level. In a rooted tree, it processes all vertices at depth $0$, then depth $1$, then depth $2$, and so on. With equal edge weights, BFS computes the shortest distance from the root to every reachable vertex.

Depth-first search (DFS) follows one branch as far as possible before backtracking. Its principal tree orders are:

• Preorder: process a vertex before its children.

• Postorder: process all children before the vertex.

• Inorder: in a binary tree, process the left subtree, then the vertex, then the right subtree.

For the binary tree with root $A$, children $B$ and $C$, and children $D,E$ under $B$, the orders are:

• Preorder: $A,B,D,E,C$

• Inorder: $D,B,E,A,C$

• Postorder: $D,E,B,C,A$

• Level order: $A,B,C,D,E$

Takeaway: BFS emphasizes distance and levels; DFS emphasizes depth, backtracking, and subtree order.

Core Graph Algorithms

BFS and DFS extend naturally from trees to general graphs. With adjacency lists, both run in $O(\lvert V\rvert+\lvert E\rvert)$ time because each vertex and edge is examined only a constant number of times.

Reachability and Components

Starting BFS or DFS at a vertex $s$ visits exactly the vertices reachable from $s$. To find every connected component of an undirected graph, repeatedly begin a search from an unvisited vertex. Each search identifies one component.

Cycle Detection and Tree Testing

During DFS in an undirected graph, an already visited neighbor that is not the current vertex's parent indicates a cycle. A connected undirected graph is a tree exactly when it has $\lvert E\rvert=\lvert V\rvert-1$ and contains no cycle. Thus, a practical test combines a connectivity search with an edge-count check.

Shortest Paths in Unweighted Graphs

BFS explores vertices in nondecreasing order of distance from its source. Therefore, when a vertex is first discovered, its distance is minimal. Storing a predecessor for each newly discovered vertex allows a shortest path to be reconstructed by following predecessor links backward.

Those predecessor links form a shortest-path tree rooted at the source: the tree records one selected shortest route to every reachable vertex.

Applications and Algorithm Selection

A directed acyclic graph, or DAG, can be arranged in a topological ordering. For every directed edge $u\to v$, the vertex $u$ must occur before $v$. A DFS-based method records vertices in postorder and reverses that order. A directed cycle prevents any topological ordering because the required precedence relations would contradict one another.

Trees and graph algorithms appear in many practical structures:

• File systems: Directories form a rooted hierarchy, and a path records successive child choices from the root.

• Organization and classification: Supervisory structures and taxonomies use parent-child relationships.

• Expression trees: Operators are internal vertices and operands are leaves. For $(a+b)\times c$, multiplication is the root, addition is its left child, and $c$ is its right child. Postorder lists operands before their operators, making evaluation convenient.

• Decision trees: Internal vertices hold tests, branches represent outcomes, and leaves represent final decisions.

• Infrastructure networks: A spanning tree supplies a connected backbone without redundant links, while a minimum spanning tree minimizes construction or maintenance cost.

• Data structures: Binary search trees support ordered searching, heaps support priority queues, and tries organize strings by shared prefixes.

Choose the method according to the task:

• Visit reachable vertices: BFS or DFS.

• Find shortest paths with equal edge weights: BFS.

• Explore deeply or process dependencies: DFS.

• Find connected components: repeated BFS or DFS.

• Detect cycles: BFS or DFS with parent or recursion-state tracking.

• Produce a topological ordering: DFS or indegree-based processing on a DAG.

• Connect all vertices at minimum total weight: Kruskal's or Prim's algorithm.

Final takeaway: Trees simplify connectivity by removing cycles, while BFS, DFS, and greedy spanning-tree algorithms turn that structure into practical methods for searching, optimization, organization, and decision-making.