Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
Sem resumo de edição |
||
Linha 3:
=== Detecção de Ciclos por Busca em Profundidade ===
Um método eficiente para detectar ciclos em grafos direcionados é por meio do algoritmo de busca em profundidade. Intuitivamente, o algoritmo começa num nó raiz (selecionando algum nó como sendo o raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder.
Formalmente, um algoritmo de busca em profundidade realiza uma busca não-informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não possui filhos (nó folha). Então a busca retrocede e começa no próximo nó. Numa implementação não-recursiva, todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração.
==== Pseudo-Código ====
Linha 19 ⟶ 21:
10 marcar ''e'' como aresta de retorno
11 todo o caminho de ''w'' até ''v'' representa um ciclo
A seguir é apresentado um exemplo da execução do algoritmo de busca em profundidade. A aresta (4,2), na cor verde, representa uma aresta de retorno, e o caminho do vértice (2,3,4) representa um ciclo do grafo.
[[Ficheiro:GraphDFS.png|commoldura|centro|Detecção de Ciclos por Busca em Profundidade]]
| |||