"Muitos problemas podem ser descritos por meio de grafos, nos quais a solução para o problema requer que realizemos uma busca pelo grafo. As buscas, em geral, partem de um nó inicial em direção a um nó alvo, fazendo com que tenhamos que percorrer toda uma sequência ordenada de nós e arestas. Além disso, o próprio caminho, em si, pode ser objeto da busca, isto é, às vezes a solução reside no caminho percorrido, e não em um nó alvo específico."

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.

Considerando tanto o algoritmo de busca em largura, quanto em profundidade, para que seja possível que tais algoritmos consigam navegar por todos os nós de um grafo, é imprescindível que o grafo seja:
Alternativas
Alternativa 1:
Um dígrafo.

Alternativa 2:
Orientado.

Alternativa 3:
Conexo.

Alternativa 4:
Ponderado.

Alternativa 5:
Um multigrafo.