# Breadth-First-Search (BFS)
The path finding algorithm is guided by a form of breadth-first-search (BFS).
The search starts from the target binding. The main reasons for starting at the back are:
- There's always only a single target, but there may be multiple trust anchors.
We can start search without having to know where to end up.
- Trust depths restrict how deep a path may be in the forward direction.
By starting from the back, we can disqualify many paths early due to restrictions of delegation checks.
## Methodology
Starting from the target binding, each connected node is explored one at a time, with newly discovered nodes being put at the end of the BFS queue.
In contrast to a typical BFS, paths that have a higher "throughput" are favored, **as long** as they have the same depth/length.
The length of the path is the most important criterion for choosing a path, while the trust amount is merely used as a tie-breaker if multiple paths lead to a certificate or target binding.
If both length and trust are identical, any of the paths may be used.
So in the following scenario:
The path with the bigger trust amount will be chosen:
## BFS with Trust Depth
In Web of Trust networks, delegation edges may be limited to a depth of `Y`. This means that trust may only be extended along at most `Y` followup edges, after that delegation edge.
Consider the following graph, which provides a special annotation on each edge.
- `t:X` means a trust amount of `X`.
- `d:Y` means a trust depth of `Y`.
If no trust depth is provided, trust may not be further delegated.
Note that the edge `TA -> C1` only has a trust depth of 2, which allows delegation of trust via `C1 -> C2`, but is insufficient for reaching the binding `Target, target@foo.example`. Along the path via `C1`, the certificate `Target` is not considered a "trusted introducer".
Since path finding happens from the back, `C2 -> Target` and `C2 -> C1` would be explored, but the algorithm terminates at `C1`, as indicated by the violet color, since the trust depth exceeds the current path length.
Hence, in this network, the only valid path is `TA -> C3 -> C4 -> Target -> Binding`.
