# Generic Graph Search Both [Breadth First Search](Breadth%20First%20Search.md) and [Depth-First-Search](Depth-First-Search.md) are examples of a **Generic Graph Search**, which can be described nicely via pseudocode as: **Input**: graph $G = (V, E)$ and a vertex $s \in V$ **Postcondition**: a vertex is reachable from $s$ if and only if it is marked as "explored" **Algorithm**: * mark $s$ as explored, all other vertices unexplored * **while** there is an edge $(v, w) \in E$ with $v$ explored and $w$ unexplored, do: * choose some such edge $(v,w)$ (this is *underspecified*) * mark $w$ as explored ### Key Idea Every iteration of the `GenericSearch` algorithm above chooses an edge that is "*on the frontier*" of the explored part of the graph, with one endpoint explored and the other unexplored. There can be many such edges and to specify the algorithm fully we need a method for choosing one of them. The two most important strategies are [Breadth First Search](Breadth%20First%20Search.md) and [Depth-First-Search](Depth-First-Search.md). --- Date: 20211015 Links to: Tags: References: * Algorithms Illuminated 2, pg 20 (chapter 8)