Atingibilidade (teoria dos grafos)

Em teoria dos grafos, a atingibilidade se refere a capacidade de ir de um vértice para outro em um grafo. Dizemos que um vértice ${\displaystyle s}$ pode alcançar outro vértice ${\displaystyle t}$ (ou que ${\displaystyle t}$ é atingível a partir de ${\displaystyle s}$) se exite uma sequência de vértices adjacentes (ex.: um caminho) que começam com ${\displaystyle s}$ e terminam com ${\displaystyle t}$.

Em um grafo não-direcionado, é suficiente identificar apenas os componentes conexos, assim como qualquer par de vértices, em tal grafo, pode se alcançar se e somente se eles pertencem ao mesmo componente conexo. Os componentes conexos de um grafo podem ser identificados em tempo linear. Lembramos que este artigo foca em atingibilidade nas configurações de grafos orientados.