# 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:

![Simple BFS](../Diagrams/figures/BFS/BFS-simple.svg)

The path with the bigger trust amount will be chosen:

![Simple BFS with path](../Diagrams/figures/BFS/BFS-simple_path.svg)

## 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.

![Complex BFS](../Diagrams/figures/BFS/BFS-forked.svg)

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`.

![Complex BFS with Path](../Diagrams/figures/BFS/BFS-forked_path.svg)
