Detetando Ciclos em um Grafo
Detetar ciclos em grafos é essencial para compreender a estrutura e as propriedades dos dados em vários domínios, como gestão de dependências, deteção de deadlocks e roteamento de redes. Ao identificar ciclos, conseguimos evitar problemas como dependências circulares, ineficiências e até falhas de sistema.
Uma versão modificada do DFS pode ser usada para detetar um ciclo em um grafo.
Ao percorrer um grafo com DFS, normalmente marcamos os vértices como visitados ou não visitados. Ao detetar ciclos, isso não é suficiente. Precisamos de 3 estados para cada vértice:
- Vértice não visitado
- Vértice e respetiva subárvore DFS em processamento
- Vértice totalmente visitado (com todos os nós filhos)
Assim, podemos detetar um ciclo se, ao percorrer o grafo, chegarmos a um vértice que esteja atualmente em processamento.
➰
Se chegarmos a um vértice marcado como em processamento (2) ao percorrer o grafo, então encontrámos um ciclo.
O algoritmo executa os seguintes passos:
- Marcar todos os vértices como não visitados
- Iniciar um DFS a partir de algum vértice
- Para o vértice atual, marcar como em processamento
- Quando todos os nós filhos do vértice atual estiverem processados, marcar o vértice como totalmente visitado
O algoritmo pode ser aplicado tanto em grafos dirigidos como em grafos não dirigidos:
color = [1] * n # cor dos vértices (1: não visitado, 2: em processamento, 3: totalmente visitado)
def dfs(v, p): # depth-first search (v: vértice, p: pai)
color[v] = 2 # marcar vértice como em processamento
cycle = False # indicador para verificar se existe ciclo
for to in g[v]: # para cada vértice ligado a v
if color[to] == 1: # se o vértice não foi visitado
cycle |= dfs(to, v) # chamar dfs no vértice e assinalar se existe ciclo
elif color[to] == 2 and to != p: # se o vértice está em processamento e não é o pai
cycle = True # marcar indicador como True
color[v] = 3 # marcar vértice como totalmente visitado
return cycle # retornar indicador
for start in range(n): # para cada vértice
if color[start] == 1: # se o vértice não foi visitado
if dfs(start, -1): # chamar dfs no vértice e verificar se há ciclo
print('Cycle') # imprimir ciclo
break # interromper o loop
else: # se o loop não foi interrompido por um break
print('No cycle') # imprimir que não há cicloObserve que, para grafos direcionados, levar em conta o vértice-pai não é necessário. Consegue dizer porquê 🤔?
Vamos simular o algoritmo em vários exemplos de entrada:
n = 4, e = 4
Os pares de entrada
a, b são os seguintes: [(0, 1), (0, 2), (1, 2), (3, 2)]O vértice inicial é 3
v=3, p=-1→color = [1, 1, 1, 2]⇒ explorar todos os vizinhos de 3 ⇒[2]
v=2, p=3→color = [1, 1, 2, 2]⇒ explorar todos os vizinhos de 2 ⇒[0, 1]
v=0, p=2→color = [2, 1, 2, 2]⇒ explorar todos os vizinhos de 0 ⇒[1, 2]
v=1, p=0→color = [2, 2, 2, 2]⇒ explorar todos os vizinhos de 1 ⇒[0, 2]⇒ 0 está marcado como 1 ⇒ marcarcycle = True⇒return True
Desafio: Verificar se um grafo contém um ciclo
Dado um grafo direcionado com
v vértices e e arestas, a sua tarefa é verificar se o grafo contém um ciclo.Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 100 000) e e (1 ≤ e ≤ 100 000).As seguintes
e linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v) que significam que existe um caminho do vértice v1 para o vértice v2.Saída
O programa deve imprimir
Yes se o grafo tiver um ciclo e No caso contrário.Exemplos
Input | Output |
4 3
1 2
2 3
3 1
| Yes |
4 3
1 2
1 3
2 4 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB