Implemente um algoritmo para verificar se um grafo é acíclico utilizando o algoritmo de busca em profundidade.

Passo 1

A questão pede para implementar um algoritmo que detecte se um grafo é acíclico usando busca em profundidade (DFS). Esse é um problema clássico de grafos dirigidos, onde precisamos identificar a existência de ciclos.
Vamos representar o grafo por uma lista de adjacência e usar um vetor de estados (cores) para cada vértice. Os estados são: 0 (não visitado), 1 (visitando/na recursão) e 2 (visitado). Quando, durante o DFS, encontrarmos um vizinho no estado 1, temos um ciclo.

Passo 2

O algoritmo geral é: para cada vértice não visitado executar DFS. No DFS, marcamos o vértice como 1, percorremos seus vizinhos e, se algum vizinho já estiver em 1, retornamos que há ciclo. Depois de visitar todos os vizinhos, marcamos o vértice como 2 e voltamos.
Vou detalhar o pseudocódigo passo a passo para ficar claro como implementar.
Finalmente, a complexidade do algoritmo é O(V+E), pois visitamos cada vértice e cada aresta no máximo uma vez.

Resposta

// Pseudocódigo para detectar ciclo em grafo dirigido usando DFS
função isAcyclic(Grafo G):
n ← número de vértices em G
cor ← vetor de tamanho n inicializado com 0 // 0=branco,1=cinza,2=preto
para v de 1 até n:
se cor[v] == 0:
se dfsDetect(v, G, cor) == verdadeiro:
retorna falso // encontrou ciclo
retorna verdadeiro // não encontrou ciclo
função dfsDetect(v, Grafo G, vetor cor):
cor[v] ← 1 // marcando como cinza (em recursão)
para cada w em G.adj[v]:
se cor[w] == 1:
retorna verdadeiro // ciclo (aresta de retorno)
se cor[w] == 0:
se dfsDetect(w, G, cor) == verdadeiro:
retorna verdadeiro
cor[v] ← 2 // marcando como preto (visitado)
retorna falso

Exercícios relacionados