树/树形搜索算法

A tree is a connected graph without cycles.

Suppose there are two different paths $P_1 = u\to x_1\to\dots\to x_m\to v$ and $P_2 = u\to y_1\to\dots\to y_n\to v$. Since these two paths are different, we know that there exists a point at which they diverge, and since they have the same destination, a point at which the converge again. Let $z_d$ be the vertex at which the two paths go to different edges, and $z_c$ be the next vertex that both paths share. It then follows that from $P_1$ we have a path from $z_d$ to $z_c$, and from $P_2$ a path from $z_c$ to $z_d$ with no edges in both these paths. Combining the two, we have formed a cycle $z_d \to \dots \to z_c \to \dots \to z_d$.

Note here that we were careful in choosing $z_c$ and $z_d$ using precise language, as $P_1$ and $P_2$ could converge and diverge at multiple points before reaching $v$.

Important: this same argument proves that $3,4,5,\dots$ are all wrong answers too. Therefore, all trees have precisely one path between any connected pairs of vertices.

Now let $G$ be any graph with this property, that each pair of vertices has either $0$ or $1$ path from one to the other. If $G$ had any cycles, then we could just cycle around many times, which violates this property. Therefore, $G$ is a tree. Therefore, a tree can equivalently be defined as any graph with precisely one path between any connected pairs of vertices.

Trees have a very nice structure that allow us to determine if there is a path from one vertex to another.

Depth-First Search

A depth-first search (DFS) starting at vertex $U$ and searching for $V\neq U$ iteratively searches all possible paths by going down one path until it stops, then recursing at the very last possible step. It's called depth-first because it goes down one path until it exhausts everything in that direction. Formally, the algorithm is:

We will use a stack $S$ to hold the vertices we need to search, and a list $L$ to contain the vertices we have already searched. Therefore, let $S$ initially contain the neighbors of $U$ and $L$ initially contain all of the vertices of the graph except $U$ and its neighbors. Now we perform the following step until we can no longer perform it:

Pop an element $W$ off of $S$, and delete $W$ from $L$. If $W=V$, we're done. Otherwise, for each neighbor of $W$ that is still in $L$, push it to the stack.

Breadth-First Search

A breadth-first search (BFS) starting at vertex $U$ and searching for $V\neq U$ iteratively expands from $U$ by checking the neighbors of all vertices. It's called breadth-first because breadth refers to width. Formally, the algorithm is:

We start with a list $L$ for the vertices we've already searched, and another list $M$ containing the neighbors of a given level. Initially, $L$ contains $U$, and $M$ contains the neighbors of $U$. We then perform the following step until we can no longer perform it:

If $V\in M$, we're done. Otherwise, add all elements of $M$ to $L$, and let $M'$ be the list of all vertices not in $L$ that are adjacent to some element of of $M$. Finally, replace $M$ with $M'$.

Comparing the Algorithms

DFS is better than BFS for memory purposes (it doesn't have to store so many neighbors). However, it is possible for a DFS to look for a very long time in the wrong direction, even if the $V$ is adjacent to $U$. For this reason, BFS may be faster because it covers more ground at each iteration.