Grafos são estruturas de dados formadas por vértices e arestas. Em grafos os vértices que fazem parte do grafo podem ou não estar conectados pelas arestas. As arestas sempre estão conectadas a pelo menos dois vértices. As arestas podem ser unidirecionais ou bidirecionais. Em um mesmo grafo as arestas são representadas por seta se a ligação entre os vértices é direcional, ou seja, A para B é diferente de B para A. As arestas são representadas por linhas se a ligação entre os vértices é bidirecional, ou seja, A para B é igual B para A. Os grafos servem para representar elementos conectados ou não, por exemplo, em uma região com cidades e estradas, sendo as cidades representadas pelos vértices e as estradas, pelas arestas. Com base no contexto apresentado, assinale a alternativa correta.

Vamos avaliar as alternativas com base nas aplicações típicas de grafos e dos algoritmos de busca em profundidade (DFS) e em largura (BFS).

1. “O algoritmo de busca em profundidade resolve o problema de identificar o grau de separação entre pessoas numa rede social.” O “grau de separação” (menor número de arestas entre duas pessoas) é um problema de menor caminho em grafo não ponderado, cuja abordagem clássica é a busca em largura (BFS), não a DFS. Logo, falsa.

2. “O algoritmo de busca em profundidade descobre os computadores conectados numa rede ponto a ponto (peer-to-peer).” Para descobrir computadores alcançáveis/conectados a partir de um nó (componente conexa/alcançabilidade), tanto DFS quanto BFS podem ser usados. A frase atribui isso como se fosse algo específico da DFS, o que torna a alternativa imprecisa como “a correta” única. Em provas, esse tipo de tarefa não é exclusiva da DFS. Logo, não é a melhor correta.

3. “O algoritmo de busca em profundidade é usado em sistemas de GPS para obter os pontos turísticos ao redor de onde está.” GPS/rotas normalmente envolvem pesos (distância/tempo) e usam algoritmos como Dijkstra ou A*, não DFS. Além disso, “pontos turísticos ao redor” é mais consulta geográfica do que busca em grafo via DFS. Falsa.

4. “Somente o algoritmo de busca em profundidade resolve o problema de detecção de caminho.” Detectar se existe caminho entre dois vértices pode ser feito por DFS ou BFS (ambas determinam alcançabilidade). O “somente” torna falsa.

5. “Os algoritmos de busca em profundidade e em largura são usados para detectar ciclos.” A detecção de ciclos pode ser feita com DFS (muito comum, inclusive com marcação de estados/cores em grafos direcionados) e também pode ser feita com BFS (por exemplo, em grafos não direcionados, verificando arestas para vértices já visitados que não sejam o pai; e há variações para direcionados). Portanto, é a alternativa correta.

Alternativa correta: (E).